Thanks for those performance improvements. I installed them, with some minor
changes to commentary. I also installed a couple of minor tweaks to the code, to
use memrchr and to simplify the multibyte test. Attached are the revised set of
patches.
From a341e981fec14f3a76e88bca3e40fdbc98539cf8 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <nori...@kcn.ne.jp>
Date: Tue, 13 Oct 2015 09:42:57 +0900
Subject: [PATCH 1/5] grep: improve performance of grep -Fw
* src/kwsearch.c (Fexecute): grep -Fw examined whether the previous
character is a word character after matching from the head of the
buffer. It is extremely slow. Now, if grep found a potential match,
it looks for the previous newline, and examines from there.
---
src/kwsearch.c | 6 +++++-
1 file changed, 5 insertions(+), 1 deletion(-)
diff --git a/src/kwsearch.c b/src/kwsearch.c
index 5a91eb6..045ef46 100644
--- a/src/kwsearch.c
+++ b/src/kwsearch.c
@@ -124,7 +124,11 @@ Fexecute (char const *buf, size_t size, size_t *match_size,
if (match_words)
for (try = beg; ; )
{
- if (wordchar (mb_prev_wc (buf, try, buf + size)))
+ char const *bol;
+ bol = beg;
+ while (buf < bol && bol[-1] != eol)
+ --bol;
+ if (wordchar (mb_prev_wc (bol, try, buf + size)))
break;
if (wordchar (mb_next_wc (try + len, buf + size)))
{
--
2.1.4
From b7fc3ad6f999a02e534b1a196bb46db3c4d71452 Mon Sep 17 00:00:00 2001
From: Paul Eggert <egg...@cs.ucla.edu>
Date: Fri, 16 Oct 2015 22:26:10 -0700
Subject: [PATCH 2/5] grep: use memchr/memrchar
* src/kwsearch.c (Fexecute): Prefer memchr and memrchr to doing it
by hand.
---
src/kwsearch.c | 16 ++++++----------
1 file changed, 6 insertions(+), 10 deletions(-)
diff --git a/src/kwsearch.c b/src/kwsearch.c
index 045ef46..2997ae1 100644
--- a/src/kwsearch.c
+++ b/src/kwsearch.c
@@ -124,10 +124,8 @@ Fexecute (char const *buf, size_t size, size_t *match_size,
if (match_words)
for (try = beg; ; )
{
- char const *bol;
- bol = beg;
- while (buf < bol && bol[-1] != eol)
- --bol;
+ char const *bol = memrchr (buf, eol, beg - buf);
+ bol = bol ? bol + 1 : buf;
if (wordchar (mb_prev_wc (bol, try, buf + size)))
break;
if (wordchar (mb_next_wc (try + len, buf + size)))
@@ -153,12 +151,10 @@ Fexecute (char const *buf, size_t size, size_t
*match_size,
return -1;
success:
- if ((end = memchr (beg + len, eol, (buf + size) - (beg + len))) != NULL)
- end++;
- else
- end = buf + size;
- while (buf < beg && beg[-1] != eol)
- --beg;
+ end = memchr (beg + len, eol, (buf + size) - (beg + len));
+ end = end ? end + 1 : buf + size;
+ beg = memrchr (buf, eol, beg - buf);
+ beg = beg ? beg + 1 : buf;
len = end - beg;
success_in_beg_and_len:;
size_t off = beg - buf;
--
2.1.4
From cb6a695c8507ee35bf2d2236445bc0941112e38a Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <nori...@kcn.ne.jp>
Date: Tue, 13 Oct 2015 09:19:10 +0900
Subject: [PATCH 3/5] grep: use grep matcher for grep -Fw when unibyte
In single byte locales with grep -Fw, prefer the grep matcher to the
kwset matcher, as the former uses KWset and a DFA, whereas the latter
calls kwsexec many times until it matches a word.
* src/grep.c (main): Change pattern for fgrep into grep for grep -Fw in
single byte locales.
---
src/grep.c | 9 ++++++---
1 file changed, 6 insertions(+), 3 deletions(-)
diff --git a/src/grep.c b/src/grep.c
index d8ea70f..0ca0d9a 100644
--- a/src/grep.c
+++ b/src/grep.c
@@ -2563,9 +2563,12 @@ main (int argc, char **argv)
/* If fgrep in a multibyte locale, then use grep if either
(1) case is ignored (where grep is typically faster), or
- (2) the pattern has an encoding error (where fgrep might not work). */
- if (compile == Fcompile && MB_CUR_MAX > 1
- && (match_icase || contains_encoding_error (keys, keycc)))
+ (2) the pattern matches words (where grep is typically faster), or
+ (3) the pattern has an encoding error (where fgrep might not work). */
+ if (compile == Fcompile
+ && (MB_CUR_MAX > 1 && (match_icase
+ || contains_encoding_error (keys, keycc)))
+ || (MB_CUR_MAX == 1 && match_words))
{
size_t new_keycc;
char *new_keys;
--
2.1.4
From 37d7b0a2bfb30d6c1c113029c2b6d2b4e045d145 Mon Sep 17 00:00:00 2001
From: Paul Eggert <egg...@cs.ucla.edu>
Date: Fri, 16 Oct 2015 22:39:51 -0700
Subject: [PATCH 4/5] grep: simplify previous change
* src/grep.c (main): Simplify recently-changed grep -Fw test.
---
src/grep.c | 13 +++++++------
1 file changed, 7 insertions(+), 6 deletions(-)
diff --git a/src/grep.c b/src/grep.c
index 0ca0d9a..2c5e09a 100644
--- a/src/grep.c
+++ b/src/grep.c
@@ -2561,14 +2561,15 @@ main (int argc, char **argv)
build_mbclen_cache ();
init_easy_encoding ();
- /* If fgrep in a multibyte locale, then use grep if either
+ /* In a unibyte locale, switch from fgrep to grep if
+ the pattern matches words (where grep is typically faster).
+ In a multibyte locale, switch from fgrep to grep if either
(1) case is ignored (where grep is typically faster), or
- (2) the pattern matches words (where grep is typically faster), or
- (3) the pattern has an encoding error (where fgrep might not work). */
+ (2) the pattern has an encoding error (where fgrep might not work). */
if (compile == Fcompile
- && (MB_CUR_MAX > 1 && (match_icase
- || contains_encoding_error (keys, keycc)))
- || (MB_CUR_MAX == 1 && match_words))
+ && (MB_CUR_MAX <= 1
+ ? match_words
+ : match_icase || contains_encoding_error (keys, keycc)))
{
size_t new_keycc;
char *new_keys;
--
2.1.4
From 0ee838142a5183757425ef0f4d3c034c5448dc00 Mon Sep 17 00:00:00 2001
From: Paul Eggert <egg...@cs.ucla.edu>
Date: Fri, 16 Oct 2015 22:46:41 -0700
Subject: [PATCH 5/5] maint: add news item
* NEWS: Document grep -Fw speedup.
---
NEWS | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
diff --git a/NEWS b/NEWS
index fa4d9a1..91db25d 100644
--- a/NEWS
+++ b/NEWS
@@ -32,7 +32,8 @@ GNU grep NEWS -*- outline
-*-
command-line arguments, not against command-line components.
[bug introduced in grep-2.6]
- Performance has improved for patterns containing very long strings.
+ Performance has improved for patterns containing very long strings,
+ and for grep -Fw in unibyte locales.
* Noteworthy changes in release 2.21 (2014-11-23) [stable]
--
2.1.4
