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

From: Paul Eggert <[email-masked]>
Date: Fri, 11 Sep 2020 16:01:01 -0700

> And here is the adjusted patch:

Hold on, that looks like a cleanup of the April 18 patch posted here:

https://bugs.gnu.org/40634#26

But there's a later patch dated April 19, which Norihiro Tanaka said should be 
more correct and simpler:

https://bugs.gnu.org/40634#32

I'll try to take a look at the later patch.
>From a185ed4e6341b5c6aab3e3d950aafeae9eafe4cc Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Fri, 11 Sep 2020 15:46:14 -0700
Subject: [PATCH] dfa: minor improvements of previous change

* lib/dfa.c (epsclosure): Use one xnmalloc call to allocate
CURRS and NEXTS, to lessen pressure on the heap allocator.
Assign unconditionally in a couple of places, to help branch
prediction.  Redo comparison order to help the compiler.
Omit unnecessary index variable J.
---
 ChangeLog |  9 +++++++++
 lib/dfa.c | 28 ++++++++++++++--------------
 2 files changed, 23 insertions(+), 14 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index bf39cc512..da75e4757 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,12 @@
+2020-09-11  Paul Eggert  <[email-masked]>
+
+	dfa: minor improvements of previous change
+	* lib/dfa.c (epsclosure): Use one xnmalloc call to allocate
+	CURRS and NEXTS, to lessen pressure on the heap allocator.
+	Assign unconditionally in a couple of places, to help branch
+	prediction.  Redo comparison order to help the compiler.
+	Omit unnecessary index variable J.
+
 2020-09-10  Paul Eggert  <[email-masked]>
 
 	canonicalize: fix pointer indexing bugs
diff --git a/lib/dfa.c b/lib/dfa.c
index c4300dfb5..df6399e45 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -2203,6 +2203,8 @@ replace (position_set *dst, idx_t del, position_set *add,
     }
 }
 
+/* Return true if any position in S has an index equal to any element
+   of ELEMS, which has NELEM elements.  */
 static bool _GL_ATTRIBUTE_PURE
 overwrap (position_set const *s, idx_t const *elems, idx_t nelem)
 {
@@ -2316,28 +2318,27 @@ static void
 epsclosure (struct dfa const *d)
 {
   position_set tmp;
-  idx_t *currs, *nexts;
   idx_t ncurr = 0;
   idx_t nnext = 0;
+  idx_t tindex = d->tindex;
 
   alloc_position_set (&tmp, d->nleaves);
-  currs = xnmalloc (d->tindex, sizeof *currs);
-  nexts = xnmalloc (d->tindex, sizeof *nexts);
 
-  for (idx_t i = 0; i < d->tindex; i++)
+  idx_t *currs = xnmalloc (tindex, 2 * sizeof *currs);
+  for (idx_t i = 0; i < 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)
-        currs[ncurr++] = i;
+      currs[ncurr] = i;
+      ncurr += (d->follows[i].nelem > 0
+                && NOTCHAR <= d->tokens[i] && d->tokens[i] < CSET
+                && d->tokens[i] != BACKREF && d->tokens[i] != ANYCHAR
+                && d->tokens[i] != MBCSET);
     }
 
-  for (idx_t i = 0, j = 0; i < d->tindex; i++)
+  idx_t *nexts = currs + ncurr;
+  for (idx_t i = 0; i < tindex; i++)
     {
-      while (j < ncurr && currs[j] < i)
-        j++;
-      if (overwrap (&d->follows[i], currs, ncurr))
-        nexts[nnext++] = i;
+      nexts[nnext] = i;
+      nnext += overwrap (&d->follows[i], currs, ncurr);
     }
 
   for (idx_t i = 0; i < ncurr; i++)
@@ -2377,7 +2378,6 @@ epsclosure (struct dfa const *d)
 
   free (tmp.elems);
   free (currs);
-  free (nexts);
 }
 
 /* Returns the set of contexts for which there is at least one
-- 
2.17.1