Subject: bug#21763: closed (Re: bug#22357: grep -f not only huge memory usage, but also huge time cost)

From: [email-masked] (GNU bug Tracking System)
Date: Wed, 21 Dec 2016 06:46:02 +0000

Your bug report

#21763: poor performance since grep 2.19 when comparing files with grep

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

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

Subject: Re: bug#22357: grep -f not only huge memory usage, but also huge time cost
From: Paul Eggert <[email-masked]>
To: [email-masked], [email-masked]
Cc: Norihiro Tanaka <[email-masked]>, sur-behoffski <[email-masked]>, "L.A. Walsh" <[email-masked]>, Jim Meyering <[email-masked]>, "Bennett, Steve" <[email-masked]>, JQK <[email-masked]>, [email-masked], [email-masked], Trevor Cordes <[email-masked]>, Paul Jackson <[email-masked]>, Bruno Haible <[email-masked]>,Ondřej Cífka <[email-masked]>, Bruce Dubbs <[email-masked]>
Date: Tue, 20 Dec 2016 21:17:01 -0800
List-Id: <debbugs-submit.debbugs.gnu.org>

I installed the attached patches into grep master. These fix the performance 
regressions noted at the start of Bug#22357. I see that the related performance 
problems noted in Bug#21763 seem to be fixed too, I expect because of Norihiro 
Tanaka's recent changes, so I'll boldly close both bug reports.

To some extent the attached patches restore the old behavior for grep -F, when 
grep is given two or more patterns. The patch doesn't change the underlying 
algorithms; it merely uses a different heuristic to decide whether to use the -F 
matcher. Although I wouldn't be surprised if the attached patches hurt 
performance in some cases, I didn't uncover any such cases in my performance 
testing, which I admit mostly consisted of running the examples in the 
abovementioned bug reports.

I'll leave Bug#22239 open, as I get the following performance figures 
(user+system CPU time) for the Bug#22239 benchmark, where list.txt is created by 
"aspell dump master | head -n 100000 >list.txt", and the grep commands all use 
the operands "-F -f list.txt /etc/passwd" in the en_US.utf8 locale on Fedora 24 
x86-64.

   no -i       -i       grep version
    0.25      0.33      2.16
    0.26     10.95      2.21
    0.11      2.90*     current master (including attached patches)

In the C locale, the current grep master is always significantly faster than 
grep 2.16 or 2.21 on the benchmark, so the only significant problem is the 
number marked "*". I ran the benchmarks on an AMD Phenom II X4 910e.
From 75bca3ca0a6ea87a66531ab7c0f8859e1d6c4300 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Tue, 20 Dec 2016 08:56:06 -0800
Subject: [PATCH 1/3] grep: simplify line counting in patterns

* src/grep.c (n_patterns): Rename from patfile_lineno,
as it is now origin-zero.  Now size_t, not uintmax_t.
(count_nl_bytes, fl_add): Simplify to just buffer and size.
All callers changed.
---
 src/grep.c | 49 ++++++++++++++++++++-----------------------------
 1 file changed, 20 insertions(+), 29 deletions(-)

diff --git a/src/grep.c b/src/grep.c
index 30e0f54..76f83d5 100644
--- a/src/grep.c
+++ b/src/grep.c
@@ -104,46 +104,35 @@ static size_t n_fl_pair_slots;
    and any command-line argument that serves as a regular expression.  */
 static size_t n_pattern_files;
 
-/* Given the concatenation of all patterns, one per line, be they
-   specified via -e, a lone command-line argument or -f, this is the
-   number of the first line of each entity, in that concatenation.
+/* The number of patterns seen so far.
    It is advanced by fl_add and, when needed, used in pattern_file_name
    to derive a file-relative line number.  */
-static uintmax_t patfile_lineno = 1;
+static size_t n_patterns;
 
