diff options
author | Jim Meyering <meyering@fb.com> | 2020-11-25 16:49:51 -0800 |
---|---|---|
committer | Jim Meyering <meyering@fb.com> | 2020-11-26 10:32:00 -0800 |
commit | 192e59903c7d313bb47de3d5c15b3dc634e98c5f (patch) | |
tree | 94f500ed106d001dcbe89d6aed7da086bde2708b | |
parent | 9095818f2669ceed97c41d72c5269f60cbfa9260 (diff) | |
download | grep-192e59903c7d313bb47de3d5c15b3dc634e98c5f.tar.gz |
grep: avoid performance regression with many patterns
* src/grep.c (hash_pattern): Switch from PJW to DJB2, to avoid an
O(N) to O(N^2) performance regression due to hash collisions with
patterns from e.g., seq 500000|tr 0-9 A-J
Reported by Frank Heckenbach in https://bugs.gnu.org/44754
* NEWS (Bug fixes): Mention it.
* tests/hash-collision-perf: New file.
* tests/Makefile.am (TESTS): Add it.
-rw-r--r-- | NEWS | 7 | ||||
-rw-r--r-- | src/grep.c | 5 | ||||
-rw-r--r-- | tests/Makefile.am | 1 | ||||
-rwxr-xr-x | tests/hash-collision-perf | 53 |
4 files changed, 64 insertions, 2 deletions
@@ -2,6 +2,13 @@ GNU grep NEWS -*- outline -*- * Noteworthy changes in release ?.? (????-??-??) [?] +** Bug fixes + + Preprocessing N patterns would take at least O(N^2) time when too many + patterns hashed to too few buckets. This now takes seconds, not days: + : | grep -Ff <(seq 6400000 | tr 0-9 A-J) + [Bug#44754 introduced in grep 3.5] + * Noteworthy changes in release 3.6 (2020-11-08) [stable] @@ -128,8 +128,9 @@ hash_pattern (void const *pat, size_t n_buckets) { size_t h = 0; intptr_t pat_offset = (intptr_t) pat - 1; - for (char const *s = pattern_array + pat_offset; *s != '\n'; s++) - h = *s + ((h << 9) | (h >> (SIZE_WIDTH - 9))); + unsigned char const *s = (unsigned char const *) pattern_array + pat_offset; + for ( ; *s != '\n'; s++) + h = h * 33 ^ *s; return h % n_buckets; } static bool _GL_ATTRIBUTE_PURE diff --git a/tests/Makefile.am b/tests/Makefile.am index 480bfb47..b1b5d61a 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -109,6 +109,7 @@ TESTS = \ grep-dev-null \ grep-dev-null-out \ grep-dir \ + hash-collision-perf \ help-version \ high-bit-range \ in-eq-out-infloop \ diff --git a/tests/hash-collision-perf b/tests/hash-collision-perf new file mode 100755 index 00000000..38c876de --- /dev/null +++ b/tests/hash-collision-perf @@ -0,0 +1,53 @@ +#!/bin/sh +# Test for this performance regression: +# grep-3.5 and 3.6 would take O(N^2) time for some sets of input regexps. + +# Copyright 2020 Free Software Foundation, Inc. + +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. + +# You should have received a copy of the GNU General Public License +# along with this program. If not, see <https://www.gnu.org/licenses/>. + +. "${srcdir=.}/init.sh"; path_prepend_ ../src + +fail=0 + +: > empty || framework_failure_ + +# Construct a test case that consumes enough CPU time that we don't +# have to worry about measurement noise. This first case is searching +# for digits, which never exhibited a problem with hash collisions. +n_pat=40000 +while :; do + seq $n_pat > in || framework_failure_ + small_ms=$(LC_ALL=C user_time_ 1 grep --file=in empty) || fail=1 + test $small_ms -ge 200 && break + n_pat=$(expr $n_pat '*' 2) +done + +# Now, search for those same digits mapped to A-J. +# With the PJW-based hash function, this became O(N^2). +seq $n_pat | tr 0-9 A-J > in || framework_failure_ +large_ms=$(LC_ALL=C user_time_ 1 grep --file=in empty) || fail=1 + +# Deliberately recording in an unused variable so it +# shows up in set -x output, in case this test fails. +ratio=$(expr "$large_ms" / "$small_ms") +warn_ ratio=$ratio + +# The duration of the latter run must be no more than 10 times +# that of the former. Using recent versions prior to this fix, +# this test would fail due to ratios > 800. Using the fixed version, +# it's common to see a ratio less than 1. +returns_ 1 expr $small_ms '<' $large_ms / 10 || fail=1 + +Exit $fail |