Subject: bug#17013: closed (Re: bug#17013: [PATCH] grep: optimization by using the Galil rule for Boyer-Moore algorithm in KWSet)

From: [email-masked] (GNU bug Tracking System)
Date: Tue, 08 Apr 2014 02:57:03 +0000

Your bug report

#17013: [PATCH] grep: optimization by using the Galil rule for Boyer-Moore algorithm in KWSet

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

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

Subject: Re: bug#17013: [PATCH] grep: optimization by using the Galil rule for Boyer-Moore algorithm in KWSet
From: Paul Eggert <[email-masked]>
To: Norihiro Tanaka <[email-masked]>, [email-masked]
Date: Mon, 07 Apr 2014 19:56:29 -0700
List-Id: <debbugs-submit.debbugs.gnu.org>

Norihiro Tanaka wrote:
> In second patch, I changed so that Boyer-Moore algorithm could be used
> also to case-insensitive matching if MB_CUR_MAX == 1.

Thanks, I merged this patch into the savannah git master (attachment 1), 
applied a fixup patch for clarity and to fix some minor style issues 
(attachment 2), and fixed some longstanding kwset memory-allocation 
infelicities mostly having to do with unecessary code (attachment 3).
From ad03d4eb22be1b907221af78f4a3b4bcd85e1fc2 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Sat, 15 Mar 2014 14:41:52 +0900
Subject: [PATCH 1/3] grep: use the Galil rule for Boyer-Moore algorithm in
 KWSet

The Boyer-Moore algorithm is O(m*n), which means it may be much
slower than the DFA.  Its Galil rule variant is O(n) and increases
efficiency in the typical case; it skips sections that are known
to match and does not compare more than once for a position in the text.
To use the Galil rule, look for the delta2 shift at each position
from the trie instead of the 'mind2' value.
* src/kwset.c (struct kwset): Replace member 'mind2' with 'shift'.
(kwsprep): Look for the delta2 shift.
(bmexec): Use it.
---
 src/kwset.c | 214 ++++++++++++++++++++++++++++++++++++------------------------
 1 file changed, 127 insertions(+), 87 deletions(-)

diff --git a/src/kwset.c b/src/kwset.c
index 410e046..e0bf6b2 100644
--- a/src/kwset.c
+++ b/src/kwset.c
@@ -83,7 +83,7 @@ struct kwset
   unsigned char delta[NCHAR];	/* Delta table for rapid search. */
   struct trie *next[NCHAR];	/* Table of children of the root. */
   char *target;			/* Target string if there's only one. */
-  int mind2;			/* Used in Boyer-Moore search for one string. */
+  int *shift;			/* Used in Boyer-Moore search for one string. */
   char const *trans;		/* Character translation table. */
 };
 
@@ -397,12 +397,70 @@ kwsprep (kwset_t kws)
      node at which an outgoing edge is labeled by that character. */
   memset(delta, kwset->mind < UCHAR_MAX ? kwset->mind : UCHAR_MAX, NCHAR);
 
+  struct trie *fail;
+  struct trie *last, *next[NCHAR];
+
+  /* Traverse the nodes of the trie in level order, simultaneously
+     computing the delta table, failure function, and shift function. */
+  for (curr = last = kwset->trie; curr; curr = curr->next)
+    {
+      /* Enqueue the immediate descendants in the level order queue. */
+      enqueue(curr->links, &last);
+
+      curr->shift = kwset->mind;
+      curr->maxshift = kwset->mind;
+
+      /* Update the delta table for the descendants of this node. */
+      treedelta(curr->links, curr->depth, delta);
+
+      /* Compute the failure function for the descendants of this node.  */
+      treefails(curr->links, curr->fail, kwset->trie);
+
+      /* Update the shifts at each node in the current node's chain
+         of fails back to the root. */
+      for (fail = curr->fail; fail; fail = fail->fail)
+        {
+          /* If the current node has some outgoing edge that the fail
+             doesn't, then the shift at the fail should be no larger
+             than the difference of their depths. */
+          if (!hasevery(fail->links, curr->links))
+            if (curr->depth - fail->depth < fail->shift)
+              fail->shift = curr->depth - fail->depth;
+
+          /* If the current node is accepting then the shift at the
+             fail and its descendants should be no larger than the
+             difference of their depths. */
+          if (curr->accepting && fail->maxshift > curr->depth - fail->depth)
+            fail->maxshift = curr->depth - fail->depth;
+        }
+    }
+
+  /* Traverse the trie in level order again, fixing up all nodes whose
+     shift exceeds their inherited maxshift. */
+  for (curr = kwset->trie->next; curr; curr = curr->next)
+    {
+      if (curr->maxshift > curr->parent->maxshift)
+        curr->maxshift = curr->parent->maxshift;
+      if (curr->shift > curr->maxshift)
+        curr->shift = curr->maxshift;
+    }
+
+  /* Create a vector, indexed by character code, of the outgoing links
+     from the root node. */
+  for (i = 0; i < NCHAR; ++i)
+    next[i] = NULL;
+  treenext(kwset->trie->links, next);
+
+  if ((trans = kwset->trans) != NULL)
+    for (i = 0; i < NCHAR; ++i)
+      kwset->next[i] = next[U(trans[i])];
+  else
+    memcpy(kwset->next, next, NCHAR * sizeof(struct trie *));
+
   /* Check if we can use the simple boyer-moore algorithm, instead
      of the hairy commentz-walter algorithm. */
   if (kwset->words == 1 && kwset->trans == NULL)
     {
-      char c;
-
       /* Looking for just one string.  Extract it from the trie. */
       kwset->target = obstack_alloc(&kwset->obstack, kwset->mind);
       if (!kwset->target)
@@ -410,80 +468,22 @@ kwsprep (kwset_t kws)
       for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i)
         {
           kwset->target[i] = curr->links->label;
-          curr = curr->links->trie;
+          curr = curr->next;
         }