-/* Return the number of newline bytes in BUF starting at offset BEG
-   and up to and not including offset END.  */
+/* Return the number of newline bytes in BUF with size SIZE.  */
 static size_t _GL_ATTRIBUTE_PURE
-count_nl_bytes (char const *buf, size_t beg, size_t end)
+count_nl_bytes (char const *buf, size_t size)
 {
-  char const *p = buf + beg;
-  char const *end_p = buf + end;
-  uintmax_t n = 0;
-  while (true)
-    {
-      p = memchr (p, '\n', end_p - p);
-      if (!p)
-        break;
-      p++;
-      n++;
-    }
+  char const *p = buf;
+  char const *end_p = buf + size;
+  size_t n = 0;
+  while ((p = memchr (p, '\n', end_p - p)))
+    p++, n++;
   return n;
 }
 
-/* Append a FILENAME,line-number pair to FL_PAIR.  The line number we save
-   with FILENAME is the initial value of the global PATFILE_LINENO.
-   PATFILE_LINENO is then incremented by the number of newlines in BUF
-   from offset BEG up to but not including offset END.  */
+/* Append a FILENAME,line-number pair to FL_PAIR, and update
+   pattern-related counts from the contents of BUF with SIZE bytes.  */
 static void
-fl_add (char const *buf, size_t beg, size_t end, char const *filename)
+fl_add (char const *buf, size_t size, char const *filename)
 {
   if (n_fl_pair_slots <= n_pattern_files)
     fl_pair = x2nrealloc (fl_pair, &n_fl_pair_slots, sizeof *fl_pair);
 
-  fl_pair[n_pattern_files].lineno = patfile_lineno;
+  fl_pair[n_pattern_files].lineno = n_patterns + 1;
   fl_pair[n_pattern_files].filename = filename;
   n_pattern_files++;
-  patfile_lineno += count_nl_bytes (buf, beg, end);
+  n_patterns += count_nl_bytes (buf, size);
 }
 
 /* Map the line number, LINENO, of one of the input patterns to the
@@ -2521,10 +2510,11 @@ main (int argc, char **argv)
             keyalloc = keycc + cc + 1;
             keys = x2realloc (keys, &keyalloc);
           }
-        memcpy (&keys[keycc], optarg, cc);
+        oldcc = keycc;
+        memcpy (keys + oldcc, optarg, cc);
         keycc += cc;
         keys[keycc++] = '\n';
-        fl_add (keys, keycc - cc - 1, keycc, "");
+        fl_add (keys + oldcc, cc + 1, "");
         break;
 
       case 'f':
@@ -2548,7 +2538,7 @@ main (int argc, char **argv)
         /* Append final newline if file ended in non-newline. */
         if (oldcc != keycc && keys[keycc - 1] != '\n')
           keys[keycc++] = '\n';
-        fl_add (keys, oldcc, keycc, xstrdup (optarg));
+        fl_add (keys + oldcc, keycc - oldcc, optarg);
         break;
 
       case 'h':
@@ -2741,7 +2731,8 @@ main (int argc, char **argv)
       /* Make a copy so that it can be reallocated or freed later.  */
       keycc = strlen (argv[optind]);
       keys = xmemdup (argv[optind++], keycc + 1);
-      fl_add (keys, 0, keycc, "");
+      fl_add (keys, keycc, "");
+      n_patterns++;
     }
   else
     usage (EXIT_TROUBLE);
-- 
2.7.4

From 214be13d33a26ab45231afe8e983d9a174aae282 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Tue, 20 Dec 2016 08:56:06 -0800
Subject: [PATCH 2/3] grep: simplify matcher configuration

