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

[Paul Eggert]

address@hidden wrote:
> I'm sure that Paul and Jim would welcome patches.
I wrote a patch that prefers -F when the input looks like a troublesome case. It 
merely uses heuristics though, nothing scientific like what Bruno Haible suggested.
Before installing anything like that, I'd first like to look into improving the 
DFA performance, along the lines suggested by Norhiro Tanaka. 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. Perhaps we should change the 
representation of position sets to use simple arrays; although this would take 
more space, merging would be O(N) and the code would surely be simpler.