bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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


From: Paul Eggert
Subject: Re: 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.

Attachment: 0001-dfa-improve-worst-case-replace-performance.patch
Description: Text Data


reply via email to

[Prev in Thread] Current Thread [Next in Thread]