Subject: bug#17576: closed (Re: [PATCH] dfa: speed-up at initial state)

From: [email-masked] (GNU bug Tracking System)
Date: Sun, 28 Sep 2014 04:02:03 +0000

Your bug report

#17576: [PATCH] dfa: speed-up at initial state

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

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

Subject: Re: [PATCH] dfa: speed-up at initial state
From: Paul Eggert <[email-masked]>
To: Norihiro Tanaka <[email-masked]>
Cc: [email-masked]
Date: Sat, 27 Sep 2014 21:01:14 -0700
List-Id: <debbugs-submit.debbugs.gnu.org>

Norihiro Tanaka wrote:
> The test case "k" is 50%
> faster and "l" is also about 16% faster with GCC 4.8.2 on my platform by
> two changes.

Thanks, I finally got around to looking at this and got similar performance 
results to yours.  That __attribute__((noinline)) bothers me, though, as it's 
not portable and is a bit inelegant.  I figured out a different way to avoid the 
inlining, and tweaked the commentary a bit, and so installed the attached 
additional patch after installing your patches.
From ac757a34d6b93942732d1026c1e4e3c67f882d86 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Sat, 27 Sep 2014 20:55:13 -0700
Subject: [PATCH] dfa: minor tweaks, mostly to remove __attribute__
 ((noinline))

That attribute isn't portable, and I found a way to get similar
performance with standard C features.
* NEWS: Document the recently-installed performance improvement.
* src/dfa.c (struct dfa): New member dfaexec.
(dfaexec_main): Remove unnecessary 'const'.
(dfaexec_mb, dfaexec_sb): Remove __attribute__ ((noinline));
no longer needed.
(dfaexec): Use new dfaexec member.
(dfainit, dfaoptimize, dfassbuild): Initialize it.
---
 NEWS      |  3 +++
 src/dfa.c | 32 +++++++++++++++++++++++---------
 2 files changed, 26 insertions(+), 9 deletions(-)

diff --git a/NEWS b/NEWS
index 5bc89c0..a146e9e 100644
--- a/NEWS
+++ b/NEWS
@@ -7,6 +7,9 @@ GNU grep NEWS                                    -*- outline -*-
   Performance has been greatly improved for searching files containing
   holes, on platforms where lseek's SEEK_DATA flag works efficiently.
 
+  Performance has improved for rejecting data that cannot match even
+  the first part of a nontrivial pattern.
+
   Performance has improved for very long strings in patterns.
 
   If a file contains data improperly encoded for the current locale,
diff --git a/src/dfa.c b/src/dfa.c
index ff23c07..4f45fff 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -342,6 +342,9 @@ struct dfa
   token utf8_anychar_classes[5]; /* To lower ANYCHAR in UTF-8 locales.  */
   mbstate_t mbs;		/* Multibyte conversion state.  */
 
+  /* dfaexec implementation.  */
+  char *(*dfaexec) (struct dfa *, char const *, char *, int, size_t *, int *);
+
   /* The following are valid only if MB_CUR_MAX > 1.  */
 
   /* The value of multibyte_prop[i] is defined by following rule.
@@ -3266,10 +3269,14 @@ skip_remains_mb (struct dfa *d, unsigned char const *p,
    If COUNT is non-NULL, increment *COUNT once for each newline processed.
    Finally, if BACKREF is non-NULL set *BACKREF to indicate whether we
    encountered a back-reference (1) or not (0).  The caller may use this
-   to decide whether to fall back on a backtracking matcher.  */
+   to decide whether to fall back on a backtracking matcher.
+
+   If MULTIBYTE, the input consists of multibyte characters and/or
+   encoding-error bytes.  Otherwise, the input consists of single-byte
+   characters.  */
 static inline char *
 dfaexec_main (struct dfa *d, char const *begin, char *end,
-             int allow_nl, size_t *count, int *backref, bool const multibyte)
+             int allow_nl, size_t *count, int *backref, bool multibyte)
 {
   state_num s, s1;              /* Current state.  */
   unsigned char const *p, *mbp; /* Current input character.  */
@@ -3432,27 +3439,31 @@ dfaexec_main (struct dfa *d, char const *begin, char *end,
   return (char *) p;
 }
 
-static char *__attribute__((noinline))
+/* Specialized versions of dfaexec_main for multibyte and single-byte
+   cases.  This is for performance.  */
+
+static char *
 dfaexec_mb (struct dfa *d, char const *begin, char *end,
-           int allow_nl, size_t *count, int *backref)
+            int allow_nl, size_t *count, int *backref)
 {
   return dfaexec_main (d, begin, end, allow_nl, count, backref, true);
 }
 
-static char *__attribute__((noinline))
+static char *
 dfaexec_sb (struct dfa *d, char const *begin, char *end,
-           int allow_nl, size_t *count, int *backref)
+            int allow_nl, size_t *count, int *backref)
 {
   return dfaexec_main (d, begin, end, allow_nl, count, backref, false);
 }
 
+/* Like dfaexec_main (D, BEGIN, END, ALLOW_NL, COUNT, BACKREF, D->multibyte),
+   but faster.  */
+
 char *
 dfaexec (struct dfa *d, char const *begin, char *end,
          int allow_nl, size_t *count, int *backref)
 {
-  return (d->multibyte
-    ? dfaexec_mb (d, begin, end, allow_nl, count, backref)
-    : dfaexec_sb (d, begin, end, allow_nl, count, backref));
+  return d->dfaexec (d, begin, end, allow_nl, count, backref);
 }
 
 struct dfa *
