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