Subject: bug#34951: closed (Re: bug#34951: [PATCH] grep: a kwset matcher not work in a grep matcher)

From: [email-masked] (GNU bug Tracking System)
Date: Fri, 20 Dec 2019 03:42:02 +0000

Your bug report

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

which was filed against the grep package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to [email-masked].

-- 
34951: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=34951
GNU Bug Tracking System
Contact [email-masked] with problems

Subject: Re: bug#34951: [PATCH] grep: a kwset matcher not work in a grep matcher
From: Paul Eggert <[email-masked]>
To: Norihiro Tanaka <[email-masked]>, [email-masked]
Date: Thu, 19 Dec 2019 19:41:47 -0800
List-Id: <debbugs-submit.debbugs.gnu.org>

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]

Subject: [PATCH] grep: a kwset matcher not work in a grep matcher
From: Norihiro Tanaka <[email-masked]>
To: <[email-masked]>
Cc: [email-masked]
Date: Sat, 23 Mar 2019 08:06:35 +0900
List-Id: <debbugs-submit.debbugs.gnu.org>

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
From fca6a4c3b9e0757637b7a2009ca8b9070a6874f5 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Sat, 23 Mar 2019 07:18:37 +0900
Subject: [PATCH] dfa: separate parse and compile phase

DFAMUST() must be called after parse and before tokens re-order which is
introduced in commit 5c7a0371823876cca7a1347fa09ca26bbbff0c98, but both are
executed in compilation phase.

* lib/dfa.c (dfaparse): Change it to global function.
(dfacomp): If first argument is NULL, skip parse.
* lib/dfa.h: (dfaparse): Add a prototype.
---
 src/dfasearch.c |    3 ++-
 1 files changed, 2 insertions(+), 1 deletions(-)

diff --git a/src/dfasearch.c b/src/dfasearch.c
index 3ebd25e..f3f889f 100644
--- a/src/dfasearch.c
+++ b/src/dfasearch.c
@@ -202,8 +202,9 @@ GEAcompile (char *pattern, size_t size, reg_syntax_t syntax_bits)
   else
     motif = NULL;
 
-  dfacomp (pattern, size, dc->dfa, 1);
+  dfaparse (pattern, size, dc->dfa);
   kwsmusts (dc);
+  dfacomp (NULL, 0, dc->dfa, 1);
 
   free (motif);
 
-- 
1.7.1

From 60d47e1d9a5af18eeb61719c7ac8c8ae097a06e4 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Sat, 23 Mar 2019 07:39:04 +0900
Subject: [PATCH] grep: a kwset matcher not work in a grep matcher

A kwset matcher is not built in a grep matcher after tokens re-order is
introduced in commit 5c7a0371823876cca7a1347fa09ca26bbbff0c98 in dfa.
Now DFAMUST() must be called after parse and before compile.

* src/dfasearch.c (GEAcompile): Build a kwset match before compile dfa.
---
 src/dfasearch.c |    3 ++-
 1 files changed, 2 insertions(+), 1 deletions(-)

diff --git a/src/dfasearch.c b/src/dfasearch.c
index 3ebd25e..f3f889f 100644
--- a/src/dfasearch.c
+++ b/src/dfasearch.c
@@ -202,8 +202,9 @@ GEAcompile (char *pattern, size_t size, reg_syntax_t syntax_bits)
   else
     motif = NULL;
 
-  dfacomp (pattern, size, dc->dfa, 1);
+  dfaparse (pattern, size, dc->dfa);
   kwsmusts (dc);
+  dfacomp (NULL, 0, dc->dfa, 1);
 
   free (motif);
 
-- 
1.7.1