GNU bug report logs - #34951
[PATCH] grep: a kwset matcher not work in a grep matcher

Previous Next

Full log

View this message in rfc822 format

From: help-debbugs <at> gnu.org (GNU bug Tracking System)
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: tracker <at> debbugs.gnu.org
Subject: bug#34951: closed ([PATCH] grep: a kwset matcher not work in a
 grep matcher)
Date: Fri, 20 Dec 2019 03:42:02 +0000

[Message part 1 (text/plain, inline)]

Your message dated Thu, 19 Dec 2019 19:41:47 -0800
with message-id <3ff805f9-89dc-fb26-29c7-acf7f25ce895 <at> cs.ucla.edu>
and subject line Re: bug#34951: [PATCH] grep: a kwset matcher not work in a grep matcher
has caused the debbugs.gnu.org bug report #34951,
regarding [PATCH] grep: a kwset matcher not work in a grep matcher
to be marked as done.

(If you believe you have received this mail in error, please contact
help-debbugs <at> gnu.org.)


-- 
34951: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=34951
GNU Bug Tracking System
Contact help-debbugs <at> gnu.org with problems

[Message part 2 (message/rfc822, inline)]

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: <bug-grep <at> gnu.org>
Cc: bug-gnulib <at> gnu.org
Subject: [PATCH] grep: a kwset matcher not work in a grep matcher
Date: Sat, 23 Mar 2019 08:06:35 +0900

[Message part 3 (text/plain, inline)]

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

[0001-dfa-separate-parse-and-compile-phase.patch (text/plain, attachment)]

[0001-grep-a-kwset-matcher-not-work-in-a-grep-matcher.patch (text/plain, attachment)]

[Message part 6 (message/rfc822, inline)]

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>, 34951-done <at> debbugs.gnu.org
Subject: Re: bug#34951: [PATCH] grep: a kwset matcher not work in a grep
 matcher
Date: Thu, 19 Dec 2019 19:41:47 -0800

On 12/11/19 3:25 PM, Paul Eggert wrote:
> On 3/22/19 7:49 PM, Norihiro Tanaka wrote:
>> Missing a patch for dfa.  Re-send correct patch file.
> 
> Thanks, I installed the DFA-relevant parts of your proposed fix into Gnulib.
> (The grep parts still need doing.)

I finally got around to reviewing the grep parts, and installed them into 'grep'
master. Thanks again for the fix, and sorry about the delay. Closing the bug
report, as the original bug has been fixed (though we can still talk about what
name to give ptrdiff_t, in bug-gnulib perhaps).

I followed up with this NEWS entry:

  A performance bug has been fixed for patterns like '01.2' that
  cause grep to reorder tokens internally.
  [Bug#34951 introduced in grep 3.2]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.