Subject: bug#17700: closed (Re: bug#17700: [PATCH] dfa: speed-up for a pattern that many atoms are catenated)

From: [email-masked] (GNU bug Tracking System)
Date: Fri, 06 Jun 2014 13:20:03 +0000

Your bug report

#17700: [PATCH] dfa: speed-up for a pattern that many atoms are catenated

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

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

Subject: Re: bug#17700: [PATCH] dfa: speed-up for a pattern that many atoms are catenated
From: Norihiro Tanaka <[email-masked]>
To: Paul Eggert <[email-masked]>
Cc: Aharon Robbins <[email-masked]>, [email-masked]
Date: Fri, 06 Jun 2014 22:19:13 +0900
List-Id: <debbugs-submit.debbugs.gnu.org>

Paul Eggert wrote:
> So it looks like your patch confers some advantage, but on my platform
> almost all the speedup is achieved simply by switching to the system strstr.

First, I tested on CentOS 5.10.  Next, I tested on RHEL 6.5, and get
result as same as you.  strstr() on CentOS 5.10 may be too old.  I'm
sure that this bug has already been fixed.  So closing.

Thanks,
Norihiro

Subject: [PATCH] dfa: speed-up for a pattern that many atoms are catenated
From: Norihiro Tanaka <[email-masked]>
To: [email-masked]
Date: Thu, 05 Jun 2014 20:32:44 +0900
List-Id: <debbugs-submit.debbugs.gnu.org>

When many atoms are catenated, dfamust() is very slow in order that
pushing a string into `in' list is slow.  This change fixes it.

I tested below to confirm the effect.

  $ printf '%08192d\n' 0 | time -p src/grep -f - /dev/null
From d7ff453a2aac557fb133100b94e2fc7c007fbe26 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Tue, 20 May 2014 10:18:42 +0900
Subject: [PATCH] dfa: speed-up for a pattern that many atoms are catenated

When many atoms are catenated, dfamust() is very slow in order that
pushing a string into `in' list is slow.  This change fixes it.

* src/dfa.c (istrstr): Use memchr() in order to find a potential match.
(enlist): If there is already something in the list, don't allocate
memory.
(dfamust): If don't have to check in the list, enlist a new entry
directly.
---
 src/dfa.c | 57 +++++++++++++++++++++++++++++++++++++--------------------
 1 file changed, 37 insertions(+), 20 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index 48a83cd..9f6d588 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -3753,15 +3753,24 @@ icatalloc (char *old, char const *new)
 }
 
 static char *_GL_ATTRIBUTE_PURE
-istrstr (char const *lookin, char const *lookfor)
+istrstr (char const *lookin, char const *lookfor, size_t const lenfor)
 {
   char const *cp;
-  size_t len;
+  size_t lenin;
 
-  len = strlen (lookfor);
-  for (cp = lookin; *cp != '\0'; ++cp)
-    if (strncmp (cp, lookfor, len) == 0)
-      return (char *) cp;
+  lenin = strlen (lookin);
+  if (lenfor == 1)
+    return memchr (lookin, *lookfor, lenin);
+
+  cp = lookin;
+  for (cp = lookin; cp < lookin + lenin - lenfor; ++cp)
+    {
+      memchr (cp, *lookfor, lenin - (cp - lookin));
+      if (!cp)
+        return NULL;
+      if (strncmp (cp + 1, lookfor + 1, lenfor - 1) == 0)
+        return (char *) cp;
+    }
   return NULL;
 }
 
@@ -3776,19 +3785,16 @@ static char **
 enlist (char **cpp, char *new, size_t len)
 {
   size_t i, j;
-  new = memcpy (xmalloc (len + 1), new, len);
-  new[len] = '\0';
   /* Is there already something in the list that's new (or longer)?  */
   for (i = 0; cpp[i] != NULL; ++i)
-    if (istrstr (cpp[i], new) != NULL)
-      {
-        free (new);
-        return cpp;
-      }
+    if (istrstr (cpp[i], new, len) != NULL)
+      return cpp;
+  new = memcpy (xmalloc (len + 1), new, len);
+  new[len] = '\0';
   /* Eliminate any obsoleted strings.  */
   j = 0;
   while (cpp[j] != NULL)
-    if (istrstr (new, cpp[j]) == NULL)
+    if (istrstr (new, cpp[j], strlen (cpp[j])) == NULL)
       ++j;
     else
       {
@@ -4023,17 +4029,28 @@ dfamust (struct dfa *d)
             /* In.  Everything in left, plus everything in
                right, plus concatenation of
                left's right and right's left.  */
-            lmp->in = addlists (lmp->in, rmp->in);
             if (lmp->right[0] != '\0' && rmp->left[0] != '\0')
               {
                 size_t lrlen = strlen (lmp->right);
                 size_t rllen = strlen (rmp->left);
-                char *tp = xmalloc (lrlen + rllen);
-                memcpy (tp, lmp->right, lrlen);
-                memcpy (tp + lrlen, rmp->left, rllen);
-                lmp->in = enlist (lmp->in, tp, lrlen + rllen);
-                free (tp);
+                if (!lmp->in[1] && !rmp->in[1])
+                  {
+                    lmp->in[0] = xnrealloc (lmp->in[0], lrlen + rllen + 1,
+                                            sizeof *lmp->in[0]);
+                    memcpy (lmp->in[0] + lrlen, rmp->in[0], rllen + 1);
+                  }
+                else
+                  {
+                    char *tp = xmalloc (lrlen + rllen);
+                    memcpy (tp, lmp->right, lrlen);
+                    memcpy (tp + lrlen, rmp->left, rllen);
+                    lmp->in = addlists (lmp->in, rmp->in);
+                    lmp->in = enlist (lmp->in, tp, lrlen + rllen);
+                    free (tp);
+                  }
               }
+            else
+              lmp->in = addlists (lmp->in, rmp->in);
             /* Left-hand */
             if (lmp->is[0] != '\0')
               lmp->left = icatalloc (lmp->left, rmp->left);
-- 
2.0.0