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

[Bruce Dubbs]

JQK wrote:

> 【without option "-F"】
> # env time grep -w -f <(seq 200000) <(shuf -i 1-200000 -n 250)
> :
> 288.77user 64.23system 10:35.71elapsed 55%CPU (0avgtext+0avgdata
> 3492784maxresident)k
> 8967032inputs+0outputs (154389major+1493890minor)pagefaults 0swaps

I certainly have different results.  There is a certain amount of 
randomization in the shuf command, but the elapsed time seems to be 
consistent.   I'll note that the first time I ran the command, some of the 
timing stats were significantly different, but I was unable to reproduce 
it.  It looks like the process takes about 12.5G of ram so the issue may 
be some memory allocation differences.

1st:

19.46user 1.18system 1:00.48elapsed 34%CPU (0avgtext+0avgdata 
12749612maxresident)k
224inputs+0outputs (1major+3194814minor)pagefaults 0swaps

Subsequent:

$ grep --version| head -n1
grep (GNU grep) 2.23

$ env time grep -w -f <(seq 200000) <(shuf -i 1-200000 -n 250)
...
55.52user 3.46system 0:58.99elapsed 99%CPU (0avgtext+0avgdata 
12655908maxresident)k
0inputs+0outputs (0major+3171385minor)pagefaults 0swaps

55.65user 3.34system 0:59.00elapsed 99%CPU (0avgtext+0avgdata 
12436972maxresident)k
0inputs+0outputs (0major+3116666minor)pagefaults 0swaps

> 【with option "-F"】
> # env time grep -F -w -f <(seq 200000) <(shuf -i 1-200000 -n 250)
> :
> 0.10user 0.01system 0:00.22elapsed 53%CPU (0avgtext+0avgdata
> 87856maxresident)k
> 0inputs+0outputs (0major+5534minor)pagefaults 0swaps

$ env time grep -F -w -f <(seq 200000) <(shuf -i 1-200000 -n 250)

57.76user 3.43system 1:01.21elapsed 99%CPU (0avgtext+0avgdata 
12686580maxresident)k
128inputs+0outputs (1major+3179052minor)pagefaults 0swaps

56.91user 3.43system 1:00.35elapsed 99%CPU (0avgtext+0avgdata 
12717860maxresident)k
0inputs+0outputs (0major+3186885minor)pagefaults 0swaps

  -- Bruce Dubbs
     LFS