Subject: Re: bug#21696: [PATCH 1/2] grep: improvement of performance of grep -Fw
From: Paul Eggert <[email-masked]>
To: Norihiro Tanaka <[email-masked]>, [email-masked]
Date: Fri, 16 Oct 2015 22:48:07 -0700
List-Id: <debbugs-submit.debbugs.gnu.org>

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 <[email-masked]>
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 <[email-masked]>
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 <[email-masked]>
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 <[email-masked]>
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 <[email-masked]>
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