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

[Norihiro Tanaka <noritnk@kcn.ne.jp>]

[-- Attachment #1: Type: text/plain, Size: 2670 bytes --]

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

[-- Attachment #2: 0001-dfa-separate-parse-and-compile-phase.patch --]
[-- Type: text/plain, Size: 1015 bytes --]

From fca6a4c3b9e0757637b7a2009ca8b9070a6874f5 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <noritnk@kcn.ne.jp>
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


[-- Attachment #3: 0001-grep-a-kwset-matcher-not-work-in-a-grep-matcher.patch --]
[-- Type: text/plain, Size: 975 bytes --]

From 60d47e1d9a5af18eeb61719c7ac8c8ae097a06e4 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <noritnk@kcn.ne.jp>
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