-      /* Build the Boyer Moore delta.  Boy that's easy compared to CW. */
-      for (i = 0; i < kwset->mind; ++i)
-        delta[U(kwset->target[i])] = kwset->mind - (i + 1);
-      /* Find the minimal delta2 shift that we might make after
-         a backwards match has failed. */
-      c = kwset->target[kwset->mind - 1];
-      for (i = kwset->mind - 2; i >= 0; --i)
-        if (kwset->target[i] == c)
-          break;
-      kwset->mind2 = kwset->mind - (i + 1);
-    }
-  else
-    {
-      struct trie *fail;
-      struct trie *last, *next[NCHAR];
-
-      /* Traverse the nodes of the trie in level order, simultaneously
-         computing the delta table, failure function, and shift function. */
-      for (curr = last = kwset->trie; curr; curr = curr->next)
+      /* Looking for the delta2 shift that we might make after a
+         backwards match has failed.  Extract it from the trie. */
+      if (kwset->mind > 1)
         {
-          /* Enqueue the immediate descendants in the level order queue. */
-          enqueue(curr->links, &last);
-
-          curr->shift = kwset->mind;
-          curr->maxshift = kwset->mind;
-
-          /* Update the delta table for the descendants of this node. */
-          treedelta(curr->links, curr->depth, delta);
-
-          /* Compute the failure function for the descendants of this node.  */
-          treefails(curr->links, curr->fail, kwset->trie);
-
-          /* Update the shifts at each node in the current node's chain
-             of fails back to the root. */
-          for (fail = curr->fail; fail; fail = fail->fail)
+          kwset->shift = obstack_alloc(&kwset->obstack,
+                                       sizeof (*kwset->shift) * (kwset->mind - 1));
+          if (!kwset->shift)
+            return _("memory exhausted");
+          for (i = 0, curr = kwset->trie->next; i < kwset->mind - 1; ++i)
             {
-              /* If the current node has some outgoing edge that the fail
-                 doesn't, then the shift at the fail should be no larger
-                 than the difference of their depths. */
-              if (!hasevery(fail->links, curr->links))
-                if (curr->depth - fail->depth < fail->shift)
-                  fail->shift = curr->depth - fail->depth;
-
-              /* If the current node is accepting then the shift at the
-                 fail and its descendants should be no larger than the
-                 difference of their depths. */
-              if (curr->accepting && fail->maxshift > curr->depth - fail->depth)
-                fail->maxshift = curr->depth - fail->depth;
+              kwset->shift[i] = curr->shift;
+              curr = curr->next;
             }
         }
-
-      /* Traverse the trie in level order again, fixing up all nodes whose
-         shift exceeds their inherited maxshift. */
-      for (curr = kwset->trie->next; curr; curr = curr->next)
-        {
-          if (curr->maxshift > curr->parent->maxshift)
-            curr->maxshift = curr->parent->maxshift;
-          if (curr->shift > curr->maxshift)
-            curr->shift = curr->maxshift;
-        }
-
-      /* Create a vector, indexed by character code, of the outgoing links
-         from the root node. */
-      for (i = 0; i < NCHAR; ++i)
-        next[i] = NULL;
-      treenext(kwset->trie->links, next);
-
-      if ((trans = kwset->trans) != NULL)
-        for (i = 0; i < NCHAR; ++i)
-          kwset->next[i] = next[U(trans[i])];
-      else
-        memcpy(kwset->next, next, NCHAR * sizeof(struct trie *));
     }
 
   /* Fix things up for any translation table. */
@@ -503,7 +503,8 @@ bmexec (kwset_t kws, char const *text, size_t size)
   struct kwset const *kwset;
   unsigned char const *d1;
   char const *ep, *sp, *tp;
-  int d, gc, i, len, md2;
+  int d, i, len, skip;
+  char gc1, gc2;
 
   kwset = (struct kwset const *) kws;
   len = kwset->mind;
