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

[Norihiro Tanaka]

On Wed, 14 Dec 2016 17:19:27 -0800
Paul Eggert <address@hidden> wrote:

> I was referring to code with his proposed patch installed. 'delete' is
> O(N); 'replace' calls 'delete' in a loop and is therefore O(N**2).
> 'epsclosure' calls 'replace' in a loop and so I suppose it is O(N**3).
> I haven't looked into how likely the worst-case performance is, though.

Yes.  It is same both before and after with my proposed patch, but It
seems that memset() for VISITED causes slowdown in before code.  So it
may extremely depress efficiency of memory cache, although there is no
basis.

- before

$ time -p env LC_ALL=C src/grep -F -w -f /usr/share/dict/linux.words /dev/null
real 188.98
user 188.46
sys 0.33

- after

$ time -p env LC_ALL=C src/grep -F -w -f /usr/share/dict/linux.words /dev/null
real 2.19
user 1.84
sys 0.34