Subject: bug#16823: closed (Re: bug#16823: Use DFA regex engine on fgrep matcher)

From: [email-masked] (GNU bug Tracking System)
Date: Mon, 24 Mar 2014 01:19:02 +0000

Your bug report

#16823: Use DFA regex engine on fgrep matcher

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].

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

Subject: Re: bug#16823: Use DFA regex engine on fgrep matcher
From: Paul Eggert <[email-masked]>
To: Norihiro Tanaka <[email-masked]>, [email-masked]
Date: Sun, 23 Mar 2014 18:18:34 -0700
List-Id: <debbugs-submit.debbugs.gnu.org>

Thanks, I pushed your patch (with a minor change to make it integrate 
with the latest grep) and then pushed some fixes and one major 
simplification: don't have any special case for "grep -iF PAT" when PAT 
contains no alphabetics.  This is rare enough that I expect it's not 
worth complicating grep to worry about it.

I'm attaching the combined patch, that is the merge of your patch plus 
my changes.
diff --git a/src/grep.c b/src/grep.c
index 475cb1a..a1bccdb 100644
--- a/src/grep.c
+++ b/src/grep.c
@@ -1904,6 +1904,45 @@ parse_grep_colors (void)
    ? (*(s) = wctob ((wint_t) (wc)), 1) \
    : wcrtomb (s, wc, ps))
 
+/* Change a pattern for fgrep into grep.  */
+static void
+fgrep_to_grep_pattern (size_t len, char const *keys,
+                       size_t *new_len, char **new_keys)
+{
+  char *p = *new_keys = xnmalloc (len + 1, 2);
+  mbstate_t mb_state = { 0 };
+  size_t n;
+
+  for (; len; keys += n, len -= n)
+    {
+      wchar_t wc;
+      n = MBRTOWC (&wc, keys, len, &mb_state);
+      switch (n)
+        {
+        case (size_t) -2:
+          n = len;
+          /* Fall through.  */
+        default:
+          p = mempcpy (p, keys, n);
+          break;
+
+        case (size_t) -1:
+          memset (&mb_state, 0, sizeof mb_state);
+          /* Fall through.  */
+        case 1:
+          *p = '\\';
+          p += strchr ("$*.[\\^", *keys) != NULL;
+          /* Fall through.  */
+        case 0:
+          *p++ = *keys;
+          n = 1;
+          break;
+        }
+    }
+
+  *new_len = p - *new_keys;
+}
+
 /* If the newline-separated regular expressions, KEYS (with length, LEN
    and no trailing NUL byte), are amenable to transformation into
    otherwise equivalent case-ignoring ones, perform the transformation,
@@ -2379,6 +2418,21 @@ main (int argc, char **argv)
   else
     usage (EXIT_TROUBLE);
 
+  /* If case-insensitive fgrep in a multibyte locale, improve
+     performance by using grep instead.  */
+  if (match_icase && compile == Fcompile && MB_CUR_MAX > 1)
+    {
+      size_t new_keycc;
+      char *new_keys;
+      fgrep_to_grep_pattern (keycc, keys, &new_keycc, &new_keys);
+      free (keys);
+      keys = new_keys;
+      keycc = new_keycc;
+      matcher = "grep";
+      compile = Gcompile;
+      execute = EGexecute;
+    }
+
   /* Case-insensitive matching is expensive in multibyte locales
      because a few characters may change size when converted to upper
      or lower case.  To accommodate those, search the input one line

Subject: Use DFA regex engine on fgrep matcher
From: Norihiro Tanaka <[email-masked]>
To: [email-masked]
Date: Thu, 20 Feb 2014 22:26:35 +0900
List-Id: <debbugs-submit.debbugs.gnu.org>

Package: grep
Tags: patch

In recent years, grep matcher is very fast by improving the dfa engine.
On the other hands, fgrep matcher only uses kwset engine, which isn't
generally very good at for case-insensitive matching.

The patch enables to switch case-insensitive matching with fgrep matcher
into one with grep matcher, which can use DFA engine, make --ignore-case
(-i) with fgrep master faster (about 30-40x) in UTF locale.

- Before the patch

$ yes $(printf '%078dm' 0)| head -1000000 | tr 0 a > in
$ for i in 1 2 3 4 5; do env LC_ALL=en_US.UTF-8 time src/fgrep -i 'n' in; done
Command exited with non-zero status 1
6.06user 2.23system 0:08.59elapsed 96%CPU (0avgtext+0avgdata 2624maxresident)k
0inputs+0outputs (0major+188minor)pagefaults 0swaps
Command exited with non-zero status 1
6.23user 2.15system 0:08.64elapsed 97%CPU (0avgtext+0avgdata 2608maxresident)k
0inputs+0outputs (0major+187minor)pagefaults 0swaps
Command exited with non-zero status 1
6.83user 1.44system 0:08.47elapsed 97%CPU (0avgtext+0avgdata 2608maxresident)k
0inputs+0outputs (0major+187minor)pagefaults 0swaps
Command exited with non-zero status 1
7.35user 1.25system 0:08.77elapsed 98%CPU (0avgtext+0avgdata 2624maxresident)k
0inputs+0outputs (0major+188minor)pagefaults 0swaps
Command exited with non-zero status 1
7.60user 0.63system 0:08.48elapsed 97%CPU (0avgtext+0avgdata 2608maxresident)k
0inputs+0outputs (0major+187minor)pagefaults 0swaps

- After the patch

$ yes $(printf '%078dm' 0)| head -1000000 | tr 0 a > in
$ for i in 1 2 3 4 5; do env LC_ALL=en_US.UTF-8 time src/fgrep -i 'n' in; done
Command exited with non-zero status 1
0.19user 0.10system 0:00.30elapsed 97%CPU (0avgtext+0avgdata 2976maxresident)k
0inputs+0outputs (0major+210minor)pagefaults 0swaps
Command exited with non-zero status 1
0.16user 0.06system 0:00.22elapsed 99%CPU (0avgtext+0avgdata 2976maxresident)k
0inputs+0outputs (0major+210minor)pagefaults 0swaps
Command exited with non-zero status 1
0.18user 0.04system 0:00.23elapsed 95%CPU (0avgtext+0avgdata 2976maxresident)k
0inputs+0outputs (0major+210minor)pagefaults 0swaps
Command exited with non-zero status 1
0.15user 0.07system 0:00.23elapsed 96%CPU (0avgtext+0avgdata 2976maxresident)k
0inputs+0outputs (0major+210minor)pagefaults 0swaps
Command exited with non-zero status 1
0.17user 0.04system 0:00.24elapsed 93%CPU (0avgtext+0avgdata 2976maxresident)k
0inputs+0outputs (0major+210minor)pagefaults 0swaps

Norihiro