@@ -520,9 +521,10 @@ bmexec (kwset_t kws, char const *text, size_t size)
 
   d1 = kwset->delta;
   sp = kwset->target + len;
-  gc = U(sp[-2]);
-  md2 = kwset->mind2;
+  gc1 = sp[-1];
+  gc2 = sp[-2];
   tp = text + len;
+  skip = 0;
 
   /* Significance of 12: 1 (initial offset) + 10 (skip loop) + 1 (md2). */
   if (size > 12 * len)
@@ -550,14 +552,33 @@ bmexec (kwset_t kws, char const *text, size_t size)
           }
         break;
       found:
-        if (U(tp[-2]) == gc)
+        d = len;
+        while (1)
           {
-            for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)
-              ;
-            if (i > len)
-              return tp - len - text;
+            if (tp[-2] == gc2)
+              {
+                for (i = 3; i <= d && tp[-i] == sp[-i]; ++i)
+                  ;
+                if (i > d)
+                  {
+                    for (i = d + skip + 1; i <= len && tp[-i] == sp[-i]; ++i)
+                      ;
+                    if (i > len)
+                      return tp - len - text;
+                  }
+                d = kwset->shift[i - 2]; tp += d;
+                if (tp > ep || tp[-1] != gc1)
+                  break;
+                skip = i - 1;
+              }
+            else
+              {
+                d = kwset->shift[0]; tp += d;
+                if (tp > ep || tp[-1] != gc1)
+                  break;
+                skip = 1;
+              }
           }
-        tp += md2;
       }
 
   /* Now we have only a few characters left to search.  We
@@ -569,14 +590,33 @@ bmexec (kwset_t kws, char const *text, size_t size)
       d = d1[U((tp += d)[-1])];
       if (d != 0)
         continue;
-      if (U(tp[-2]) == gc)
+      d = len;
+      while (1)
         {
-          for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)
-            ;
-          if (i > len)
-            return tp - len - text;
+          if (tp[-2] == gc2)
+            {
+              for (i = 3; i <= d && tp[-i] == sp[-i]; ++i)
+                ;
+              if (i > d)
+                {
+                  for (i = d + skip + 1; i <= len && tp[-i] == sp[-i]; ++i)
+                    ;
+                  if (i > len)
+                    return tp - len - text;
+                }
+              d = kwset->shift[i - 2]; tp += d;
+              if (tp > ep || tp[-1] != gc1)
+                break;
+              skip = i - 1;
+            }
+          else
+            {
+              d = kwset->shift[0]; tp += d;
+              if (tp > ep || tp[-1] != gc1)
+                break;
+              skip = 1;
+            }
         }
-      d = md2;
     }
 
   return -1;
-- 
1.9.0

From 6546f25525f2912c0733e1e19e4e38e410df28b0 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Mon, 7 Apr 2014 12:18:33 -0700
Subject: [PATCH 2/3] grep: minor cleanups for Galil speedups

* src/kwset.c: Update citations.
Include stdbool.h.
(kwsincr, kwsprep): Clarify by using C99 decls after statements.
(kwsprep): Clarify by using MIN.  Avoid a couple of buffer copies
when !TRANS.
(bmexec): Use bool for boolean.  Prefer "continue;" to ";".
---
 src/kwset.c | 121 +++++++++++++++++++++++++++++-------------------------------
 1 file changed, 59 insertions(+), 62 deletions(-)

diff --git a/src/kwset.c b/src/kwset.c
index e0bf6b2..6c07249 100644
--- a/src/kwset.c
+++ b/src/kwset.c
@@ -23,13 +23,16 @@
 
 /* The algorithm implemented by these routines bears a startling resemblance
    to one discovered by Beate Commentz-Walter, although it is not identical.
-   See "A String Matching Algorithm Fast on the Average," Technical Report,
-   IBM-Germany, Scientific Center Heidelberg, Tiergartenstrasse 15, D-6900
-   Heidelberg, Germany.  See also Aho, A.V., and M. Corasick, "Efficient
-   String Matching:  An Aid to Bibliographic Search," CACM June 1975,
-   Vol. 18, No. 6, which describes the failure function used below. */
+   See: Commentz-Walter B. A string matching algorithm fast on the average.
+   Lecture Notes in Computer Science 71 (1979), 118-32
+   <http://dx.doi.org/10.1007/3-540-09510-1_10>.
+   See also: Aho AV, Corasick MJ. Efficient string matching: an aid to
+   bibliographic search. CACM 18, 6 (1975), 333-40
+   <http://dx.doi.org/10.1145/360825.360855>, which describes the
+   failure function used below. */
 
 #include <config.h>
+#include <stdbool.h>
 #include <sys/types.h>
 #include "system.h"
 #include "kwset.h"
