|
From: | Paul Eggert |
Subject: | bug#22357: grep -f not only huge memory usage, but also huge time cost |
Date: | Sun, 11 Dec 2016 19:12:19 -0800 |
User-agent: | Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.5.1 |
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.
[Prev in Thread] | Current Thread | [Next in Thread] |