tests/many-regex-performance

   1 #!/bin/sh
   2 # Test for this performance regression:
   3 # grep-3.4 would require O(N^2) RSS for N regexps
   4 # grep-3.5 requires O(N) in the most common cases.
   5
   6 # Copyright 2020-2025 Free Software Foundation, Inc.
   7
   8 # This program is free software: you can redistribute it and/or modify
   9 # it under the terms of the GNU General Public License as published by
  10 # the Free Software Foundation, either version 3 of the License, or
  11 # (at your option) any later version.
  12
  13 # This program is distributed in the hope that it will be useful,
  14 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 # GNU General Public License for more details.
  17
  18 # You should have received a copy of the GNU General Public License
  19 # along with this program.  If not, see <https://www.gnu.org/licenses/>.
  20
  21 . "${srcdir=.}/init.sh"; path_prepend_ ../src
  22
  23 fail=0
  24
  25 # This test is susceptible to failure due to differences in
  26 # system load during the two test runs, so we'll mark it as
  27 # "expensive", making it less likely to be run by regular users.
  28 expensive_
  29 require_perl_
  30
  31 # Make the quick/small input large enough so that even on high-end
  32 # systems this first invocation takes at least 10ms of user time.
  33 word_list=/usr/share/dict/linux.words
  34
  35 # If $word_list does not exist, generate an input that exhibits
  36 # similar performance characteristics.
  37 if ! test -f $word_list; then
  38   # Generate data comparable to that word list.
  39   # Note how all "words" start with "a", and that there is
  40   # a small percentage of lines with at least one "." metachar.
  41   # This requires /dev/urandom, so if it's not present, skip
  42   # this test. If desperate, we could fall back to using
  43   # tar+compressed lib/*.c as the data source.
  44   test -r /dev/urandom \
  45     || skip_ 'this system has neither word list nor working /dev/urandom'
  46   word_list=word_list
  47   ( echo a; cat /dev/urandom            \
  48     | LC_ALL=C tr -dc 'a-zA-Z0-9_'      \
  49     | head -c500000                     \
  50     | sed 's/\(........\)/\1\n/g'       \
  51     | sed s/rs/./                       \
  52     | sed s/./a/                        \
  53     | sort                              \
  54   ) > $word_list
  55 fi
  56
  57 n_lines=2000
  58 while :; do
  59   sed ${n_lines}q < $word_list > in || framework_failure_
  60   small_ms=$(LC_ALL=C user_time_ 1 grep --file=in -v in) || fail=1
  61   test $small_ms -ge 10 && break
  62   n_lines=$(expr $n_lines + 2000)
  63 done
  64
  65 # Now, run it again, but with 20 times as many lines.
  66 n_lines=$(expr $n_lines \* 20)
  67 sed ${n_lines}q < $word_list > in || framework_failure_
  68 large_ms=$(LC_ALL=C user_time_ 1 grep --file=in -v in) || fail=1
  69
  70 # Deliberately recording in an unused variable so it
  71 # shows up in set -x output, in case this test fails.
  72 ratio=$(expr "$large_ms" / "$small_ms")
  73
  74 # The duration of the larger run must be no more than 60 times
  75 # that of the small one.  Using recent versions prior to this fix,
  76 # this test would fail due to ratios larger than 300.  Using the
  77 # fixed version, it's common to see a ratio of 20-30.
  78 returns_ 1 expr $small_ms '<' $large_ms / 60 || fail=1
  79
  80 Exit $fail