@@ -131,32 +134,28 @@ kwsalloc (char const *trans)
 const char *
 kwsincr (kwset_t kws, char const *text, size_t len)
 {
-  struct kwset *kwset;
-  struct trie *trie;
-  unsigned char label;
-  struct tree *link;
-  int depth;
-  struct tree *links[DEPTH_SIZE];
-  enum { L, R } dirs[DEPTH_SIZE];
-  struct tree *t, *r, *l, *rl, *lr;
+  struct kwset *kwset = kws;
+  struct trie *trie = kwset->trie;
+  char const *trans = kwset->trans;
 
-  kwset = (struct kwset *) kws;
-  trie = kwset->trie;
   text += len;
 
   /* Descend the trie (built of reversed keywords) character-by-character,
      installing new nodes when necessary. */
   while (len--)
     {
-      label = kwset->trans ? kwset->trans[U(*--text)] : *--text;
+      unsigned char uc = *--text;
+      unsigned char label = trans ? trans[uc] : uc;
 
       /* Descend the tree of outgoing links for this trie node,
          looking for the current character and keeping track
          of the path followed. */
-      link = trie->links;
+      struct tree *link = trie->links;
+      struct tree *links[DEPTH_SIZE];
+      enum { L, R } dirs[DEPTH_SIZE];
       links[0] = (struct tree *) &trie->links;
       dirs[0] = L;
-      depth = 1;
+      int depth = 1;
 
       while (link && label != link->label)
         {
@@ -215,6 +214,8 @@ kwsincr (kwset_t kws, char const *text, size_t len)
           if (depth && ((dirs[depth] == L && --links[depth]->balance)
                         || (dirs[depth] == R && ++links[depth]->balance)))
             {
+              struct tree *t, *r, *l, *rl, *lr;
+
               switch (links[depth]->balance)
                 {
                 case (char) -2:
@@ -384,59 +385,56 @@ treenext (struct tree const *tree, struct trie *next[])
 const char *
 kwsprep (kwset_t kws)
 {
-  struct kwset *kwset;
+  struct kwset *kwset = kws;
+  char const *trans = kwset->trans;
   int i;
-  struct trie *curr;
-  char const *trans;
-  unsigned char delta[NCHAR];
-
-  kwset = (struct kwset *) kws;
+  unsigned char deltabuf[NCHAR];
+  unsigned char *delta = trans ? deltabuf : kwset->delta;
 
   /* Initial values for the delta table; will be changed later.  The
      delta entry for a given character is the smallest depth of any
      node at which an outgoing edge is labeled by that character. */
-  memset(delta, kwset->mind < UCHAR_MAX ? kwset->mind : UCHAR_MAX, NCHAR);
-
-  struct trie *fail;
-  struct trie *last, *next[NCHAR];
+  memset (delta, MIN (kwset->mind, UCHAR_MAX), sizeof deltabuf);
 
   /* Traverse the nodes of the trie in level order, simultaneously
-     computing the delta table, failure function, and shift function. */
+     computing the delta table, failure function, and shift function.  */
+  struct trie *curr, *last;
   for (curr = last = kwset->trie; curr; curr = curr->next)
     {
-      /* Enqueue the immediate descendants in the level order queue. */
-      enqueue(curr->links, &last);
+      /* Enqueue the immediate descendants in the level order queue.  */
+      enqueue (curr->links, &last);
 
       curr->shift = kwset->mind;
       curr->maxshift = kwset->mind;
 
-      /* Update the delta table for the descendants of this node. */
-      treedelta(curr->links, curr->depth, delta);
+      /* Update the delta table for the descendants of this node.  */
+      treedelta (curr->links, curr->depth, delta);
 
       /* Compute the failure function for the descendants of this node.  */
-      treefails(curr->links, curr->fail, kwset->trie);
+      treefails (curr->links, curr->fail, kwset->trie);
 
       /* Update the shifts at each node in the current node's chain
-         of fails back to the root. */
+         of fails back to the root.  */
+      struct trie *fail;
       for (fail = curr->fail; fail; fail = fail->fail)
         {
           /* If the current node has some outgoing edge that the fail
              doesn't, then the shift at the fail should be no larger
-             than the difference of their depths. */
-          if (!hasevery(fail->links, curr->links))
+             than the difference of their depths.  */
+          if (!hasevery (fail->links, curr->links))
             if (curr->depth - fail->depth < fail->shift)
               fail->shift = curr->depth - fail->depth;
 
           /* If the current node is accepting then the shift at the
              fail and its descendants should be no larger than the
-             difference of their depths. */
+             difference of their depths.  */
           if (curr->accepting && fail->maxshift > curr->depth - fail->depth)
             fail->maxshift = curr->depth - fail->depth;
         }
     }
 
   /* Traverse the trie in level order again, fixing up all nodes whose
-     shift exceeds their inherited maxshift. */
+     shift exceeds their inherited maxshift.  */
   for (curr = kwset->trie->next; curr; curr = curr->next)
     {
       if (curr->maxshift > curr->parent->maxshift)
@@ -446,20 +444,18 @@ kwsprep (kwset_t kws)
     }
 
   /* Create a vector, indexed by character code, of the outgoing links
-     from the root node. */
-  for (i = 0; i < NCHAR; ++i)
-    next[i] = NULL;
-  treenext(kwset->trie->links, next);
-
-  if ((trans = kwset->trans) != NULL)
+     from the root node.  */
+  struct trie *nextbuf[NCHAR];
+  struct trie **next = trans ? nextbuf : kwset->next;
+  memset (next, 0, sizeof nextbuf);
+  treenext (kwset->trie->links, next);
+  if (trans)
     for (i = 0; i < NCHAR; ++i)
       kwset->next[i] = next[U(trans[i])];
-  else
-    memcpy(kwset->next, next, NCHAR * sizeof(struct trie *));
 
   /* Check if we can use the simple boyer-moore algorithm, instead
      of the hairy commentz-walter algorithm. */
-  if (kwset->words == 1 && kwset->trans == NULL)
+  if (!trans && kwset->words == 1)
     {
       /* Looking for just one string.  Extract it from the trie. */
       kwset->target = obstack_alloc(&kwset->obstack, kwset->mind);
@@ -471,11 +467,12 @@ kwsprep (kwset_t kws)
           curr = curr->next;
         }
       /* Looking for the delta2 shift that we might make after a
-         backwards match has failed.  Extract it from the trie. */
+         backwards match has failed.  Extract it from the trie.  */
       if (kwset->mind > 1)
         {
-          kwset->shift = obstack_alloc(&kwset->obstack,
-                                       sizeof (*kwset->shift) * (kwset->mind - 1));
+          kwset->shift
+            = obstack_alloc (&kwset->obstack,
+                             sizeof *kwset->shift * (kwset->mind - 1));
           if (!kwset->shift)
             return _("memory exhausted");
           for (i = 0, curr = kwset->trie->next; i < kwset->mind - 1; ++i)
@@ -487,11 +484,9 @@ kwsprep (kwset_t kws)
     }
 
   /* Fix things up for any translation table. */
-  if ((trans = kwset->trans) != NULL)
+  if (trans)
     for (i = 0; i < NCHAR; ++i)
       kwset->delta[i] = delta[U(trans[i])];
-  else
-    memcpy(kwset->delta, delta, NCHAR);
 
   return NULL;
 }
@@ -553,16 +548,16 @@ bmexec (kwset_t kws, char const *text, size_t size)
         break;
       found:
         d = len;
-        while (1)
+        while (true)
           {
             if (tp[-2] == gc2)
               {
                 for (i = 3; i <= d && tp[-i] == sp[-i]; ++i)
-                  ;
+                  continue;
                 if (i > d)
                   {
                     for (i = d + skip + 1; i <= len && tp[-i] == sp[-i]; ++i)
-                      ;
+                      continue;
                     if (i > len)
                       return tp - len - text;
                   }
@@ -591,16 +586,16 @@ bmexec (kwset_t kws, char const *text, size_t size)
       if (d != 0)
         continue;
       d = len;
-      while (1)
+      while (true)
         {
           if (tp[-2] == gc2)
             {
               for (i = 3; i <= d && tp[-i] == sp[-i]; ++i)
-                ;
+                continue;
               if (i > d)
                 {
                   for (i = d + skip + 1; i <= len && tp[-i] == sp[-i]; ++i)
-                    ;
+                    continue;
                   if (i > len)
                     return tp - len - text;
                 }
@@ -691,7 +686,8 @@ cwexec (kwset_t kws, char const *text, size_t len, struct kwsmatch *kwsmatch)
       d = trie->shift;
       while (beg > text)
         {
-          c = trans ? trans[U(*--beg)] : *--beg;
+          unsigned char uc = *--beg;
+          c = trans ? trans[uc] : uc;
           tree = trie->links;
           while (tree && c != tree->label)
             if (c < tree->label)
@@ -742,7 +738,8 @@ cwexec (kwset_t kws, char const *text, size_t len, struct kwsmatch *kwsmatch)
       d = trie->shift;
       while (beg > text)
         {
-          c = trans ? trans[U(*--beg)] : *--beg;
+          unsigned char uc = *--beg;
+          c = trans ? trans[uc] : uc;
           tree = trie->links;
           while (tree && c != tree->label)
             if (c < tree->label)
-- 
1.9.0

From 22af87b1a8de1958d504b5e6e17553ee11930b6c Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Mon, 7 Apr 2014 19:48:33 -0700
Subject: [PATCH 3/3] grep: simplify memory allocation in kwset

* src/kwset.c: Include kwset.h first, to check its prereqs.
Include xalloc.h, for xmalloc.
(kwsalloc): Use xmalloc, not malloc, so that the caller need not
worry about memory allocation failure.
(kwsalloc, kwsincr, kwsprep): Do not worry about obstack_alloc
returning NULL, as that's not possible.
(kwsalloc, kwsincr, kwsprep, bmexec, cwexec, kwsexec, kwsfree):
Omit unnecessary conversion between struct kwset * and kwset_t.
(kwsincr, kwsprep): Return void since memory-allocation failure is
not possible now.  All uses changed.
* src/kwset.h: Include <stddef.h>, for size_t, so that this
include file doesn't require other files to be included first.
---
 src/dfasearch.c | 10 ++-----
 src/kwsearch.c  |  7 ++---
 src/kwset.c     | 93 ++++++++++++++++++---------------------------------------
 src/kwset.h     | 17 +++++------
 4 files changed, 42 insertions(+), 85 deletions(-)

diff --git a/src/dfasearch.c b/src/dfasearch.c
index adec4e2..44360b6 100644
--- a/src/dfasearch.c
+++ b/src/dfasearch.c
@@ -90,7 +90,6 @@ kwsmusts (void)
   struct dfamust const *dm = dfamusts (dfa);
   if (dm)
     {
-      char const *err;
       kwsinit (&kwset);
       /* First, we compile in the substrings known to be exact
          matches.  The kwset matcher will return the index
@@ -100,8 +99,7 @@ kwsmusts (void)
           if (!dm->exact)
             continue;
           ++kwset_exact_matches;
-          if ((err = kwsincr (kwset, dm->must, strlen (dm->must))) != NULL)
-            error (EXIT_TROUBLE, 0, "%s", err);
+          kwsincr (kwset, dm->must, strlen (dm->must));
         }
       /* Now, we compile the substrings that will require
          the use of the regexp matcher.  */
@@ -109,11 +107,9 @@ kwsmusts (void)
         {
           if (dm->exact)
             continue;
-          if ((err = kwsincr (kwset, dm->must, strlen (dm->must))) != NULL)
-            error (EXIT_TROUBLE, 0, "%s", err);
+          kwsincr (kwset, dm->must, strlen (dm->must));
         }
-      if ((err = kwsprep (kwset)) != NULL)
-        error (EXIT_TROUBLE, 0, "%s", err);
+      kwsprep (kwset);
     }
 }
 
diff --git a/src/kwsearch.c b/src/kwsearch.c
index dd01518..df94951 100644
--- a/src/kwsearch.c
+++ b/src/kwsearch.c
@@ -32,7 +32,6 @@ static kwset_t kwset;
 void
 Fcompile (char const *pattern, size_t size)
 {
-  char const *err;
   size_t psize = size;
   mb_len_map_t *map = NULL;
   char const *pat = (match_icase && MB_CUR_MAX > 1
@@ -65,14 +64,12 @@ Fcompile (char const *pattern, size_t size)
 #endif
         }
 
-      if ((err = kwsincr (kwset, beg, end - beg)) != NULL)
-        error (EXIT_TROUBLE, 0, "%s", err);
+      kwsincr (kwset, beg, end - beg);
       beg = lim;
     }
   while (beg < pat + psize);
 
-  if ((err = kwsprep (kwset)) != NULL)
-    error (EXIT_TROUBLE, 0, "%s", err);
+  kwsprep (kwset);
 }
 
 /* Apply the MAP (created by mbtoupper) to the uppercase-buffer-relative
diff --git a/src/kwset.c b/src/kwset.c
index 6c07249..d5db12f 100644
--- a/src/kwset.c
+++ b/src/kwset.c
@@ -32,11 +32,14 @@
    failure function used below. */
 
 #include <config.h>
+
+#include "kwset.h"
+
 #include <stdbool.h>
 #include <sys/types.h>
 #include "system.h"
-#include "kwset.h"
 #include "obstack.h"
+#include "xalloc.h"
 
 #define link kwset_link
 
@@ -91,25 +94,15 @@ struct kwset
 };
 
 /* Allocate and initialize a keyword set object, returning an opaque
-   pointer to it.  Return NULL if memory is not available. */
+   pointer to it.  */
 kwset_t
 kwsalloc (char const *trans)
 {
-  struct kwset *kwset;
+  struct kwset *kwset = xmalloc (sizeof *kwset);
 
-  kwset = (struct kwset *) malloc(sizeof (struct kwset));
-  if (!kwset)
-    return NULL;
-
-  obstack_init(&kwset->obstack);
+  obstack_init (&kwset->obstack);
   kwset->words = 0;
-  kwset->trie
-    = (struct trie *) obstack_alloc(&kwset->obstack, sizeof (struct trie));
-  if (!kwset->trie)
-    {
-      kwsfree((kwset_t) kwset);
-      return NULL;
-    }
+  kwset->trie = obstack_alloc (&kwset->obstack, sizeof *kwset->trie);
   kwset->trie->accepting = 0;
   kwset->trie->links = NULL;
   kwset->trie->parent = NULL;
@@ -122,19 +115,17 @@ kwsalloc (char const *trans)
   kwset->target = NULL;
   kwset->trans = trans;
 
-  return (kwset_t) kwset;
+  return kwset;
 }
 
 /* This upper bound is valid for CHAR_BIT >= 4 and
    exact for CHAR_BIT in { 4..11, 13, 15, 17, 19 }. */
 #define DEPTH_SIZE (CHAR_BIT + CHAR_BIT/2)
 
-/* Add the given string to the contents of the keyword set.  Return NULL
-   for success, an error message otherwise. */
-const char *
-kwsincr (kwset_t kws, char const *text, size_t len)
+/* Add the given string to the contents of the keyword set.  */
+void
+kwsincr (kwset_t kwset, char const *text, size_t len)
 {
-  struct kwset *kwset = kws;
   struct trie *trie = kwset->trie;
   char const *trans = kwset->trans;
 
@@ -171,19 +162,10 @@ kwsincr (kwset_t kws, char const *text, size_t len)
          a link in the current trie node's tree. */
       if (!link)
         {
-          link = (struct tree *) obstack_alloc(&kwset->obstack,
-                                               sizeof (struct tree));
-          if (!link)
-            return _("memory exhausted");
+          link = obstack_alloc (&kwset->obstack, sizeof *link);
           link->llink = NULL;
           link->rlink = NULL;
-          link->trie = (struct trie *) obstack_alloc(&kwset->obstack,
-                                                     sizeof (struct trie));
-          if (!link->trie)
-            {
-              obstack_free(&kwset->obstack, link);
-              return _("memory exhausted");
-            }
+          link->trie = obstack_alloc (&kwset->obstack, sizeof *link->trie);
           link->trie->accepting = 0;
           link->trie->links = NULL;
           link->trie->parent = trie;
@@ -283,8 +265,6 @@ kwsincr (kwset_t kws, char const *text, size_t len)
     kwset->mind = trie->depth;
   if (trie->depth > kwset->maxd)
     kwset->maxd = trie->depth;
-
-  return NULL;
 }
 
 /* Enqueue the trie nodes referenced from the given tree in the
@@ -382,10 +362,9 @@ treenext (struct tree const *tree, struct trie *next[])
 
 /* Compute the shift for each trie node, as well as the delta
    table and next cache for the given keyword set. */
-const char *
-kwsprep (kwset_t kws)
+void
+kwsprep (kwset_t kwset)
 {
-  struct kwset *kwset = kws;
   char const *trans = kwset->trans;
   int i;
   unsigned char deltabuf[NCHAR];
@@ -458,9 +437,7 @@ kwsprep (kwset_t kws)
   if (!trans && kwset->words == 1)
     {
       /* Looking for just one string.  Extract it from the trie. */
-      kwset->target = obstack_alloc(&kwset->obstack, kwset->mind);
-      if (!kwset->target)
-        return _("memory exhausted");
+      kwset->target = obstack_alloc (&kwset->obstack, kwset->mind);
       for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i)
         {
           kwset->target[i] = curr->links->label;
@@ -473,8 +450,6 @@ kwsprep (kwset_t kws)
           kwset->shift
             = obstack_alloc (&kwset->obstack,
                              sizeof *kwset->shift * (kwset->mind - 1));
-          if (!kwset->shift)
-            return _("memory exhausted");
           for (i = 0, curr = kwset->trie->next; i < kwset->mind - 1; ++i)
             {
               kwset->shift[i] = curr->shift;
@@ -487,22 +462,17 @@ kwsprep (kwset_t kws)
   if (trans)
     for (i = 0; i < NCHAR; ++i)
       kwset->delta[i] = delta[U(trans[i])];
-
-  return NULL;
 }
 
 /* Fast boyer-moore search. */
 static size_t _GL_ATTRIBUTE_PURE
-bmexec (kwset_t kws, char const *text, size_t size)
+bmexec (kwset_t kwset, char const *text, size_t size)
 {
-  struct kwset const *kwset;
   unsigned char const *d1;
   char const *ep, *sp, *tp;
-  int d, i, len, skip;
+  int d, i, skip;
   char gc1, gc2;
-
-  kwset = (struct kwset const *) kws;
-  len = kwset->mind;
+  int len = kwset->mind;
 
   if (len == 0)
     return 0;
@@ -619,9 +589,8 @@ bmexec (kwset_t kws, char const *text, size_t size)
 
 /* Hairy multiple string search. */
 static size_t _GL_ARG_NONNULL ((4))
-cwexec (kwset_t kws, char const *text, size_t len, struct kwsmatch *kwsmatch)
+cwexec (kwset_t kwset, char const *text, size_t len, struct kwsmatch *kwsmatch)
 {
-  struct kwset const *kwset;
   struct trie * const *next;
   struct trie const *trie;
   struct trie const *accept;
@@ -638,7 +607,6 @@ cwexec (kwset_t kws, char const *text, size_t len, struct kwsmatch *kwsmatch)
 #endif
 
   /* Initialize register copies and look for easy ways out. */
-  kwset = (struct kwset *) kws;
   if (len < kwset->mind)
     return -1;
   next = kwset->next;
@@ -775,18 +743,18 @@ cwexec (kwset_t kws, char const *text, size_t len, struct kwsmatch *kwsmatch)
   return mch - text;
 }
 
-/* Search TEXT for a match of any member of the keyword set, KWS.
+/* Search TEXT for a match of any member of KWSET.
    Return the offset (into TEXT) of the first byte of the matching substring,
    or (size_t) -1 if no match is found.  Upon a match, store details in
    *KWSMATCH: index of matched keyword, start offset (same as the return
    value), and length.  */
 size_t
-kwsexec (kwset_t kws, char const *text, size_t size, struct kwsmatch *kwsmatch)
+kwsexec (kwset_t kwset, char const *text, size_t size,
+         struct kwsmatch *kwsmatch)
 {
-  struct kwset const *kwset = (struct kwset *) kws;
   if (kwset->words == 1 && kwset->trans == NULL)
     {
-      size_t ret = bmexec (kws, text, size);
+      size_t ret = bmexec (kwset, text, size);
       if (ret != (size_t) -1)
         {
           kwsmatch->index = 0;
@@ -796,16 +764,13 @@ kwsexec (kwset_t kws, char const *text, size_t size, struct kwsmatch *kwsmatch)
       return ret;
     }
   else
-    return cwexec(kws, text, size, kwsmatch);
+    return cwexec (kwset, text, size, kwsmatch);
 }
 
 /* Free the components of the given keyword set. */
 void
-kwsfree (kwset_t kws)
+kwsfree (kwset_t kwset)
 {
-  struct kwset *kwset;
-
-  kwset = (struct kwset *) kws;
-  obstack_free(&kwset->obstack, NULL);
-  free(kws);
+  obstack_free (&kwset->obstack, NULL);
+  free (kwset);
 }
diff --git a/src/kwset.h b/src/kwset.h
index 2d3cdd9..12afb8e 100644
--- a/src/kwset.h
+++ b/src/kwset.h
@@ -21,6 +21,8 @@
    The author may be reached (Email) at the address [email-masked],
    or (US mail) as Mike Haertel c/o Free Software Foundation. */
 
+#include <stddef.h>
+
 struct kwsmatch
 {
   size_t index;			/* Index number of matching keyword. */
@@ -33,20 +35,17 @@ struct kwsmatch
 struct kwset;
 typedef struct kwset *kwset_t;
 
-/* Return an opaque pointer to a newly allocated keyword set, or NULL
-   if enough memory cannot be obtained.  The argument if non-NULL
+/* Return an opaque pointer to a newly allocated keyword set.  A nonnull arg
    specifies a table of character translations to be applied to all
-   pattern and search text. */
+   pattern and search text.  */
 extern kwset_t kwsalloc (char const *);
 
 /* Incrementally extend the keyword set to include the given string.
-   Return NULL for success, or an error message.  Remember an index
-   number for each keyword included in the set. */
-extern const char *kwsincr (kwset_t, char const *, size_t);
+   Remember an index number for each keyword included in the set.  */
+extern void kwsincr (kwset_t, char const *, size_t);
 
-/* When the keyword set has been completely built, prepare it for
-   use.  Return NULL for success, or an error message. */
-extern const char *kwsprep (kwset_t);
+/* When the keyword set has been completely built, prepare it for use.  */
+extern void kwsprep (kwset_t);
 
 /* Search through the given buffer for a member of the keyword set.
    Return a pointer to the leftmost longest match found, or NULL if
-- 
1.9.0

Subject: [PATCH] grep: optimization by using the Galil rule for Boyer-Moore algorithm in KWSet
From: Norihiro Tanaka <[email-masked]>
To: [email-masked]
Date: Fri, 14 Mar 2014 21:21:21 +0900
List-Id: <debbugs-submit.debbugs.gnu.org>

Package: grep
Tags: patch

The Boyer-Moore algorithm runs in O(m n) in the worst case,
 which perhaps it may be much slower than the DFA.

The Galil rule enables to change O(m n) into O(n) for its case without
overheads and/or slow-down for other cases by avoiding to compare more
than once for a position in the text.  This patch implements it.

I prepare following string, which makes a worst case for Boyer-Moore
algorithm, to measure the performance.

    yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 > ../k

I run the test with the patch (best-of-5 trials):

    env LC_ALL=C time -p src/grep kjjjjjjjjjjjjjjjjjjj k
        real 0.70       user 0.32       sys 0.38

Back out that commit (temporarily), recompile, and rerun the experiment:

    env LC_ALL=C time -p src/grep kjjjjjjjjjjjjjjjjjjj k
        real 3.97       user 3.56       sys 0.40

Norihiro