* src/grep.c (matcher, compile): Remove static vars.
(compile_fp_t): Now takes a 3rd syntax argument.
(Gcomppile, Ecompile, Acompile, GAcompile, PAcompile): Remove.
(struct matcher): Now nameless, since it is used only once.
Make 'name' a bit shorter.  New member 'syntax'.
(matchers): Initialize it, and change removed functions to GEAcompile.
(F_MATCHER_INDEX, G_MATCHER_INDEX): New constants.
(setmatcher): New arg MATCHER, and return new matcher index.
Avoid unnecessary call to strcmp.
(main): Keep matcher as a local int, not a global pointer.
* src/kwsearch.c (Fcompile):
* src/pcresearch.c (Pcompile): Ignore the 3rd syntax argument.
---
 src/grep.c       | 111 +++++++++++++++++++------------------------------------
 src/kwsearch.c   |   2 +-
 src/pcresearch.c |   2 +-
 src/search.h     |   4 +-
 4 files changed, 41 insertions(+), 78 deletions(-)

diff --git a/src/grep.c b/src/grep.c
index 76f83d5..574a380 100644
--- a/src/grep.c
+++ b/src/grep.c
@@ -491,8 +491,6 @@ bool match_words;
 bool match_lines;
 char eolbyte;
 
-static char const *matcher;
-
 /* For error messages. */
 /* The input file name, or (if standard input) null or a --label argument.  */
 static char const *filename;
@@ -577,9 +575,8 @@ static bool seek_failed;
 static bool seek_data_failed;
 
 /* Functions we'll use to search. */
-typedef void (*compile_fp_t) (char const *, size_t);
+typedef void (*compile_fp_t) (char const *, size_t, reg_syntax_t);
 typedef size_t (*execute_fp_t) (char const *, size_t, size_t *, char const *);
-static compile_fp_t compile;
 static execute_fp_t execute;
 
 static char const *
@@ -2019,70 +2016,36 @@ if any error occurs and -q is not given, the exit status is 2.\n"));
 
 /* Pattern compilers and matchers.  */
 
-static void
-Gcompile (char const *pattern, size_t size)
-{
-  GEAcompile (pattern, size, RE_SYNTAX_GREP);
-}
-
-static void
-Ecompile (char const *pattern, size_t size)
-{
-  GEAcompile (pattern, size, RE_SYNTAX_EGREP);
-}
-
-static void
-Acompile (char const *pattern, size_t size)
-{
-  GEAcompile (pattern, size, RE_SYNTAX_AWK);
-}
-
-static void
-GAcompile (char const *pattern, size_t size)
-{
-  GEAcompile (pattern, size, RE_SYNTAX_GNU_AWK);
-}
-
-static void
-PAcompile (char const *pattern, size_t size)
-{
-  GEAcompile (pattern, size, RE_SYNTAX_POSIX_AWK);
-}
-
-struct matcher
+static struct
 {
-  char const name[16];
+  char const name[12];
+  int syntax; /* used if compile == GEAcompile */
   compile_fp_t compile;
   execute_fp_t execute;
+} const matchers[] = {
+  { "grep", RE_SYNTAX_GREP, GEAcompile, EGexecute },
+  { "egrep", RE_SYNTAX_EGREP, GEAcompile, EGexecute },
+  { "fgrep", 0, Fcompile, Fexecute, },
+  { "awk", RE_SYNTAX_AWK, GEAcompile, EGexecute },
+  { "gawk", RE_SYNTAX_GNU_AWK, GEAcompile, EGexecute },
+  { "posixawk", RE_SYNTAX_POSIX_AWK, GEAcompile, EGexecute },
+  { "perl", 0, Pcompile, Pexecute, },
 };
-static struct matcher const matchers[] = {
-  { "grep",      Gcompile, EGexecute },
-  { "egrep",     Ecompile, EGexecute },
-  { "fgrep",     Fcompile,  Fexecute },
-  { "awk",       Acompile, EGexecute },
-  { "gawk",     GAcompile, EGexecute },
-  { "posixawk", PAcompile, EGexecute },
-  { "perl",      Pcompile,  Pexecute },
-  { "", NULL, NULL },
-};
+/* Keep these in sync with the 'matchers' table.  */
+enum { F_MATCHER_INDEX = 2, G_MATCHER_INDEX = 0 };
 
