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

[Norihiro Tanaka]

On Sun, 18 Dec 2016 23:48:10 -0800
Paul Eggert <address@hidden> wrote:

> >> '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.
> 
> I looked into it some more. Your patch looks like a win so I
> installed it; thanks. Also, I improved the worst-case performance for
> 'replace' from O(N*(N + log N)) to O(N log N), by installing the
> attached patch. I also bumped grep's gnulib version so that it gets
> this patch.
> 
> This doesn't address the main problem in this area, as 'grep' is
> still pretty slow with lots of multiple patterns. However, one step
> at a time.

Thanks.

BTW, What case do you the worst?  One more I think previous 'replace' is
not O(N*(N + log N)) but O(N + N log N) i.e. O(N log N) .

> This doesn't address the main problem in this area, as 'grep' is still
> pretty slow with lots of multiple patterns. However, one step at a time.

Yes, I think slowness with lots of multiple patterns is caused by two
reasons mainly.

 1. dfa is not optimize parsed patterns.

    For example, dfa does not replace pattern 'a \|a \|a \| ... \|a \|b'
    to 'a \|b'.

    I tried it several times, have not succeeded it yet.

 2. grep matcher compiles regex always to check syntax of a pattern,
    even when it is not used in searching.

    I also tried it, have not succeeded it yet.