| 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-2021 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 | : > empty || framework_failure_
|
|---|
| 25 |
|
|---|
| 26 | # Construct a test case that consumes enough CPU time that we don't
|
|---|
| 27 | # have to worry about measurement noise. This first case is searching
|
|---|
| 28 | # for digits, which never exhibited a problem with hash collisions.
|
|---|
| 29 | n_pat=40000
|
|---|
| 30 | while :; do
|
|---|
| 31 | seq $n_pat > in || framework_failure_
|
|---|
| 32 | small_ms=$(LC_ALL=C user_time_ 1 grep --file=in empty) || fail=1
|
|---|
| 33 | test $small_ms -ge 200 && break
|
|---|
| 34 | n_pat=$(expr $n_pat '*' 2)
|
|---|
| 35 | done
|
|---|
| 36 |
|
|---|
| 37 | # Now, search for those same digits mapped to A-J.
|
|---|
| 38 | # With the PJW-based hash function, this became O(N^2).
|
|---|
| 39 | seq $n_pat | tr 0-9 A-J > in || framework_failure_
|
|---|
| 40 | large_ms=$(LC_ALL=C user_time_ 1 grep --file=in empty) || fail=1
|
|---|
| 41 |
|
|---|
| 42 | # Deliberately recording in an unused variable so it
|
|---|
| 43 | # shows up in set -x output, in case this test fails.
|
|---|
| 44 | ratio=$(expr "$large_ms" / "$small_ms")
|
|---|
| 45 | warn_ ratio=$ratio
|
|---|
| 46 |
|
|---|
| 47 | # The duration of the latter run must be no more than 10 times
|
|---|
| 48 | # that of the former. Using recent versions prior to this fix,
|
|---|
| 49 | # this test would fail due to ratios > 800. Using the fixed version,
|
|---|
| 50 | # it's common to see a ratio less than 1.
|
|---|
| 51 | returns_ 1 expr $small_ms '<' $large_ms / 10 || fail=1
|
|---|
| 52 |
|
|---|
| 53 | Exit $fail
|
|---|
