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

[Paul Eggert]

On 12/12/2016 03:49 AM, Bruno Haible wrote:
> > Part of the
> > problem appears to be that position-set merging, even with his latest proposed
> > changes, is O(N**2) where N is the pattern size....
> I'm confused. Which code are you talking about?

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.


> So, the larger the two input files, the larger the relative time eaten by
> 'dfastate'. IMO this means the bottleneck is 'dfastate'.

Yes, there is a bottleneck there. I haven't had time yet to investigate 
more.