| 1 |
#!/bin/sh |
| 2 |
# Test for this performance regression: |
| 3 |
# grep-3.5 and 3.6 would take O(N^2) time for some sets of input regexps. |
| 4 |
|
| 5 |
# Copyright 2020-2025 Free Software Foundation, Inc. |
| 6 |
|
| 7 |
# This program is free software: you can redistribute it and/or modify |
| 8 |
# it under the terms of the GNU General Public License as published by |
| 9 |
# the Free Software Foundation, either version 3 of the License, or |
| 10 |
# (at your option) any later version. |
| 11 |
|
| 12 |
# This program is distributed in the hope that it will be useful, |
| 13 |
# but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 14 |
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 15 |
# GNU General Public License for more details. |
| 16 |
|
| 17 |
# You should have received a copy of the GNU General Public License |
| 18 |
# along with this program. If not, see <https://www.gnu.org/licenses/>. |
| 19 |
|
| 20 |
. "${srcdir=.}/init.sh"; path_prepend_ ../src |
| 21 |
|
| 22 |
fail=0 |
| 23 |
|
| 24 |
require_perl_ |
| 25 |
|
| 26 |
: > empty || framework_failure_ |
| 27 |
|
| 28 |
# Construct a test case that consumes enough CPU time that we don't |
| 29 |
# have to worry about measurement noise. This first case is searching |
| 30 |
# for digits, which never exhibited a problem with hash collisions. |
| 31 |
n_pat=40000 |
| 32 |
while :; do |
| 33 |
seq $n_pat > in || framework_failure_ |
| 34 |
small_ms=$(LC_ALL=C user_time_ 1 grep --file=in empty) || fail=1 |
| 35 |
test $small_ms -ge 200 && break |
| 36 |
n_pat=$(expr $n_pat '*' 2) |
| 37 |
case $n_pat:$small_ms in |
| 38 |
640000:0) skip_ 'user_time_ appears always to report 0 elapsed ms';; |
| 39 |
esac |
| 40 |
done |
| 41 |
|
| 42 |
# Now, search for those same digits mapped to A-J. |
| 43 |
# With the PJW-based hash function, this became O(N^2). |
| 44 |
seq $n_pat | tr 0-9 A-J > in || framework_failure_ |
| 45 |
large_ms=$(LC_ALL=C user_time_ 1 grep --file=in empty) || fail=1 |
| 46 |
|
| 47 |
# Deliberately recording in an unused variable so it |
| 48 |
# shows up in set -x output, in case this test fails. |
| 49 |
ratio=$(expr "$large_ms" / "$small_ms") |
| 50 |
|
| 51 |
# The duration of the latter run must be no more than 10 times |
| 52 |
# that of the former. Using recent versions prior to this fix, |
| 53 |
# this test would fail due to ratios > 800. Using the fixed version, |
| 54 |
# it's common to see a ratio less than 1. |
| 55 |
returns_ 1 expr $small_ms '<' $large_ms / 10 || fail=1 |
| 56 |
|
| 57 |
Exit $fail |