How make grep walinh through FS by scanning breadth first instead of the usual depth
On 3/23/19, Norihiro Tanaka <nori...@kcn.ne.jp> wrote: > On Sat, 23 Mar 2019 08:06:35 +0900 > Norihiro Tanaka <nori...@kcn.ne.jp> wrote: > >> 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 > > Missing a patch for dfa. Re-send correct patch file. >
