Subject: bug#40634: Massive pattern list handling with -E format seems very slow since 2.28.

From: Norihiro Tanaka <[email-masked]>
Date: Sun, 19 Apr 2020 07:41:49 +0900

On Sat, 18 Apr 2020 00:22:26 +0900
Norihiro Tanaka <[email-masked]> wrote:

> 
> On Fri, 17 Apr 2020 10:24:42 +0900
> Norihiro Tanaka <[email-masked]> wrote:
> 
> > 
> > On Fri, 17 Apr 2020 09:35:36 +0900
> > Norihiro Tanaka <[email-masked]> wrote:
> > 
> > > 
> > > On Thu, 16 Apr 2020 16:00:29 -0700
> > > Paul Eggert <[email-masked]> wrote:
> > > 
> > > > On 4/16/20 3:53 PM, Norihiro Tanaka wrote:
> > > > 
> > > > > I have had no idea to solve the problem yet.  If we revert it, bug#33357
> > > > > will come back.
> > > > 
> > > > Yes, I'd rather not revert if we can help it.
> > > > 
> > > > My own thought was to not analyze the regular expression if we discover that the input is empty. :-)
> > > 
> > > Now, I have a idea, it is that we build indexes of epsilon nodes
> > > including in follows before remove epsilon nodes.
> > 
> > 
> > I wrote fix for the bug, but it will be slower then at grep 2.27 yet.
> 
> It was improved previous patch.

Sorry, correct patch is here.
From 8357fa551c8a5a4f14540b250bc2485c4812a234 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Fri, 17 Apr 2020 10:12:01 +0900
Subject: [PATCH] dfa: build auxiliary indexes before remove epsilon closure

When remove epsilon closure, so far searched nodes including epsilon closure
in all nodes sequentially, but it is slow for some cases.  Now build
auxiliary indexes before search.

Problem reported in: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=40634

* lib/dfa.c (epsclosure): build auxiliary indexes before remove epsilon
closure.
---
 lib/dfa.c |  129 +++++++++++++++++++++++++++++++++++++++++++++----------------
 1 files changed, 95 insertions(+), 34 deletions(-)

diff --git a/lib/dfa.c b/lib/dfa.c
index 9939d22..5f90a92 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -2298,45 +2298,106 @@ static void
 epsclosure (struct dfa const *d)
 {
   position_set tmp;
+  idx_t *currs, *backs;
+  idx_t ncurr = 0;
+  position_set *prevs;
+
   alloc_position_set (&tmp, d->nleaves);
+  currs = xnmalloc (d->nleaves, sizeof *currs);
+  backs = xnmalloc (d->tindex, sizeof *backs);
+
   for (idx_t i = 0; i < d->tindex; i++)
-    if (d->follows[i].nelem > 0 && d->tokens[i] >= NOTCHAR
-        && d->tokens[i] != BACKREF && d->tokens[i] != ANYCHAR
-        && d->tokens[i] != MBCSET && d->tokens[i] < CSET)
-      {
-        unsigned int constraint;
-        switch (d->tokens[i])
-          {
-          case BEGLINE:
-            constraint = BEGLINE_CONSTRAINT;
-            break;
-          case ENDLINE:
-            constraint = ENDLINE_CONSTRAINT;
-            break;
-          case BEGWORD:
-            constraint = BEGWORD_CONSTRAINT;
-            break;
-          case ENDWORD:
-            constraint = ENDWORD_CONSTRAINT;
-            break;
-          case LIMWORD:
-            constraint = LIMWORD_CONSTRAINT;
-            break;
-          case NOTLIMWORD:
-            constraint = NOTLIMWORD_CONSTRAINT;
-            break;
-          default:
-            constraint = NO_CONSTRAINT;
-            break;
-          }
+    {
+      if (d->follows[i].nelem > 0 && d->tokens[i] >= NOTCHAR
+          && d->tokens[i] != ANYCHAR && d->tokens[i] != BEG
+          && d->tokens[i] != BACKREF && d->tokens[i] != MBCSET
+          && d->tokens[i] < CSET)
+        {
+          currs[ncurr] = i;
+          backs[i] = ncurr++;
+        }
+      else
+        backs[i] = -1;
+    }
 
-        delete (i, &d->follows[i]);
+  prevs = xnmalloc (ncurr, sizeof *prevs);
 
-        for (idx_t j = 0; j < d->tindex; j++)
-          if (i != j && d->follows[j].nelem > 0)
-            replace (&d->follows[j], i, &d->follows[i], constraint, &tmp);
-      }
+  for (idx_t i = 0; i < ncurr; i++)
+    {
+      prevs[i].elems = NULL;
+      prevs[i].nelem = 0;
+    }
+
+  for (idx_t i = 0; i < d->tindex; i++)
+    {
+      for (idx_t j = 0, k = 0; j < d->follows[i].nelem && k < ncurr;)
+        {
+          if (d->follows[i].elems[j].index < currs[k])
+            j++;
+          else if (currs[k] < d->follows[i].elems[j].index)
+            k++;
+          else
+            {
+              if (currs[k] != i)
+                {
+                  position p;
+                  p.index = i;
+                  p.constraint = NO_CONSTRAINT;
+                  if (prevs[k].nelem == 0)
+                    alloc_position_set (&prevs[k], 1);
+                  insert (p, &prevs[k]);
+                }
+              j++;
+              k++;
+            }
+        }
+    }
+
+  for (idx_t i = 0; i < ncurr; i++)
+    {
+      unsigned int constraint;
+      switch (d->tokens[currs[i]])
+        {
+        case BEGLINE:
+          constraint = BEGLINE_CONSTRAINT;
+          break;
+        case ENDLINE:
+          constraint = ENDLINE_CONSTRAINT;
+          break;
+        case BEGWORD:
+          constraint = BEGWORD_CONSTRAINT;
+          break;
+        case ENDWORD:
+          constraint = ENDWORD_CONSTRAINT;
+          break;
+        case LIMWORD:
+          constraint = LIMWORD_CONSTRAINT;
+          break;
+        case NOTLIMWORD:
+          constraint = NOTLIMWORD_CONSTRAINT;
+          break;
+        default:
+          constraint = NO_CONSTRAINT;
+          break;
+        }
+
+      delete (currs[i], &d->follows[currs[i]]);
+
+      for (idx_t j = 0; j < prevs[i].nelem; j++)
+        replace (&d->follows[prevs[i].elems[j].index], currs[i],
+                 &d->follows[currs[i]], constraint, &tmp);
+      for (idx_t j = 0; j < d->follows[currs[i]].nelem; j++)
+        if (backs[d->follows[currs[i]].elems[j].index] >= 0)
+          replace (&prevs[backs[d->follows[currs[i]].elems[j].index]],
+                   currs[i], &prevs[i], NO_CONSTRAINT, &tmp);
+    }
+
+  for (idx_t i = 0; i < ncurr; i++)
+    free (prevs[i].elems);
+  free (prevs);
   free (tmp.elems);
+  free (currs);
+  free (backs);
 }
 
 /* Returns the set of contexts for which there is at least one
-- 
1.7.1