Norihiro Tanaka wrote:
Sorry, I forgot to send the patch. We need the patch to optimize MERGE
function to speed-up for some cases.
Thanks, that improved the performance of the 'grep -vf linux.words linux.words'
benchmark from (before the recent changes) real 8.06 user 6.20 sys 1.85 to
(after) real 2.57 user 2.11 sys 0.45.
I installed it (with minor tweaks to the ChangeLog) into gnulib master and
updated the grep master accordingly. I'll CC: this email to bug-gnulib to give
them a heads-up, attaching the revised patch.
>From 617a6097466d818e425609eff9ed85039aea25db Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <nori...@kcn.ne.jp>
Date: Wed, 19 Sep 2018 08:35:49 -0700
Subject: [PATCH] dfa: optimization for state merge
* lib/dfa.c (merge2): New function.
(merge_nfa_state): Use it.
---
ChangeLog | 6 ++++++
lib/dfa.c | 18 ++++++++++++++++--
2 files changed, 22 insertions(+), 2 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index 181039c1a..b9d7b30d6 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+2018-09-19 Norihiro Tanaka <nori...@kcn.ne.jp>
+
+ dfa: optimization for state merge
+ * lib/dfa.c (merge2): New function.
+ (merge_nfa_state): Use it.
+
2018-09-18 Jim Meyering <meyer...@fb.com>
dfa: trivial comment fix: s/is/if/
diff --git a/lib/dfa.c b/lib/dfa.c
index 13b2a0baf..d04bcbe64 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -2102,6 +2102,21 @@ merge (position_set const *s1, position_set const *s2, position_set *m)
merge_constrained (s1, s2, -1, m);
}
+static void
+merge2 (position_set *dst, position_set const *src, position_set *m)
+{
+ if (src->nelem < 4)
+ {
+ for (ptrdiff_t i = 0; i < src->nelem; ++i)
+ insert (src->elems[i], dst);
+ }
+ else
+ {
+ merge (src, dst, m);
+ copy (m, dst);
+ }
+}
+
/* Delete a position from a set. Return the nonzero constraint of the
deleted position, or zero if there was no such position. */
static unsigned int
@@ -2388,8 +2403,7 @@ merge_nfa_state (struct dfa *d, size_t *queue, ptrdiff_t nqueue, size_t tindex,
if (flags[sindex] & OPT_REPEAT)
delete (sindex, &follows[sindex]);
- merge (&follows[dindex], &follows[sindex], merged);
- copy (merged, &follows[dindex]);
+ merge2 (&follows[dindex], &follows[sindex], merged);
/* Mark it as pruned in future. */
follows[tindex].elems[j].constraint = 0;
--
2.17.1
