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

From: Norihiro Tanaka <[email-masked]>
Date: Mon, 26 Dec 2016 21:06:55 +0900

On Fri, 23 Dec 2016 17:38:42 -0800
Paul Eggert <[email-masked]> wrote:

> 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:

Hmm, how about the following test cases, although it is extreame?

$ cat pat
0
00 0
00 00 0
00 00 00 0
00 00 00 00 0
00 00 00 00 00 0
00 00 00 00 00 00 0
00 00 00 00 00 00 00 0
00 00 00 00 00 00 00 00 0
00 00 00 00 00 00 00 00 00 0
00 00 00 00 00 00 00 00 00 00 0
00 00 00 00 00 00 00 00 00 00 00 0
00 00 00 00 00 00 00 00 00 00 00 00 0
00 00 00 00 00 00 00 00 00 00 00 00 00 0
$ yes '00 00 00 00 00 00 00 00 00 00 00 00 00' |
  head -1000000 >inp
$ time -p env LC_ALL=C src/grep -w -f pat inp