Subject: bug#17230: [PATCH 1/2] grep: may also use Boyer-Moore algorithm for case-insensitive matching

From: Norihiro Tanaka <[email-masked]>
Date: Thu, 24 Apr 2014 08:59:38 +0900

Paul Eggert wrote:
> That's odd, as I'm not observing this slowdown.

Though I apply 17230.diff and tests, I don't observed slowdown.  However,
I cann't find macros `BM_DELTA2_SEARCH' etc in 17230.diff.  Could you also
consider them, and run (A) instead of (B)?  It means that overheads by
`yes' and `head' should be ignored.

(A)
$ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >k
$ grep -i jk

(B)
$ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 | grep -i jk

I attach the difference between current master and my version.

Though I don't analyze detail still, don't seem that overhead by check
for `trans' in `tr' function, which is called each time the comparison
of a character, can be ignorable.

Norihiro
diff --git a/src/kwset.c b/src/kwset.c
index f86ee03..3c53e81 100644
--- a/src/kwset.c
+++ b/src/kwset.c
@@ -55,6 +55,35 @@
 
 #define U(c) (to_uchar (c))
 
+#if defined(__i386__) || defined(__x86_64__)
+#define SHIFT(p, d)	\
+  switch (d)		\
+    {			\
+    default:		\
+      p += d;		\
+      break;		\
+    case 8:		\
+      ++p;		\
+    case 7:		\
+      ++p;		\
+    case 6:		\
+      ++p;		\
+    case 5:		\
+      ++p;		\
+    case 4:		\
+      ++p;		\
+    case 3:		\
+      ++p;		\
+    case 2:		\
+      ++p;		\
+    case 1:		\
+      ++p;		\
+    }
+#else
+#define SHIFT(p, d)	\
+  p += d;
+#endif
+
 /* Balanced tree of edges and labels leaving a given trie node. */
 struct tree
 {
@@ -464,80 +493,75 @@ kwsprep (kwset_t kwset)
       kwset->delta[i] = delta[U(trans[i])];
 }
 
