Debian Codegraph @

tests/hash-collision-perf

raw
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