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 <egg...@cs.ucla.edu>
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 <egg...@cs.ucla.edu>
+
+ 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 <egg...@cs.ucla.edu>
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
