Subject: bug#21696: closed (Re: bug#21696: [PATCH 1/2] grep: improvement of performance of grep -Fw)

From: [email-masked] (GNU bug Tracking System)
Date: Sat, 17 Oct 2015 05:49:02 +0000

Your bug report

#21696: [PATCH 1/2] grep: improvement of performance of grep -Fw

which was filed against the grep package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to [email-masked].

-- 
21696: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=21696
GNU Bug Tracking System
Contact [email-masked] with problems

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

Subject: [PATCH 1/2] grep: improvement of performance of grep -Fw
From: Norihiro Tanaka <[email-masked]>
To: <[email-masked]>
Date: Sat, 17 Oct 2015 10:13:36 +0900
List-Id: <debbugs-submit.debbugs.gnu.org>

I found that grep -Fw is extremely slow in spite of whether in
multibyte locales or not.

$ yes 'abcdefg hijklmn opqrstu vwxyz' | head -100000 >k
$ time -p env LC_ALL=C grep -Fw vwxy k
real 14.03
user 12.51
sys 0.74
$ time -p env LC_ALL=ja_JP.eucJP grep -Fw vwxy k
real 14.29
user 12.67
sys 0.50

$ time -p env LC_ALL=C grep -w vwxy k
real 0.11
user 0.01
sys 0.09
$ time -p env LC_ALL=ja_JP.eucJP grep -w vwxy k
real 0.89
user 0.71
sys 0.15

First patch fixes the problem.  Second patch changes as using grep
matcher for grep -Fw in single byte locales.

In single byte locales, DFA (not regex) is also used for words matching,
and it is very fast as above result.
From 7f693ddf06280a0e638f97a1810d454c20c62716 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Tue, 13 Oct 2015 09:42:57 +0900
Subject: [PATCH 1/2] grep: improvement of performance of grep -Fw

grep -Fw examines whether previous character is not word character or
not after matching from a head of buffer.  It is extremely slow.  Now,
if grep found potential match, seeks 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.4.6

From f43fe791dd4aa8f2ca079ed461349f24de32276a Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Tue, 13 Oct 2015 09:19:10 +0900
Subject: [PATCH 2/2] grep: use grep matcher for grep -Fw in single byte
 locales

In in single byte locales, KWset and DFA are used for words matching by
grep.  It is faster than kwset matcher, as kwset matcher calls kwsexec
many times until matches words.  So we use grep matcher for grep -Fw
in single byte locales.

* 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.4.6