Subject: bug#16966: [PATCH] grep: optimization with the superset of DFA

From: Norihiro Tanaka <[email-masked]>
Date: Fri, 04 Apr 2014 12:28:47 +0900

Norihiro Tanaka wrote:
> s0: The position set is none.
> s1: The position set is 1:a
> s2: The position set is 1:a 2:CSET
> s3: The position set is 2:CSET 3:b (accepted)
> s4: The position set is 2:CSET

Sorry, it was wrong yet.  It should be as follows.

s0: The position set is none.
s1: The position set is 1:a 2:CSET 3:b
s2: The position set is 1:a 2:CSET 3:b (accepted)

First of all, I noticed that the example is wrong, because if fixed
strings are included in the pattern, kwset is used for the pattern,
and dfahint() is called for each single line.

--
By the way, I compared two cases, which are CSET* and
CSET{1,mb_cur_max}.  I used `\(a\|z\)[x-y]\{10\}\(b\|z\)' as the pattern.
`[x-z]' is MBCSET in UTF-8 locale.

If replace MBCSET to CSET*, the pattern in the superset is
`\(a\|z\)\(CSET*\)\{10\}\(b\|z\)'.
If replace MBCSET to CSET{1,mb_cur_max}, the pattern in the superset is
`\(a\|z\)\(CSET\{1,6\}\)\{10\}\(b\|z\)'.

In order to simplify, use `\(a\|z\)\(.\{1,6\}\)\{10\}\(b\|z\)' in
POSIX locale for later.

Before testing, apply the patch attached on this mail, Set `DDEBUG' to
CPPFLAGS, and re-build.  It outputs more debugging information.

  $ yes `printf '%0100d\n'` | head -320 | \
      sed -e '1s/^0/a/; $s/0$/b/' | \
      env LANG=en_US.UTF-8 src/grep '\(a\|z\)[x-y]\{10\}\(b\|z\)' 2>debug1.log
  $ yes `printf '%0100d\n'` | head -320 | \
      sed -e '1s/^0/a/; $s/0$/b/' | \
      env LANG=C src/grep '\(a\|z\)\(.\{1,6\}\)\{10\}\(b\|z\)' 2>debug2.log