-/* Use TRANS to transliterate C.  A null TRANS does no transliteration.  */
-static char
-tr (char const *trans, char c)
-{
-  return trans ? trans[U(c)] : c;
-}
-
-/* Delta2 portion of a Boyer-Moore search.  *TP is the string text
-   pointer; it is updated in place.  EP is the end of the string text,
-   and SP the end of the pattern.  LEN is the pattern length; it must
-   be at least 2.  TRANS, if nonnull, is the input translation table.
-   GC1 and GC2 are the last and second-from last bytes of the pattern,
-   transliterated by TRANS; the caller precomputes them for
-   efficiency.  If D1 is nonnull, it is a delta1 table for shifting *TP
-   when failing.  KWSET->shift says how much to shift.  */
-static inline bool
-bm_delta2_search (char const **tpp, char const *ep, char const *sp, int len,
-                  char const *trans, char gc1, char gc2,
-                  unsigned char const *d1, kwset_t kwset)
-{
-  char const *tp = *tpp;
-  int d = len, skip = 0;
-
-  while (true)
-    {
-      int i = 2;
-      if (tr (trans, tp[-2]) == gc2)
-        {
-          while (++i <= d)
-            if (tr (trans, tp[-i]) != tr (trans, sp[-i]))
-              break;
-          if (i > d)
-            {
-              for (i = d + skip + 1; i <= len; ++i)
-                if (tr (trans, tp[-i]) != tr (trans, sp[-i]))
-                  break;
-              if (i > len)
-                {
-                  *tpp = tp - len;
-                  return true;
-                }
-            }
-        }
-
-      tp += d = kwset->shift[i - 2];
-      if (tp > ep)
-        break;
-      if (tr (trans, tp[-1]) != gc1)
-        {
-          if (d1)
-            tp += d1[U(tp[-1])];
-          break;
-        }
-      skip = i - 1;
+#define BM_DELTA2_SEARCH 				\
+  if (TRANS(tp[-2]) == gc2)				\
+    {							\
+      for (i = 3; i <= len; ++i)			\
+        if (TRANS(tp[-i]) != TRANS(sp[-i]))		\
+          break;					\
+      if (i > len)					\
+        return tp - len - text;				\
+      d = kwset->shift[i - 2]; SHIFT(tp, d);		\
+      if (tp > ep)					\
+        break;						\
+      if (TRANS(tp[-1]) != gc1)				\
+        {						\
+          d = d1[U(tp[-1])]; LAST_SHIFT;		\
+          continue;					\
+        }						\
+      skip = i - 1;					\
+    }							\
+  else							\
+    {							\
+      d = kwset->shift[0]; SHIFT(tp, d);		\
+      if (tp > ep)					\
+        break;						\
+      if (TRANS(tp[-1]) != gc1)				\
+        {						\
+          d = d1[U(tp[-1])]; LAST_SHIFT;		\
+          continue;					\
+        }						\
+      skip = 1;						\
+    }							\
+  while (true)						\
+    {							\
+      if (TRANS(tp[-2]) == gc2)				\
+        {						\
+          for (i = 3; i <= d; ++i)			\
+            if (TRANS(tp[-i]) != TRANS(sp[-i]))		\
+              break;					\
+          if (i > d)					\
+            {						\
+              for (i = d + skip + 1; i <= len; ++i)	\
+                if (TRANS(tp[-i]) != TRANS(sp[-i]))	\
+                  break;				\
+              if (i > len)				\
+                return tp - len - text;			\
+            }						\
+          d = kwset->shift[i - 2]; SHIFT(tp, d);	\
+          if (tp > ep)					\
+            break;					\
+          if (TRANS(tp[-1]) != gc1)			\
+            {						\
+              d = d1[U(tp[-1])]; LAST_SHIFT;		\
+              break;					\
+            }						\
+          skip = i - 1;					\
+        }						\
+      else						\
+        {						\
+          d = kwset->shift[0]; SHIFT(tp, d);		\
+          if (tp > ep)					\
+            break;					\
+          if (TRANS(tp[-1]) != gc1)			\
+            {						\
+              d = d1[U(tp[-1])]; LAST_SHIFT;		\
+              break;					\
+            }						\
+          skip = 1;					\
+        }						\
     }
 
-  *tpp = tp;
-  return false;
-}
-
-/* Return the address of the first byte in the buffer S that equals C.
-   S contains N bytes.  If TRANS is nonnull, use it to transliterate
-   S's bytes before comparing them.  */
-static char const *
-memchr_trans (char const *s, char c, size_t n, char const *trans)
-{
-  if (! trans)
-    return memchr (s, c, n);
-  char const *slim = s + n;
-  for (; s < slim; s++)
-    if (trans[U(*s)] == c)
-      return s;
-  return NULL;
-}
 
 /* Fast boyer-moore search. */
 static size_t _GL_ATTRIBUTE_PURE
@@ -545,7 +569,8 @@ bmexec (kwset_t kwset, char const *text, size_t size)
 {
   unsigned char const *d1;
   char const *ep, *sp, *tp;
-  int d;
+  int d, i, skip;
+  char gc1, gc2;
   int len = kwset->mind;
   char const *trans = kwset->trans;
 
@@ -555,48 +580,94 @@ bmexec (kwset_t kwset, char const *text, size_t size)
     return -1;
   if (len == 1)
     {
-      tp = memchr_trans (text, kwset->target[0], size, trans);
-      return tp ? tp - text : -1;
+      if (trans)
+        {
+          for (tp = text; tp < text + size; tp++)
+            if (trans[U(*tp)] == kwset->target[0])
+              return tp - text;
+          return -1;
+        }
+      else
+        {
+          tp = memchr (text, kwset->target[0], size);
+          return tp ? tp - text : -1;
+        }
     }
 
   d1 = kwset->delta;
   sp = kwset->target + len;
   tp = text + len;
-  char gc1 = tr (trans, sp[-1]);
-  char gc2 = tr (trans, sp[-2]);
+  if (trans)
+    {
+      gc1 = trans[U(sp[-1])];
+      gc2 = trans[U(sp[-2])];
+    }
+  else
+    {
+      gc1 = sp[-1];
+      gc2 = sp[-2];
+    }
+  skip = 0;
 
   /* Significance of 12: 1 (initial offset) + 10 (skip loop) + 1 (md2). */
   if (size > 12 * len)
     /* 11 is not a bug, the initial offset happens only once. */
-    for (ep = text + size - 11 * len; tp <= ep; )
+    for (ep = text + size - 11 * len;;)
       {
-        d = d1[U(tp[-1])], tp += d;
-        d = d1[U(tp[-1])], tp += d;
-        if (d != 0)
+        while (tp <= ep)
           {
-            d = d1[U(tp[-1])], tp += d;
-            d = d1[U(tp[-1])], tp += d;
-            d = d1[U(tp[-1])], tp += d;
-            if (d != 0)
+            d = d1[U(tp[-1])]; SHIFT(tp, d);
+            d = d1[U(tp[-1])]; SHIFT(tp, d);
+            if (d == 0)
+              goto found;
+            d = d1[U(tp[-1])]; SHIFT(tp, d);
+            d = d1[U(tp[-1])]; SHIFT(tp, d);
+            d = d1[U(tp[-1])]; SHIFT(tp, d);
+            if (d == 0)
+              goto found;
+            d = d1[U(tp[-1])]; SHIFT(tp, d);
+            d = d1[U(tp[-1])]; SHIFT(tp, d);
+            d = d1[U(tp[-1])]; SHIFT(tp, d);
+            if (d == 0)
+              goto found;
+            /* memchar() of glibc is faster than seeking by delta1 on
+               some platforms.  When there is no chance to match for a
+               while, use it on them.  */
+#if defined(__GLIBC__) && (defined(__i386__) || defined(__x86_64__))
+            if (!trans)
               {
-                d = d1[U(tp[-1])], tp += d;
-                d = d1[U(tp[-1])], tp += d;
-                d = d1[U(tp[-1])], tp += d;
-                if (d != 0)
+                tp = memchr (tp - 1, gc1, size + text - tp + 1);
+                if (tp)
                   {
-                    /* Typically memchr is faster than seeking by
-                       delta1 when there is no chance to match for
-                       a while.  */
-                    tp--;
-                    tp = memchr_trans (tp, gc1, text + size - tp, trans);
-                    if (! tp)
-                      return -1;
-                    tp++;
+                    ++tp;
+                    goto found;
                   }
+                else
+                  return -1;
+              }
+            else
+#endif
+              {
+                d = d1[U(tp[-1])]; SHIFT(tp, d);
+                d = d1[U(tp[-1])]; SHIFT(tp, d);
               }
           }
-        if (bm_delta2_search (&tp, ep, sp, len, trans, gc1, gc2, d1, kwset))
-          return tp - text;
+        break;
+      found:
+#undef LAST_SHIFT
+#define LAST_SHIFT SHIFT(tp, d);
+        if (trans)
+          {
+#undef TRANS
+#define TRANS(ch) trans[U(ch)]
+            BM_DELTA2_SEARCH;
+          }
+        else
+          {
+#undef TRANS
+#define TRANS(ch) ch
+            BM_DELTA2_SEARCH;
+          }
       }
 
   /* Now we have only a few characters left to search.  We
@@ -605,11 +676,24 @@ bmexec (kwset_t kwset, char const *text, size_t size)
   d = d1[U(tp[-1])];
   while (d <= ep - tp)
     {
-      d = d1[U((tp += d)[-1])];
+      SHIFT(tp, d);
+      d = d1[U(tp[-1])];
       if (d != 0)
         continue;
-      if (bm_delta2_search (&tp, ep, sp, len, trans, gc1, gc2, NULL, kwset))
-        return tp - text;
+#undef LAST_SHIFT
+#define LAST_SHIFT
+      if (trans)
+        {
+#undef TRANS
+#define TRANS(ch) trans[U(ch)]
+          BM_DELTA2_SEARCH;
+        }
+      else
+        {
+#undef TRANS
+#define TRANS(ch) ch
+          BM_DELTA2_SEARCH;
+        }
     }
 
   return -1;
@@ -659,17 +743,19 @@ cwexec (kwset_t kwset, char const *text, size_t len, struct kwsmatch *kwsmatch)
     {
       if (qlim && end <= qlim)
         {
-          end += d - 1;
-          while ((d = delta[c = *end]) && end < qlim)
+          SHIFT(end, d);
+          while ((d = delta[c = end[-1]]) && end <= qlim)
             {
-              end += d;
-              end += delta[U(*end)];
-              end += delta[U(*end)];
+              SHIFT(end, d);
+              d = delta[U(end[-1])]; SHIFT(end, d);
+              d = delta[U(end[-1])]; SHIFT(end, d);
             }
-          ++end;
         }
       else
-        d = delta[c = (end += d)[-1]];
+        {
+          SHIFT(end, d);
+          d = delta[c = end[-1]];
+        }
       if (d)
         continue;
       beg = end - 1;
@@ -718,7 +804,8 @@ cwexec (kwset_t kwset, char const *text, size_t len, struct kwsmatch *kwsmatch)
   d = 1;
   while (lim - end >= d)
     {
-      if ((d = delta[c = (end += d)[-1]]) != 0)
+      SHIFT(end, d);
+      if ((d = delta[c = end[-1]]) != 0)
         continue;
       beg = end - 1;
       if (!(trie = next[c]))