A kwset matcher is not built in a grep matcher after token re-order is introduced in commit 5c7a0371823876cca7a1347fa09ca26bbbff0c98 in dfa. It caused performance degradation in some typical cases. This bug is introduced in grep-3.2. DFAMUST() does not work if tokens which are parsed in dfa matcher are re-ordered. Therefore, change as it is called after parse and before tokens re-order. BTW, this change does not affect programs that do not use DFAMUST(), such as sed or gawk. $ yes $(printf '%040d' 0) | head -10000000 >inp $ grep-2.2/src/grep 01.2 inp real 1.61 user 1.53 sys 0.07 $ grep-2.3/src/grep 01.2 inp real 1.57 user 1.48 sys 0.08 $ grep-2.4/src/grep 01.2 inp real 1.50 user 1.44 sys 0.05 $ grep-2.4.1/src/grep 01.2 inp real 1.53 user 1.48 sys 0.05 $ grep-2.4.2/src/grep 01.2 inp real 1.52 user 1.47 sys 0.04 $ grep-2.5.4/src/grep 01.2 inp real 1.53 user 1.47 sys 0.05 $ grep-2.6/src/grep 01.2 inp real 1.51 user 1.47 sys 0.04 $ grep-2.6.1/src/grep 01.2 inp real 1.50 user 1.44 sys 0.05 $ grep-2.6.2/src/grep 01.2 inp real 1.52 user 1.46 sys 0.05 $ grep-2.6.3/src/grep 01.2 inp real 1.52 user 1.47 sys 0.05 $ grep-2.7/src/grep 01.2 inp real 1.53 user 1.49 sys 0.04 $ grep-2.8/src/grep 01.2 inp real 1.52 user 1.46 sys 0.05 $ grep-2.9/src/grep 01.2 inp real 1.54 user 1.50 sys 0.04 $ grep-2.10/src/grep 01.2 inp real 1.51 user 1.46 sys 0.05 $ grep-2.11/src/grep 01.2 inp real 1.53 user 1.48 sys 0.05 $ grep-2.12/src/grep 01.2 inp real 1.51 user 1.47 sys 0.03 $ grep-2.13/src/grep 01.2 inp real 1.52 user 1.47 sys 0.03 $ grep-2.14/src/grep 01.2 inp real 1.52 user 1.47 sys 0.04 $ grep-2.15/src/grep 01.2 inp real 1.55 user 1.49 sys 0.05 $ grep-2.16/src/grep 01.2 inp real 1.53 user 1.48 sys 0.04 $ grep-2.17/src/grep 01.2 inp real 1.53 user 1.48 sys 0.05 $ grep-2.18/src/grep 01.2 inp real 1.51 user 1.44 sys 0.06 $ grep-2.19/src/grep 01.2 inp real 0.06 user 0.02 sys 0.04 $ grep-2.20/src/grep 01.2 inp real 0.07 user 0.01 sys 0.05 $ grep-2.21/src/grep 01.2 inp real 0.06 user 0.02 sys 0.04 $ grep-2.22/src/grep 01.2 inp real 0.06 user 0.01 sys 0.05 $ grep-2.23/src/grep 01.2 inp real 0.09 user 0.04 sys 0.05 $ grep-2.24/src/grep 01.2 inp real 0.09 user 0.04 sys 0.04 $ grep-2.25/src/grep 01.2 inp real 0.09 user 0.05 sys 0.04 $ grep-2.26/src/grep 01.2 inp real 0.09 user 0.04 sys 0.05 $ grep-2.27/src/grep 01.2 inp real 0.09 user 0.04 sys 0.04 $ grep-2.28/src/grep 01.2 inp real 0.09 user 0.04 sys 0.04 $ grep-3.0/src/grep 01.2 inp real 0.09 user 0.04 sys 0.04 $ grep-3.1/src/grep 01.2 inp real 0.11 user 0.05 sys 0.06 $ grep-3.2/src/grep 01.2 inp real 0.37 user 0.32 sys 0.04 $ grep-3.3/src/grep 01.2 inp real 0.29 user 0.25 sys 0.04 Thanks, Norihiro