(`320' originates in the default size of a buffer.)

The formar is only built 3 states.
OTOH, the later is built 224 dfastates.
i.e. even if matched multi-lines, many states aren't necessarily built. 

Next, I checked performance for each case in worst text.
It's best in 10 times.

yes `printf '%0100d\n'` | head -2 | sed -e '1s/^0/a/; $s/0$/b/' >t
yes t | head -1000000 | xargs cat >u

time -p env LANG=C src/grep '\(a\|z\)\(.\{1,6\}\)\{10\}\(b\|z\)' u
    real 1.26       user 0.95       sys 0.28
time -p env LANG=en_US.UTF-8 src/grep '\(a\|z\)[x-y]\{10\}\(b\|z\)' u
    real 0.74       user 0.45       sys 0.27

Though, the later is fast, I like the former, because it's very simple.
the later is complicated, also needs to update nleaves and depth.

Norihiro
From df6da5d40a47abbc6e3451cb9fab7a8c9ede12cc Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Fri, 28 Mar 2014 19:27:00 -0700
Subject: [PATCH 1/3] dfa: improve port to freestanding DJGPP

Suggested by Aharon Robbins (Bug#17056).
* src/dfa.c (setlocale) [!LC_ALL]: Return NULL, not "C",
reverting part of a recent change.
(using_simple_locale): Return true if setlocale returns null.
---
 src/dfa.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index 4ed2189..b22fe97 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -37,7 +37,7 @@
 /* Gawk doesn't use Gnulib, so don't assume that setlocale and
    static_assert are present.  */
 #ifndef LC_ALL
-# define setlocale(category, locale) "C"
+# define setlocale(category, locale) NULL
 #endif
 #ifndef static_assert
 # define static_assert(cond, diagnostic) \
@@ -850,8 +850,9 @@ using_simple_locale (void)
       if (unibyte_c < 0)
         {
           char const *locale = setlocale (LC_ALL, NULL);
-          unibyte_c = (locale && (STREQ (locale, "C")
-                                  || STREQ (locale, "POSIX")));
+          unibyte_c = (!locale
+                       || STREQ (locale, "C")
+                       || STREQ (locale, "POSIX"));
         }
       return unibyte_c;
     }
-- 
1.9.1

From d80c9a5da2c5e04844ac39f8cdd45e6425b2dde6 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Tue, 1 Apr 2014 11:18:44 +0200
Subject: [PATCH 2/3] dfa: avoid re-building a state built previously

* src/dfa.c (dfaexec): Avoid to re-build a state built previously.
---
 src/dfa.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/src/dfa.c b/src/dfa.c
index b22fe97..b6fbd58 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -3537,7 +3537,8 @@ dfaexec (struct dfa *d, char const *begin, char *end,
 
       if (s >= 0)
         {
-          build_state (s, d);
+          if (!d->trans[s])
+            build_state (s, d);
           trans = d->trans;
           continue;
         }
-- 
1.9.1

From f18a096be8a0be2941f97111a3870e14a8abb613 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Sat, 22 Mar 2014 17:00:36 +0900
Subject: [PATCH 3/3] grep: print the detail of DFA states

* src/dfa.c (prtok): replace `%c' to `%02x' in format of printf().
(state_index): print detail of new state.
(dfastate) print detail of the process.
---
 src/dfa.c | 52 +++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 51 insertions(+), 1 deletion(-)

diff --git a/src/dfa.c b/src/dfa.c
index b6fbd58..fc4edcb 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -556,7 +556,7 @@ prtok (token t)
   else if (t < NOTCHAR)
     {
       int ch = t;
-      fprintf (stderr, "%c", ch);
+      fprintf (stderr, "0x%02x", ch);
     }
   else
     {
@@ -2155,6 +2155,28 @@ state_index (struct dfa *d, position_set const *s, int context)
         return i;
     }
 
+#ifdef DEBUG
+  fprintf (stderr, "new state %d:\n  position:", i);
+  for (j = 0; j < s->nelem; ++j)
+    {
+      fprintf (stderr, " %d:", s->elems[j].index);
+      prtok (d->tokens[s->elems[j].index]);
+    }
+  fprintf (stderr, "\n  context:");
+  if (context & CTX_ANY)
+    fprintf (stderr, " CTX_ANY");
+  else
+    {
+      if (context & CTX_NONE)
+        fprintf (stderr, " CTX_NONE");
+      if (context & CTX_NEWLINE)
+        fprintf (stderr, " CTX_LETTER");
+      if (context & CTX_NEWLINE)
+        fprintf (stderr, " CTX_NEWLINE");
+    }
+  fprintf (stderr, "\n");
+#endif
+
   /* We'll have to create a new state.  */
   REALLOC_IF_NECESSARY (d->states, d->salloc, d->sindex + 1);
   d->states[i].hash = hash;
@@ -2626,6 +2648,10 @@ dfastate (state_num s, struct dfa *d, state_num trans[])
   int next_isnt_1st_byte = 0;   /* Flag if we can't add state0.  */
   size_t i, j, k;
 
+#ifdef DEBUG
+  fprintf (stderr, "*** DFA state %d ***\n", s);
+#endif
+
   MALLOC (grps, NOTCHAR);
   MALLOC (labels, NOTCHAR);
 
@@ -2678,6 +2704,14 @@ dfastate (state_num s, struct dfa *d, state_num trans[])
             continue;
         }
 
+#ifdef DEBUG
+      fprintf (stderr, "position %d:", pos.index);
+      for (j = 0; j < NOTCHAR; j++)
+      if (tstbit (j,  matches))
+        fprintf (stderr, " 0x%02x", j);
+      fprintf (stderr, "\n");
+#endif
+
       for (j = 0; j < ngrps; ++j)
         {
           /* If matches contains a single character only, and the current
@@ -2836,6 +2870,22 @@ dfastate (state_num s, struct dfa *d, state_num trans[])
       else
         state_letter = state;
 
+#ifdef DEBUG
+      fprintf (stderr, "group %d:\n  nextpos :", i);
+      for (j = 0; j < grps[i].nelem; ++j)
+        {
+          fprintf (stderr, " %d:", grps[i].elems[j]);
+          prtok (d->tokens[grps[i].elems[j]]);
+        }
+      fprintf (stderr, "\n  follows :");
+      for (j = 0; j < follows.nelem; ++j)
+        {
+          fprintf (stderr, " %d:", follows.elems[j].index);
+          prtok (d->tokens[follows.elems[j].index]);
+        }
+      fprintf (stderr, "\n  nextstate: %d, %d, %d\n", state, state_newline, state_letter);
+#endif
+
       /* Set the transitions for each character in the current label.  */
       for (j = 0; j < CHARCLASS_INTS; ++j)
         for (k = 0; k < INTBITS; ++k)
-- 
1.9.1