-/* Set the matcher to M if available.  Exit in case of conflicts or if
-   M is not available.  */
-static void
-setmatcher (char const *m)
+/* Return the index of the matcher corresponding to M if available.
+   MATCHER is the index of the previous matcher, or -1 if none.
+   Exit in case of conflicts or if M is not available.  */
+static int
+setmatcher (char const *m, int matcher)
 {
-  struct matcher const *p;
-
-  if (matcher && !STREQ (matcher, m))
-    die (EXIT_TROUBLE, 0, _("conflicting matchers specified"));
-
-  for (p = matchers; p->compile; p++)
-    if (STREQ (m, p->name))
+  for (int i = 0; i < sizeof matchers / sizeof *matchers; i++)
+    if (STREQ (m, matchers[i].name))
       {
-        matcher = p->name;
-        compile = p->compile;
-        execute = p->execute;
-        return;
+        if (0 <= matcher && matcher != i)
+          die (EXIT_TROUBLE, 0, _("conflicting matchers specified"));
+        return i;
       }
 
   die (EXIT_TROUBLE, 0, _("invalid matcher %s"), m);
@@ -2367,6 +2330,7 @@ main (int argc, char **argv)
 {
   char *keys = NULL;
   size_t keycc = 0, oldcc, keyalloc = 0;
+  int matcher = -1;
   bool with_filenames = false;
   size_t cc;
   int opt, prepended;
@@ -2409,9 +2373,6 @@ main (int argc, char **argv)
     error (0, 0, _("warning: GREP_OPTIONS is deprecated;"
                    " please use an alias or script"));
 
-  compile = matchers[0].compile;
-  execute = matchers[0].execute;
-
   while (prev_optind = optind,
          (opt = get_nondigit_option (argc, argv, &default_context)) != -1)
     switch (opt)
@@ -2440,23 +2401,23 @@ main (int argc, char **argv)
         break;
 
       case 'E':
-        setmatcher ("egrep");
+        matcher = setmatcher ("egrep", matcher);
         break;
 
       case 'F':
-        setmatcher ("fgrep");
+        matcher = setmatcher ("fgrep", matcher);
         break;
 
       case 'P':
-        setmatcher ("perl");
+        matcher = setmatcher ("perl", matcher);
         break;
 
       case 'G':
-        setmatcher ("grep");
+        matcher = setmatcher ("grep", matcher);
         break;
 
       case 'X': /* undocumented on purpose */
-        setmatcher (optarg);
+        matcher = setmatcher (optarg, matcher);
         break;
 
       case 'H':
@@ -2794,24 +2755,26 @@ main (int argc, char **argv)
 
   initialize_unibyte_mask ();
 
+  if (matcher < 0)
+    matcher = G_MATCHER_INDEX;
+
   /* 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) the pattern has an encoding error (where fgrep might not work), or
      (2) case is ignored and a fast fgrep ignore-case is not available.  */
-  if (compile == Fcompile
+  if (matcher == F_MATCHER_INDEX
       && (MB_CUR_MAX <= 1
           ? match_words
           : (contains_encoding_error (keys, keycc)
              || (match_icase && !fgrep_icase_available (keys, keycc)))))
     {
       fgrep_to_grep_pattern (&keys, &keycc);
-      matcher = "grep";
-      compile = Gcompile;
-      execute = EGexecute;
+      matcher = G_MATCHER_INDEX;
     }
 
-  compile (keys, keycc);
+  execute = matchers[matcher].execute;
+  matchers[matcher].compile (keys, keycc, matchers[matcher].syntax);
   free (keys);
   /* We need one byte prior and one after.  */
   char eolbytes[3] = { 0, eolbyte, 0 };
diff --git a/src/kwsearch.c b/src/kwsearch.c
index c3e69b3..7275973 100644
--- a/src/kwsearch.c
+++ b/src/kwsearch.c
@@ -34,7 +34,7 @@ wordchar (wint_t wc)
 static kwset_t kwset;
 
 void
-Fcompile (char const *pattern, size_t size)
+Fcompile (char const *pattern, size_t size, reg_syntax_t ignored)
 {
   size_t total = size;
 
diff --git a/src/pcresearch.c b/src/pcresearch.c
index 108baff..0e34861 100644
--- a/src/pcresearch.c
+++ b/src/pcresearch.c
@@ -88,7 +88,7 @@ static int empty_match[2];
 #endif
 
 void
-Pcompile (char const *pattern, size_t size)
+Pcompile (char const *pattern, size_t size, reg_syntax_t ignored)
 {
 #if !HAVE_LIBPCRE
   die (EXIT_TROUBLE, 0,
diff --git a/src/search.h b/src/search.h
index 4957a63..1ff5be2 100644
--- a/src/search.h
+++ b/src/search.h
@@ -57,11 +57,11 @@ extern void GEAcompile (char const *, size_t, reg_syntax_t);
 extern size_t EGexecute (char const *, size_t, size_t *, char const *);
 
 /* kwsearch.c */
-extern void Fcompile (char const *, size_t);
+extern void Fcompile (char const *, size_t, reg_syntax_t);
 extern size_t Fexecute (char const *, size_t, size_t *, char const *);
 
 /* pcresearch.c */
-extern void Pcompile (char const *, size_t);
+extern void Pcompile (char const *, size_t, reg_syntax_t);
 extern size_t Pexecute (char const *, size_t, size_t *, char const *);
 
 /* Return the number of bytes in the character at the start of S, which
-- 
2.7.4

From 290ca116c9172d97b2b026951fac722d3bd3ced9 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Tue, 20 Dec 2016 18:04:39 -0800
Subject: [PATCH 3/3] grep: fix performance with multiple patterns

Problem reported by Jaroslav Skarvada (Bug#22357).
* NEWS: Document this and other recent performance fixes.
* src/grep.c (E_MATCHER_INDEX): New constant.
(all_single_byte_after_folding):
New function, split out from fgrep_icase_available.
(fgrep_icase_available): Use it.
(try_fgrep_pattern): New function, which also uses it.
(main): With two or more patterns, use try_fgrep_pattern to fix
performance regression.  The number "two" here is just a heuristic.
---
 NEWS       |  11 ++++++
 src/grep.c | 132 +++++++++++++++++++++++++++++++++++++++++++++++++++----------
 2 files changed, 123 insertions(+), 20 deletions(-)

diff --git a/NEWS b/NEWS
index aa0483b..2e7d1ae 100644
--- a/NEWS
+++ b/NEWS
@@ -8,6 +8,17 @@ GNU grep NEWS                                    -*- outline -*-
   /proc file system and standard output is /dev/null.
   [bug introduced in grep-2.27]
 
+** Bug fixes
+
+  Fix performance regression with multiple patterns, e.g., for -Fi in
+  a multi-byte locale, or for -Fw in a single-byte locale.
+  [bugs introduced in grep-2.19, grep-2.22 and grep-2.26]
+
+** Improvements
+
+  Improve performance for -E or -G pattern lists that are easily
+  converted to -F format.
+
 
 * Noteworthy changes in release 2.27 (2016-12-06) [stable]
 
diff --git a/src/grep.c b/src/grep.c
index 574a380..f36654c 100644
--- a/src/grep.c
+++ b/src/grep.c
@@ -2032,7 +2032,7 @@ static struct
   { "perl", 0, Pcompile, Pexecute, },
 };
 /* Keep these in sync with the 'matchers' table.  */
-enum { F_MATCHER_INDEX = 2, G_MATCHER_INDEX = 0 };
+enum { E_MATCHER_INDEX = 1, F_MATCHER_INDEX = 2, G_MATCHER_INDEX = 0 };
 
 /* Return the index of the matcher corresponding to M if available.
    MATCHER is the index of the previous matcher, or -1 if none.
@@ -2245,23 +2245,12 @@ contains_encoding_error (char const *pat, size_t patlen)
   return false;
 }
 
-/* Return true if the fgrep pattern PAT, of size PATLEN, matches only
-   single-byte characters including case folding, and so is suitable
-   to be converted to a grep pattern.  */
+/* Return true if the set of single-byte characters USED contains only
+   characters whose case counterparts are also single-byte.  */
 
 static bool
-fgrep_icase_available (char const *pat, size_t patlen)
+all_single_byte_after_folding (bool used[UCHAR_MAX + 1])
 {
-  bool used[UCHAR_MAX + 1] = { 0, };
-
-  for (size_t i = 0; i < patlen; i++)
-    {
-      unsigned char c = pat[i];
-      if (localeinfo.sbctowc[c] == WEOF)
-        return false;
-      used[c] = true;
-    }
-
   for (int c = 0; c <= UCHAR_MAX; c++)
     if (used[c])
       {
@@ -2281,6 +2270,26 @@ fgrep_icase_available (char const *pat, size_t patlen)
   return true;
 }
 
+/* Return true if the -F patterns PAT, of size PATLEN, match only
+   single-byte characters including case folding, and so can be
+   processed by the -F matcher even if -i is given.  */
+
+static bool
+fgrep_icase_available (char const *pat, size_t patlen)
+{
+  bool used[UCHAR_MAX + 1] = { 0, };
+
+  for (size_t i = 0; i < patlen; i++)
+    {
+      unsigned char c = pat[i];
+      if (localeinfo.sbctowc[c] == WEOF)
+        return false;
+      used[c] = true;
+    }
+
+  return all_single_byte_after_folding (used);
+}
+
 /* Change the pattern *KEYS_P, of size *LEN_P, from fgrep to grep style.  */
 
 static void
@@ -2325,6 +2334,84 @@ fgrep_to_grep_pattern (char **keys_p, size_t *len_p)
   *len_p = p - new_keys;
 }
 
+/* If it is easy, convert the MATCHER-style patterns KEYS (of size
+   *LEN_P) to -F style, update *LEN_P to a possibly-smaller value, and
+   return F_MATCHER_INDEX.  If not, leave KEYS and *LEN_P alone and
+   return MATCHER.  This function is conservative and sometimes misses
+   conversions, e.g., it does not convert the -E pattern "(a|a|[aa])"
+   to the -F pattern "a".  */
+
+static int
+try_fgrep_pattern (int matcher, char *keys, size_t *len_p)
+{
+  int result = matcher;
+  size_t len = *len_p;
+  char *new_keys = xmalloc (len + 1);
+  char *p = new_keys;
+  mbstate_t mb_state = { 0 };
+  size_t mblen_lim = match_icase ? 1 : -3;
+  bool used[UCHAR_MAX + 1] = { 0, };
+
+  while (len != 0)
+    {
+      switch (*keys)
+        {
+        case '$': case '*': case '.': case '[': case '^':
+          goto fail;
+
+        case '(': case '+': case '?': case '{': case '|':
+          if (matcher != G_MATCHER_INDEX)
+            goto fail;
+          break;
+
+        case '\\':
+          if (1 < len)
+            switch (keys[1])
+              {
+              case '\n':
+              case 'B': case 'S': case 'W': case'\'': case '<':
+              case 'b': case 's': case 'w': case '`': case '>':
+              case '1': case '2': case '3': case '4':
+              case '5': case '6': case '7': case '8': case '9':
+                goto fail;
+
+              case '(': case '+': case '?': case '{': case '|':
+                if (matcher == G_MATCHER_INDEX)
+                  goto fail;
+                /* Fall through.  */
+              default:
+                keys++, len--;
+                break;
+              }
+          break;
+        }
+
+      {
+        size_t n = mb_clen (keys, len, &mb_state);
+        if (mblen_lim < n)
+          goto fail;
+        used[to_uchar (keys[0])] = true;
+        p = mempcpy (p, keys, n);
+        keys += n;
+        len -= n;
+      }
+    }
+
+  if (mblen_lim == 1 && !all_single_byte_after_folding (used))
+    goto fail;
+
+  if (*len_p != p - new_keys)
+    {
+      *len_p = p - new_keys;
+      memcpy (keys, new_keys, p - new_keys);
+    }
+  result = F_MATCHER_INDEX;
+
+ fail:
+  free (new_keys);
+  return result;
+}
+
 int
 main (int argc, char **argv)
 {
@@ -2758,11 +2845,11 @@ main (int argc, char **argv)
   if (matcher < 0)
     matcher = G_MATCHER_INDEX;
 
-  /* 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) the pattern has an encoding error (where fgrep might not work), or
-     (2) case is ignored and a fast fgrep ignore-case is not available.  */
+  /* In a single-byte locale, switch from -F to -G if it is a single
+     pattern that matches words, where -G is typically faster.  In a
+     multi-byte locale, switch if the patterns have an encoding error
+     (where -F does not work) or if -i and the patterns will not work
+     for -iF.  */
   if (matcher == F_MATCHER_INDEX
       && (MB_CUR_MAX <= 1
           ? match_words
@@ -2772,6 +2859,11 @@ main (int argc, char **argv)
       fgrep_to_grep_pattern (&keys, &keycc);
       matcher = G_MATCHER_INDEX;
     }
+  /* With two or more patterns, if -F works then switch from either -E
+     or -G, as -F is probably faster then.  */
+  else if ((matcher == G_MATCHER_INDEX || matcher == E_MATCHER_INDEX)
+           && 1 < n_patterns)
+    matcher = try_fgrep_pattern (matcher, keys, &keycc);
 
   execute = matchers[matcher].execute;
   matchers[matcher].compile (keys, keycc, matchers[matcher].syntax);
-- 
2.7.4

Subject: poor performance since grep 2.19 when comparing files with grep
From: "Bennett, Steve" <[email-masked]>
To: "[email-masked]" <[email-masked]>
Date: Mon, 26 Oct 2015 12:54:01 +0000
List-Id: <debbugs-submit.debbugs.gnu.org>

Apologies in advance if this is more of a "discuss" question, but it looks like a particular use-case shows a marked change in performance between recent versions of grep.

A colleague mentioned a performance issue with grep to me, and its puzzling me a bit.
It turns out that he was using "grep -Fvif" to find lines in one file that are not present in another.

Up until grep 2.18 this seems to work with linear performance and it takes less than 50ms to compare files up to about 20,000 lines.
With grep 2.19 and later, ever relatively small files are quite slow, runtime (and memory use) increases exponentially (e.g. 300ms to compare 200 lines, 1.5s to compare 400 lines, 5s to compare 600 lines).

I've shown my colleague how to use sort and diff (and "comm", which I think is vastly underrated), but it made me wonder if this is a reasonable thing to expect grep to be able to do, and whether such a performance drop should be seen as a bug.

The way he was using it, he had two (unsorted) data sets (about 6000 rows in each), with most lines being common, and he was just using:
    grep -Fvif FILE1 FILE2
In his case, the older version of grep took way less than a second to run, but after he had upgraded his machine it took 20 minutes before running out of swap and seg faulting. 

In terms of comparing performance, I've found that the following works to compare performance (vary N to try different sized data files):
    N=600; F=/tmp/zz.$$; seq -f '%g bottles of beer on the wall' 1 $N > $F; time grep -Fvif $F $F; rm $F

Steve.