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

[Jim Meyering]

On Mon, Dec 26, 2016 at 1:06 PM, Norihiro Tanaka <address@hidden> wrote:
>
> On Fri, 23 Dec 2016 17:38:42 -0800
> Paul Eggert <address@hidden> 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

That took 7 seconds for me.

Here is one that is O(N^2) in the length of the literal search string:
(the search strings are sequences of '0's, with lengths from 10k.. 320k):

$ n=10000; for i in $(seq 6); do env time -f "$n %e" src/grep -f
<(printf %0${n}d 0) <<<1; ((n *= 2)); done
10000 0.44
20000 1.44
40000 5.41
80000 21.27
160000 97.27
320000 426.72