Re: bug#34951: [PATCH] grep: a kwset matcher not work in a grep matcher

[Budi <budikusasi@gmail.com>]

How make grep walking through FS by scanning breadth first instead of

On 3/23/19, Budi <budikusasi@gmail.com> wrote:
> How make grep walinh through FS by scanning breadth first instead of
> the usual depth
>
> On 3/23/19, Norihiro Tanaka <noritnk@kcn.ne.jp> wrote:
>> On Sat, 23 Mar 2019 08:06:35 +0900
>> Norihiro Tanaka <noritnk@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.
>>
>