bug#40634: Massive pattern list handling with -E format seems very slow since 2.28.

[Norihiro Tanaka]

+ grep-2.2/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
grep-2.2/src/grep: invalid option -- 'm'
Usage: grep [OPTION]... PATTERN [FILE]...
Try `grep --help' for more information.
real 0.00
user 0.00
sys 0.00
+ grep-2.3/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
grep-2.3/src/grep: invalid option -- 'm'
Usage: grep [OPTION]... PATTERN [FILE]...
Try `grep --help' for more information.
real 0.00
user 0.00
sys 0.00
+ grep-2.4/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
grep-2.4/src/grep: invalid option -- 'm'
Usage: grep [OPTION]... PATTERN [FILE]...
Try `grep --help' for more information.
real 0.00
user 0.00
sys 0.00
+ grep-2.4.1/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
grep-2.4.1/src/grep: invalid option -- 'm'
Usage: grep [OPTION]... PATTERN [FILE]...
Try `grep --help' for more information.
real 0.00
user 0.00
sys 0.00
+ grep-2.4.2/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
grep-2.4.2/src/grep: invalid option -- 'm'
Usage: grep [OPTION]... PATTERN [FILE]...
Try `grep --help' for more information.
real 0.00
user 0.00
sys 0.00
+ grep-2.5.4/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 13.58
user 13.43
sys 0.14
+ grep-2.6/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 3.95
user 3.51
sys 0.42
+ grep-2.6.1/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 3.97
user 3.86
sys 0.11
+ grep-2.6.2/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 3.98
user 3.69
sys 0.28
+ grep-2.6.3/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 3.99
user 3.94
sys 0.04
+ grep-2.7/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 3.93
user 3.68
sys 0.24
+ grep-2.8/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 3.89
user 3.83
sys 0.05
+ grep-2.9/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 3.92
user 3.63
sys 0.27
+ grep-2.10/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 3.93
user 3.65
sys 0.27
+ grep-2.11/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 3.98
user 3.89
sys 0.08
+ grep-2.12/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 3.95
user 3.87
sys 0.06
+ grep-2.13/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 3.97
user 3.85
sys 0.11
+ grep-2.14/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 4.01
user 3.91
sys 0.09
+ grep-2.15/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 4.05
user 3.99
sys 0.05
+ grep-2.16/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 3.91
user 3.50
sys 0.40
+ grep-2.17/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 3.98
user 3.94
sys 0.03
+ grep-2.18/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 3.98
user 3.87
sys 0.10
+ grep-2.19/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 0.54
user 0.50
sys 0.03
+ grep-2.20/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 0.62
user 0.57
sys 0.04
+ grep-2.21/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 0.43
user 0.41
sys 0.02
+ grep-2.22/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 0.18
user 0.16
sys 0.01
+ grep-2.23/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 0.18
user 0.13
sys 0.04
+ grep-2.24/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 0.18
user 0.13
sys 0.04
+ grep-2.25/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 0.18
user 0.16
sys 0.01
+ grep-2.26/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 0.18
user 0.14
sys 0.04
+ grep-2.27/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 0.17
user 0.15
sys 0.02
+ grep-2.28/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 7.22
user 7.14
sys 0.07
+ grep-3.0/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 7.26
user 7.11
sys 0.14
+ grep-3.1/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 7.22
user 6.88
sys 0.33
+ grep-3.2/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 7.20
user 7.04
sys 0.15
+ grep-3.3/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 7.24
user 7.17
sys 0.07
+ grep-3.4/src/grep -E -v -m1 -f grep-patterns.txt /dev/null
real 7.13
user 6.49
sys 0.63

It seems to a lot of time is spent in dfa.c:replace().
It was added at d6df3873c7abc243683d0e8fccbfde4e76f23e53 in gnulib.