Patch#17230 causes slowdown for a case to repeat failure in DFA after
success in kwset, although it improves the performance for many cases.
In fact, the master without this patch is 3.5x slower than grep 2.18 for
below.
$ yes abcdabc | head -50000000 >k
$ env LC_ALL=C time -p src/grep -i 'abcd.bd' k
This patch fixes the degradation of the performance for such cases. See
the commit log for details.
Norihiro
From b33b48e630759bdc5b3bc95dc477eb2ee489960c Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email protected]>
Date: Sat, 26 Apr 2014 18:19:32 +0900
Subject: [PATCH] grep: speed up for a case to repeat failure in DFA after
success in kwset
When `multibyte' attribute of struct dfa is false and the pattern doesn't
have BACKREF, DFA is much faster, although it isn't fast as kwset in most
of cases. Therefore, when repeat failure in DFA after success in kwset
as following, it may be lower than starting with DFA without kwset.
yes abcdabc | head -50000000 >k
env LC_ALL=C time -p src/grep -i 'abcd.bd' k
This patch improves the performance for such cases.
I measured the performance without application of the patch for above
case.
real 4.86 user 4.19 sys 0.70
Subsequently, I applied the patch, and recompiled and measured the
performance.
real 1.34 user 0.85 sys 0.47
* src/dfa.c (dfaisfast): New function. It return true, if `multibyte'
attribute of struct dfa is false and the pattern doesn't have BACKREF.
* src/dfa.h (dfaisfast): New decl.
* src/dfasearch.c (EGexecute): Use dfaisfast.
---
src/dfa.c | 22 ++++++++++++++++++++++
src/dfa.h | 4 ++++
src/dfasearch.c | 15 ++++++++++-----
3 files changed, 36 insertions(+), 5 deletions(-)
diff --git a/src/dfa.c b/src/dfa.c
index 8e6c708..fc638c8 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -3411,6 +3411,28 @@ dfahint (struct dfa *d, char const *begin, char *end,
size_t *count)
}
}
+bool
+dfaisfast (struct dfa *d)
+{
+ size_t i;
+ if (d->superset)
+ {
+ for (i = 0; i < d->superset->tindex; i++)
+ if (d->superset->tokens[i] == BACKREF)
+ return false;
+ return true;
+ }
+ else if (!d->multibyte)
+ {
+ for (i = 0; i < d->tindex; i++)
+ if (d->tokens[i] == BACKREF)
+ return false;
+ return true;
+ }
+ else
+ return false;
+}
+
static void
free_mbdata (struct dfa *d)
{
diff --git a/src/dfa.h b/src/dfa.h
index 60aff11..2dd4871 100644
--- a/src/dfa.h
+++ b/src/dfa.h
@@ -82,6 +82,10 @@ extern char *dfaexec (struct dfa *d, char const *begin, char
*end,
extern size_t dfahint (struct dfa *d, char const *begin, char *end,
size_t *count);
+/* Return true, if `multibyte' attribute of struct dfa is false and the
+ pattern doesn't have BACKREF. */
+extern bool dfaisfast (struct dfa *);
+
/* Free the storage held by the components of a struct dfa. */
extern void dfafree (struct dfa *);
diff --git a/src/dfasearch.c b/src/dfasearch.c
index dc76397..79a0cd8 100644
--- a/src/dfasearch.c
+++ b/src/dfasearch.c
@@ -213,6 +213,7 @@ EGexecute (char const *buf, size_t size, size_t *match_size,
size_t len, best_len;
struct kwsmatch kwsm;
size_t i;
+ bool dfafast = dfaisfast (dfa);
mb_start = buf;
buflim = buf + size;
@@ -232,13 +233,13 @@ EGexecute (char const *buf, size_t size, size_t
*match_size,
beg += offset;
/* Narrow down to the line containing the candidate, and
run it through DFA. */
- end = memchr (beg, eol, buflim - beg);
- end = end ? end + 1 : buflim;
match = beg;
beg = memrchr (buf, eol, beg - buf);
beg = beg ? beg + 1 : buf;
if (kwsm.index < kwset_exact_matches)
{
+ end = memchr (beg, eol, buflim - beg);
+ end = end ? end + 1 : buflim;
if (MB_CUR_MAX == 1)
goto success;
if (mb_start < beg)
@@ -253,17 +254,21 @@ EGexecute (char const *buf, size_t size, size_t
*match_size,
&backref))
continue;
}
- else
+ else if (!dfafast)
{
+ /* Narrow down to the line we've found if dfa isn't fast. */
+ end = memchr (match, eol, buflim - beg);
+ end = end ? end + 1 : buflim;
if (dfahint (dfa, beg, (char *) end, NULL) == (size_t) -1)
continue;
if (! dfaexec (dfa, beg, (char *) end, 0, NULL, &backref))
continue;
}
}
- else
+ if (!kwset || dfafast)
{
- /* No good fixed strings; start with DFA. */
+ /* No good fixed strings or DFA is fast; start with DFA
+ broadly. */
size_t offset, count;
char const *next_beg;
count = 0;
--
1.9.2