@@ -3504,6 +3515,7 @@ dfainit (struct dfa *d)
 {
   memset (d, 0, sizeof *d);
   d->multibyte = MB_CUR_MAX > 1;
+  d->dfaexec = d->multibyte ? dfaexec_mb : dfaexec_sb;
   d->fast = !d->multibyte;
 }
 
@@ -3544,6 +3556,7 @@ dfaoptimize (struct dfa *d)
 
   free_mbdata (d);
   d->multibyte = false;
+  d->dfaexec = dfaexec_sb;
 }
 
 static void
@@ -3557,6 +3570,7 @@ dfassbuild (struct dfa *d)
 
   *sup = *d;
   sup->multibyte = false;
+  sup->dfaexec = dfaexec_sb;
   sup->multibyte_prop = NULL;
   sup->mbcsets = NULL;
   sup->superset = NULL;
-- 
1.9.3

Subject: [PATCH] dfa: speed-up at initial state
From: Norihiro Tanaka <[email-masked]>
To: [email-masked]
Date: Sat, 24 May 2014 12:31:37 +0900
List-Id: <debbugs-submit.debbugs.gnu.org>

Thanks to Jim and for the new release.  Let's just start with, for next
release I want to add further improvement to it.

In dfaexec, DFA state is always 0 until have found potential match.  So
we can improve matching there by continuing to use the transition table
without replacing it.

I tested the patch, and got about 3x speed-up.

$ yes j | head -10000000 >k
$ env LC_ALL=C time -p src/grep '\(a\|b\)' k
  Before: real 1.12   user 1.06   sys 0.04
  After : real 0.39   user 0.34   sys 0.04

I also tested for non-utf8 multibyte locale.
$ env LC_ALL=ja_JP.eucJP time -p src/grep '\(a\|b\)' k
  Before: real 1.41   user 1.35   sys 0.05
  After : real 0.38   user 0.32   sys 0.06

By the way, below on grep 2.18 (non-patch). (^_^)

$ env LANG=ja_JP.eucJP time -p src/grep '\(a\|b\)' k
          real 12.00  user 11.86  sys 0.13
From 6918bc2493ff7ae21c50a3b4d358ae3028374a09 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Tue, 13 May 2014 10:30:21 +0900
Subject: [PATCH] dfa: speed-up at initial state

DFA state is always 0 until have found potential match.  So we improve
matching there by continuing to use the transition table.

* src/dfa.c (skip_remains_mb): New function.
(dfaexec): Speed-up at initial state.
---
 src/dfa.c | 54 +++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 35 insertions(+), 19 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index 8ff29d0..1d73105 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -3250,6 +3250,24 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp,
   return s1;
 }
 
+/* The initial state may encounter a byte which is not a single byte character
+   nor the first byte of a multibyte character.  But it is incorrect for the
+   initial state to accept such a byte.  For example, in Shift JIS the regular
+   expression "\\" accepts the codepoint 0x5c, but should not accept the second
+   byte of the codepoint 0x815c.  Then the initial state must skip the bytes
+   that are not a single byte character nor the first byte of a multibyte
+   character.  */
+static unsigned char const *
+skip_remains_mb (struct dfa *d, unsigned char const *p,
+                 unsigned char const *mbp, char const *end)
+{
+  wint_t wc;
+  while (mbp < p)
+    mbp += mbs_to_wchar (&wc, (char const *) mbp,
+                         end - (char const *) mbp, d);
+  return mbp;
+}
+
 /* Search through a buffer looking for a match to the given struct dfa.
    Find the first occurrence of a string matching the regexp in the
    buffer, and the shortest possible version thereof.  Return a pointer to
@@ -3303,27 +3321,18 @@ dfaexec (struct dfa *d, char const *begin, char *end,
 
               if (s == 0)
                 {
-                  /* The initial state may encounter a byte which is not
-                     a single byte character nor the first byte of a
-                     multibyte character.  But it is incorrect for the
-                     initial state to accept such a byte.  For example,
-                     in Shift JIS the regular expression "\\" accepts
-                     the codepoint 0x5c, but should not accept the second
-                     byte of the codepoint 0x815c.  Then the initial
-                     state must skip the bytes that are not a single
-                     byte character nor the first byte of a multibyte
-                     character.  */
-                  wint_t wc;
-                  while (mbp < p)
-                    mbp += mbs_to_wchar (&wc, (char const *) mbp,
-                                         end - (char const *) mbp, d);
-                  p = mbp;
-
-                  if ((char *) p > end)
+                  if (d->states[s].mbps.nelem == 0)
                     {
-                      p = NULL;
-                      goto done;
+                      do
+                        {
+                          while (t[*p] == 0)
+                            p++;
+                          p = mbp = skip_remains_mb (d, p, mbp, end);
+                        }
+                      while (t[*p] == 0);
                     }
+                  else
+                    p = mbp = skip_remains_mb (d, p, mbp, end);
                 }
 
               if (d->states[s].mbps.nelem == 0)
@@ -3351,6 +3360,13 @@ dfaexec (struct dfa *d, char const *begin, char *end,
         }
       else
         {
+          if (s == 0 && (t = trans[s]) != NULL)
+            {
+              while (t[*p] == 0)
+                p++;
+              s = t[*p++];
+            }
+
           while ((t = trans[s]) != NULL)
             {
               s1 = t[*p++];
-- 
1.9.3