Hi,
dfa matcher is not good at matching for long patterns as following.
seq -f '%g bottles of beer on the wall' 2400 >in
env LC_ALL=C src/grep -vf in in
In fact, for this case GNU grep is considerably slower than ripgrep
which is released recently. I think that it is cased by some reasons
and one of them is in memory allocation.
This patch checks number of states in beginning of dfa execution, and if
there are a lot of states, release them. it can not only save memory,
but may improve performance, as when the number of the state becomes
large, it takes time to find the same state from caches of states.
Thanks.
Norihiro
From 9f7d39e943187196b68a42d2880dfea9ad6c1d94 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <nori...@kcn.ne.jp>
Date: Mon, 10 Oct 2016 23:08:29 +0900
Subject: [PATCH] dfa: save memory for states
* src/dfa (dfaexec_main): Beginning of dfa execution, release caches of
states if dfa has a lot of caches.
---
lib/dfa.c | 33 +++++++++++++++++++++++++++++++++
1 files changed, 33 insertions(+), 0 deletions(-)
diff --git a/lib/dfa.c b/lib/dfa.c
index c4dc626..744a9f1 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -3105,6 +3105,39 @@ dfaexec_main (struct dfa *d, char const *begin, char
*end, bool allow_nl,
unsigned char saved_end;
size_t nlcount = 0;
+ if (MAX_TRCOUNT <= d->sindex)
+ {
+ for (s = d->min_trcount; s < d->sindex; s++)
+ {
+ free (d->states[s].elems.elems);
+ free (d->states[s].mbps.elems);
+ }
+ d->sindex = d->min_trcount;
+
+ if (d->trans)
+ {
+ for (s = 0; s < d->tralloc; s++)
+ {
+ free (d->trans[s]);
+ free (d->fails[s]);
+ d->trans[s] = d->fails[s] = NULL;
+ }
+ d->trcount = 0;
+ }
+
+ if (d->localeinfo.multibyte && d->mb_trans)
+ {
+ for (s = -1; s < d->tralloc; s++)
+ {
+ free (d->mb_trans[s]);
+ d->mb_trans[s] = NULL;
+ }
+ for (s = 0; s < d->min_trcount; s++)
+ d->states[s].mb_trindex = -1;
+ d->mb_trcount = 0;
+ }
+ }
+
if (!d->tralloc)
{
realloc_trans_if_necessary (d, 1);
--
1.7.1
