Subject: Re: bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching

From: Paul Eggert <[email-masked]>
Date: Wed, 09 Apr 2014 17:35:31 -0700

On 04/09/2014 06:54 AM, Norihiro Tanaka wrote:
> memchr() of glibc is faster than seeking by delta1 on some platforms.
> So, when there is no chance to match for a while, use it on them.
>
> Speed-up about 3x in best case, 10% in normal case by this patch.
>
> It's still available only for x86 and x86-64 platform.
>

Thanks, I have some questions about this one.

What benchmark did you use to time this?

THe patch refers to a variable called 'trans' that is not in the current 
savannah git master.  Is there some other patch that establishes this 
variable, a patch that is a prerequisite for this one?  If trans is a 
cached copy of kwset->trans, isn't that guaranteed to be NULL here?

What is delta1?  It's mentioned in a comment but not in the code.

It'd be simpler to use memchr on all platforms; is there a major 
performance downside to that?  For example, what about the attached 
patch instead?  It also simplifies things a bit to avoid a label and its 
associated gotos, under the assumption that trans is NULL here.
diff --git a/src/kwset.c b/src/kwset.c
index d5db12f..9163482 100644
--- a/src/kwset.c
+++ b/src/kwset.c
@@ -494,29 +494,32 @@ bmexec (kwset_t kwset, char const *text, size_t size)
   /* 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;;)
+    for (ep = text + size - 11 * len; tp <= ep; )
       {
-        while (tp <= ep)
+        d = d1[U(tp[-1])], tp += d;
+        d = d1[U(tp[-1])], tp += d;
+        if (d != 0)
           {
             d = d1[U(tp[-1])], tp += d;
             d = d1[U(tp[-1])], tp += d;
-            if (d == 0)
-              goto found;
-            d = d1[U(tp[-1])], tp += d;
-            d = d1[U(tp[-1])], tp += d;
-            d = d1[U(tp[-1])], tp += d;
-            if (d == 0)
-              goto found;
-            d = d1[U(tp[-1])], tp += d;
-            d = d1[U(tp[-1])], tp += d;
-            d = d1[U(tp[-1])], tp += d;
-            if (d == 0)
-              goto found;
-            d = d1[U(tp[-1])], tp += d;
             d = d1[U(tp[-1])], tp += d;
+            if (d != 0)
+              {
+                d = d1[U(tp[-1])], tp += d;
+                d = d1[U(tp[-1])], tp += d;
+                d = d1[U(tp[-1])], tp += d;
+                if (d != 0)
+                  {
+                    /* It's typically faster to use memchr when there is
+                       no chance to match for a while.  */
+                    tp = memchr (tp - 1, gc1, text + size - (tp - 1));
+                    if (! tp)
+                      return -1;
+                    tp++;
+                  }
+              }
           }
-        break;
-      found:
+
         d = len;
         while (true)
           {