>From a185ed4e6341b5c6aab3e3d950aafeae9eafe4cc Mon Sep 17 00:00:00 2001 From: Paul Eggert 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 + + 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 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