bug#22239: bug#22357: grep -f not only huge memory usage, but also huge time cost

[Paul Eggert]

Norihiro Tanaka wrote:
> are you aware of extreme slowdown in the following cases after third patch?
>
>   yes $(printf %040d 0) | head -10000000 >inp
>   printf '0\n1\n' >pat
>   env LC_ALL=C src/grep -w -f pat inp

No. Thanks, I hadn't considered that possibility. I looked into the slowdown and 
installed the attached patches, which cause 'grep' to run about as fast on this 
test case as grep 2.25 (though not as fast as grep 2.26). The main fix is in 
patch 5. On my platform:

  -------grep version------
   v2.25  v2.26  v2.27 master     locale      command
    1.21   0.69  24.95   1.22     C           grep -w -f pat inp
  207.36 203.15 202.03   1.22     en_US.utf8  grep -w -f pat inp
    1.21   0.69  25.95   0.85     C           grep -w -f pat inp -F
   66.33  68.07  67.21   1.22     en_US.utf8  grep -w -f pat inp -F

All numbers are user+system CPU seconds on Fedora 24 x86-64 (AMD Phenom II X4 
910e). "master" means after the attached patches are installed.

Perhaps we can fiddle with the heuristics a bit so that v2.26 is not 
significantly faster than the master in the C locale.

0001-maint-rewrite-to-avoid-some-macros.patch
Description: Text Data

0002-grep-remove-C-label.patch
Description: Text Data

0003-grep-simplify-Fexecute.patch
Description: Text Data

0004-grep-specialize-word-finding-functions.patch
Description: Text Data

0005-grep-speed-up-wf-in-C-locale.patch
Description: Text Data

0006-grep-standardize-on-localeinfo.multibyte.patch
Description: Text Data

0007-grep-improve-word-checking-with-UTF-8.patch
Description: Text Data

0008-grep-fix-comment-in-searchutils.c.patch
Description: Text Data