Subject: bug#17448: closed (Re: bug#17448: [PATCH] grep: retry DFA superset after matched with multiple lines by it)

From: [email-masked] (GNU bug Tracking System)
Date: Fri, 09 May 2014 21:54:02 +0000

Your bug report

#17448: [PATCH] grep: retry DFA superset after matched with multiple lines by it

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].

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

Subject: Re: bug#17448: [PATCH] grep: retry DFA superset after matched with multiple lines by it
From: Paul Eggert <[email-masked]>
To: Norihiro Tanaka <[email-masked]>, [email-masked]
Date: Fri, 09 May 2014 14:52:58 -0700
List-Id: <debbugs-submit.debbugs.gnu.org>

Thanks, I installed that, along with the attached patch which improves 
it slightly by avoiding a test of the returned value of memrchr in a 
context where memrchr cannot return NULL, plus I redid the while-control 
to make it a bit clearer when the loop terminates.
From ad6ca9bb54ae2a9811c889c990ea67d67919a4f4 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Fri, 9 May 2014 14:48:47 -0700
Subject: [PATCH] grep: minor improvements to retry-DFA-superset patch

* src/dfasearch.c (EGexecute): Avoid unnecessary test in a context
where memrchr cannot return a null pointer.
---
 src/dfasearch.c | 24 ++++++++++--------------
 1 file changed, 10 insertions(+), 14 deletions(-)

diff --git a/src/dfasearch.c b/src/dfasearch.c
index 9fb7449..77b4e3e 100644
--- a/src/dfasearch.c
+++ b/src/dfasearch.c
@@ -284,23 +284,18 @@ EGexecute (char const *buf, size_t size, size_t *match_size,
           /* Try matching with the superset of DFA, if it's defined.  */
           if (superset && !exact_kwset_match)
             {
-              while (true)
+              /* Keep using the superset while it reports multiline
+                 potential matches; this is more likely to be fast
+                 than falling back to KWset would be.  */
+              while ((next_beg = dfaexec (superset, dfa_beg, (char *) end, 1,
+                                          &count, NULL))
+                     && next_beg != end
+                     && count != 0)
                 {
-                  next_beg = dfaexec (superset, dfa_beg, (char *) end, 1,
-                                      &count, NULL);
-                  /* If there's no match, or if we've matched the sentinel,
-                     we're done.  */
-                  if (next_beg == NULL || next_beg == end)
-                    break;
-
-                  if (count == 0)
-                    break;
+                  /* Try to match in just one line.  */
                   count = 0;
-
-                  /* If dfaexec may match in multiple lines, try to
-                     match in one line.  */
                   beg = memrchr (buf, eol, next_beg - buf);
-                  beg = beg ? beg + 1 : buf;
+                  beg++;
                   dfa_beg = beg;
                 }
               if (next_beg == NULL || next_beg == end)
@@ -310,6 +305,7 @@ EGexecute (char const *buf, size_t size, size_t *match_size,
               end = memchr (next_beg, eol, buflim - next_beg);
               end = end ? end + 1 : buflim;
             }
+
           /* Try matching with DFA.  */
           next_beg = dfaexec (dfa, dfa_beg, (char *) end, 0, &count, &backref);
 
-- 
1.9.0

Subject: [PATCH] grep: retry DFA superset after matched with multiple lines by it
From: Norihiro Tanaka <[email-masked]>
To: [email-masked]
Date: Fri, 09 May 2014 23:40:48 +0900
List-Id: <debbugs-submit.debbugs.gnu.org>

Currently, when matched with multiple lines by DFA superset, return to
KWset.  However, it won't be wrong probably, because if matches with
multiple lines by DFA superset, also matches with single line there with
high probability.  Further more, if return to KWset after matched with
multiple line by DFA superset, dfafast won't work effectively.

This patch changes to retry DFA superset immediately after matched with
multiple lines by it.

I confirmed the patch by following tests.

  $ yes abcdabc | head -50000000 >k
  $ env LC_ALL=C time -p src/grep '\(ab\)cd\1d' k

  before:
    real 3.48       user 3.41       sys 0.06

  after:
    real 2.14       user 2.07       sys 0.06

Norihiro
From fafb93db6c618e69ded15317bd953a98463d200f Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Fri, 9 May 2014 15:26:38 +0900
Subject: [PATCH] grep: retry DFA superset after matched with multiple lines by
 it

* src/dfasearch.c (EGexecute): Do it.
---
 src/dfasearch.c | 32 +++++++++++++++++++-------------
 1 file changed, 19 insertions(+), 13 deletions(-)

diff --git a/src/dfasearch.c b/src/dfasearch.c
index 4202666..9fb7449 100644
--- a/src/dfasearch.c
+++ b/src/dfasearch.c
@@ -284,26 +284,32 @@ EGexecute (char const *buf, size_t size, size_t *match_size,
           /* Try matching with the superset of DFA, if it's defined.  */
           if (superset && !exact_kwset_match)
             {
-              next_beg = dfaexec (superset, dfa_beg, (char *) end, 1,
-                                  &count, NULL);
-              /* If there's no match, or if we've matched the sentinel,
-                 we're done.  */
-              if (next_beg == NULL || next_beg == end)
-                continue;
-
-              /* Narrow down to the line we've found.  */
-              if (count != 0)
+              while (true)
                 {
+                  next_beg = dfaexec (superset, dfa_beg, (char *) end, 1,
+                                      &count, NULL);
+                  /* If there's no match, or if we've matched the sentinel,
+                     we're done.  */
+                  if (next_beg == NULL || next_beg == end)
+                    break;
+
+                  if (count == 0)
+                    break;
+                  count = 0;
+
                   /* If dfaexec may match in multiple lines, try to
                      match in one line.  */
-                  end = memrchr (buf, eol, next_beg - buf);
-                  end++;
-                  continue;
+                  beg = memrchr (buf, eol, next_beg - buf);
+                  beg = beg ? beg + 1 : buf;
+                  dfa_beg = beg;
                 }
+              if (next_beg == NULL || next_beg == end)
+                continue;
+
+              /* Narrow down to the line we've found.  */
               end = memchr (next_beg, eol, buflim - next_beg);
               end = end ? end + 1 : buflim;
             }
-
           /* Try matching with DFA.  */
           next_beg = dfaexec (dfa, dfa_beg, (char *) end, 0, &count, &backref);
 
-- 
1.9.2