|
From: | Paul Eggert |
Subject: | bug#22357: grep -f not only huge memory usage, but also huge time cost |
Date: | Sun, 18 Dec 2016 23:48:10 -0800 |
User-agent: | Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.5.1 |
'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.
0001-dfa-improve-worst-case-replace-performance.patch
Description: Text Data
[Prev in Thread] | Current Thread | [Next in Thread] |