Subject: Re: bug#38223: grep >=2.28 cannot handle -wF correctly under LANG=ja_JP.eucjp

From: Norihiro Tanaka <[email-masked]>
Date: Sun, 17 Nov 2019 09:01:21 +0900

On Sat, 16 Nov 2019 11:00:38 -0800
Jim Meyering <[email-masked]> wrote:

> I've pushed the complete fix here:
> https://git.savannah.gnu.org/cgit/grep.git/commit/?id=090a4dbe03951e427f03f83be424caacc3303799
> 
> I've also fixed the comment and a variable name and updated gnulib to latest.

After patched, I found extreamly slowdown.

  yes $(printf %040d 0) | head -1000000 >k
  time -p env LC_ALL=ja_JP.eucjp src/grep -F -w 0 k

First patch fixes it, and second improves performance more.
From 0202a83b3d0de224a5d606958e3719244d546548 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Sun, 17 Nov 2019 07:20:41 +0900
Subject: [PATCH 1/2] grep: fix performance degration with previous patch

* src/kwsearch.c (Fexecute): Avoid unnecessary backwards in non-UTF8
multibyte locales.
---
 src/kwsearch.c |   15 ++++++++++++---
 1 files changed, 12 insertions(+), 3 deletions(-)

diff --git a/src/kwsearch.c b/src/kwsearch.c
index 5edff79..f590d19 100644
--- a/src/kwsearch.c
+++ b/src/kwsearch.c
@@ -224,9 +224,18 @@ Fexecute (void *vcp, char const *buf, size_t size, size_t *match_size,
         goto success;
 
       /* We need a preceding mb_start pointer.  Use the beginning of line
-         if there is a preceding newline, else BUF.  */
-      char const *nl = memrchr (mb_start, eol, beg - mb_start);
-      mb_start = nl ? nl + 1 : buf;
+         if there is a preceding newline.  */
+      if (mb_check)
+        {
+           char const *nl = memrchr (buf, eol, beg - buf);
+           mb_start = nl ? nl + 1 : buf;
+        }
+      else
+        {
+           char const *nl = memrchr (mb_start, eol, beg - mb_start);
+           if (nl)
+             mb_start = nl + 1;
+        }
 
       /* Succeed if neither the preceding nor the following character is a
          word constituent.  If the preceding is not, yet the following
-- 
1.7.1

From 7c6990b6818e2dec89c5415673a112293598c0b8 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Sun, 17 Nov 2019 07:29:15 +0900
Subject: [PATCH 2/2] grep: performance improvement for grep -F -w in non-UTF8 multibyte locales

* src/searchutils.c (mb_goback): Add argument. All callers changed.
* src/search.h (mb_goback): Update prototype.
* src/kwsearch.c (Fexecute): Use output from mb_goback when check
word-boundary.
---
 src/dfasearch.c   |    2 +-
 src/kwsearch.c    |   15 ++++++++-------
 src/search.h      |    3 ++-
 src/searchutils.c |   13 +++++++++----
 4 files changed, 20 insertions(+), 13 deletions(-)

diff --git a/src/dfasearch.c b/src/dfasearch.c
index 3ebd25e..6c95d8c 100644
--- a/src/dfasearch.c
+++ b/src/dfasearch.c
@@ -279,7 +279,7 @@ EGexecute (void *vdc, char const *buf, size_t size, size_t *match_size,
                     goto success;
                   if (mb_start < beg)
                     mb_start = beg;
-                  if (mb_goback (&mb_start, match, buflim) == 0)
+                  if (mb_goback (&mb_start, NULL, match, buflim) == 0)
                     goto success;
                   /* The matched line starts in the middle of a multibyte
                      character.  Perform the DFA search starting from the
diff --git a/src/kwsearch.c b/src/kwsearch.c
index f590d19..442efc1 100644
--- a/src/kwsearch.c
+++ b/src/kwsearch.c
@@ -161,6 +161,7 @@ Fexecute (void *vcp, char const *buf, size_t size, size_t *match_size,
   bool longest;
   struct kwsearch *kwsearch = vcp;
   kwset_t kwset = kwsearch->kwset;
+  size_t mbclen;
 
   if (match_lines)
     mb_check = longest = false;
@@ -194,7 +195,9 @@ Fexecute (void *vcp, char const *buf, size_t size, size_t *match_size,
           return EGexecute (kwsearch->re, buf, size, match_size, start_ptr);
         }
 
-      if (mb_check && mb_goback (&mb_start, beg + offset, buf + size) != 0)
+      mbclen = 0;
+      if (mb_check
+          && mb_goback (&mb_start, &mbclen, beg + offset, buf + size) != 0)
         {
           /* We have matched a single byte that is not at the beginning of a
              multibyte character.  mb_goback has advanced MB_START past that
@@ -225,12 +228,7 @@ Fexecute (void *vcp, char const *buf, size_t size, size_t *match_size,
 
       /* We need a preceding mb_start pointer.  Use the beginning of line
          if there is a preceding newline.  */
-      if (mb_check)
-        {
-           char const *nl = memrchr (buf, eol, beg - buf);
-           mb_start = nl ? nl + 1 : buf;
-        }
-      else
+      if (mbclen == 0)
         {
            char const *nl = memrchr (mb_start, eol, beg - mb_start);
            if (nl)
@@ -241,6 +239,9 @@ Fexecute (void *vcp, char const *buf, size_t size, size_t *match_size,
          word constituent.  If the preceding is not, yet the following
          character IS a word constituent, keep trying with shorter matches.  */
       if (! wordchar_prev (mb_start, beg, buf + size))
+      if (mbclen > 0
+          ? ! wordchar_next (beg - mbclen, buf + size)
+          : ! wordchar_prev (mb_start, beg, buf + size))
         for (;;)
           {
             if (! wordchar_next (beg + len, buf + size))
diff --git a/src/search.h b/src/search.h
index a782a0c..d6010b9 100644
--- a/src/search.h
+++ b/src/search.h
@@ -52,7 +52,8 @@ extern size_t wordchars_size (char const *, char const *) _GL_ATTRIBUTE_PURE;
 extern size_t wordchar_next (char const *, char const *) _GL_ATTRIBUTE_PURE;
 extern size_t wordchar_prev (char const *, char const *, char const *)
   _GL_ATTRIBUTE_PURE;
-extern ptrdiff_t mb_goback (char const **, char const *, char const *);
+extern ptrdiff_t mb_goback (char const **, size_t *, char const *,
+                            char const *);
 
 /* dfasearch.c */
 extern void *GEAcompile (char *, size_t, reg_syntax_t);
diff --git a/src/searchutils.c b/src/searchutils.c
index 9bb35fd..abe86dd 100644
--- a/src/searchutils.c
+++ b/src/searchutils.c
@@ -83,10 +83,12 @@ kwsinit (bool mb_trans)
    END if there is no such boundary.  When returning a negative value,
    leave *MB_START alone.  */
 ptrdiff_t
-mb_goback (char const **mb_start, char const *cur, char const *end)
+mb_goback (char const **mb_start, size_t *mbclen, char const *cur,
+           char const *end)
 {
   const char *p = *mb_start;
   const char *p0 = p;
+  size_t clen;
 
   if (cur <= p)
     return cur - p;
@@ -94,13 +96,14 @@ mb_goback (char const **mb_start, char const *cur, char const *end)
   if (localeinfo.using_utf8)
     {
       p = cur;
+      clen = 1;
 
       if (cur < end && (*cur & 0xc0) == 0x80)
         for (int i = 1; i <= 3; i++)
           if ((cur[-i] & 0xc0) != 0x80)
             {
               mbstate_t mbs = { 0 };
-              size_t clen = mb_clen (cur - i, end - (cur - i), &mbs);
+              clen = mb_clen (cur - i, end - (cur - i), &mbs);
               if (i < clen && clen < (size_t) -2)
                 {
                   p0 = cur - i;
@@ -114,7 +117,7 @@ mb_goback (char const **mb_start, char const *cur, char const *end)
       mbstate_t mbs = { 0 };
       do
         {
-          size_t clen = mb_clen (p, end - p, &mbs);
+          clen = mb_clen (p, end - p, &mbs);
 
           if ((size_t) -2 <= clen)
             {
@@ -130,6 +133,8 @@ mb_goback (char const **mb_start, char const *cur, char const *end)
     }
 
   *mb_start = p;
+  if (mbclen)
+    *mbclen = clen;
   return p == cur ? 0 : cur - p0;
 }
 
@@ -192,6 +197,6 @@ wordchar_prev (char const *buf, char const *cur, char const *end)
       || (localeinfo.using_utf8 && localeinfo.sbclen[b] != -2))
     return sbwordchar[b];
   char const *p = buf;
-  cur -= mb_goback (&p, cur, end);
+  cur -= mb_goback (&p, NULL, cur, end);
   return wordchar_next (cur, end);
 }
-- 
1.7.1