>From cbf5523bd54a92c1d8ffeae4b629d2b82651f651 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Tue, 18 Sep 2018 18:24:27 -0700 Subject: [PATCH 2/4] dfa: prune states as we go * lib/dfa.c (prune): Remove. (merge_nfa_state): Prune as we go instead of at the end. Prefer ptrdiff_t for indexes, as this helps the compiler a bit. Simplify constraint checking a bit. --- ChangeLog | 5 +++++ lib/dfa.c | 49 ++++++++++++++++--------------------------------- 2 files changed, 21 insertions(+), 33 deletions(-) diff --git a/ChangeLog b/ChangeLog index 64926503a..bad8eda6d 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,6 +1,11 @@ 2018-09-18 Paul Eggert + dfa: prune states as we go + * lib/dfa.c (prune): Remove. dfa: reorder enum for efficiency + (merge_nfa_state): Prune as we go instead of at the end. + Prefer ptrdiff_t for indexes, as this helps the compiler a bit. + * lib/dfa.c (END): Now -1 again. Reorder other elements of the enumeration to make it easier for GCC to generate efficient code by using fewer comparisons to check for diff --git a/lib/dfa.c b/lib/dfa.c index 849645154..73bd6ca09 100644 --- a/lib/dfa.c +++ b/lib/dfa.c @@ -2129,22 +2129,6 @@ delete (size_t del, position_set *s) return 0; } -static void -prune (position_set *s) -{ - size_t d = 0; - - for (size_t i = 0; i < s->nelem; i++) - { - if (s->elems[i].constraint == 0) - continue; - - s->elems[d++] = s->elems[i]; - } - - s->nelem = d; -} - /* Replace a position with the followed set. */ static void replace (position_set *dst, size_t del, position_set *add, @@ -2362,17 +2346,20 @@ static size_t merge_nfa_state (struct dfa *d, size_t *queue, size_t nqueue, size_t tindex, int *flags, position_set *merged) { - size_t sindex; - size_t dindex; + position_set *follows = d->follows; + ptrdiff_t nelem = 0; - for (size_t i = 0; i < d->follows[tindex].nelem; i++) + for (ptrdiff_t i = 0; i < follows[tindex].nelem; i++) { - dindex = d->follows[tindex].elems[i].index; + size_t dindex = follows[tindex].elems[i].index; /* Skip the node as pruned in future. */ - if (d->follows[tindex].elems[i].constraint == 0) + unsigned int iconstraint = follows[tindex].elems[i].constraint; + if (iconstraint == 0) continue; + follows[tindex].elems[nelem++] = follows[tindex].elems[i]; + if (tindex < dindex && !(flags[dindex] & OPT_QUEUED)) { queue[nqueue++] = dindex; @@ -2382,11 +2369,11 @@ merge_nfa_state (struct dfa *d, size_t *queue, size_t nqueue, size_t tindex, if (flags[dindex] & (OPT_LPAREN | OPT_RPAREN)) continue; - for (size_t j = i + 1; j < d->follows[tindex].nelem; j++) + for (size_t j = i + 1; j < follows[tindex].nelem; j++) { - sindex = d->follows[tindex].elems[j].index; + size_t sindex = follows[tindex].elems[j].index; - if (d->follows[tindex].elems[j].constraint == 0) + if (follows[tindex].elems[j].constraint != iconstraint) continue; if (flags[sindex] & (OPT_LPAREN | OPT_RPAREN)) @@ -2395,25 +2382,21 @@ merge_nfa_state (struct dfa *d, size_t *queue, size_t nqueue, size_t tindex, if (d->tokens[sindex] != d->tokens[dindex]) continue; - if (d->follows[tindex].elems[i].constraint != - d->follows[tindex].elems[j].constraint) - continue; - if ((flags[sindex] ^ flags[dindex]) & OPT_REPEAT) continue; if (flags[sindex] & OPT_REPEAT) - delete (sindex, &d->follows[sindex]); + delete (sindex, &follows[sindex]); - merge (&d->follows[dindex], &d->follows[sindex], merged); - copy (merged, &d->follows[dindex]); + merge (&follows[dindex], &follows[sindex], merged); + copy (merged, &follows[dindex]); /* Mark it as pruned in future. */ - d->follows[tindex].elems[j].constraint = 0; + follows[tindex].elems[j].constraint = 0; } } - prune (&d->follows[tindex]); + follows[tindex].nelem = nelem; return nqueue; } -- 2.17.1