bug#19173: [PATCH] dfa: speed-up for long pattern

[Jim Meyering]

On Mon, Nov 24, 2014 at 5:15 PM, Norihiro Tanaka <address@hidden> wrote:
> DFA trys to find a long sequence of characters that must appear in any
> line containing the r.e. in dfamust()  However, if a pattern is long, it
> is very slow, as it processes all characters step by step.  This change
> makes a string concatenated some normal characters process at a time.
>
> Following test case is posted in bug#15191.  It speeds-up more than 60x.
>
> http://debbugs.gnu.org/cgi/bugreport.cgi?bug=15191#5
>
> << before changed >>
>   $ time -p grep -f regex.re input_lines.txt
>   real 1.28
>   user 1.27
>   sys 0.00
>
> << after changed >>
>   $ time -p grep -f regex.re input_lines.txt
>   real 0.02
>   user 0.01
>   sys 0.00

Thank you for that patch.
I have rebased it and made some small improvements:
I combined an if+do loop into a single for-loop and moved
some declarations "down". I constructed a reproducer that
does not require two large inputs to demonstrate the
performance improvement.

I've also begun to reword the commit log, but am out of time
for this evening, so will post this here, for now.

I am still trying to convince myself that this is a strict
improvement, i.e., that the O(N^2) strstr calls avoided
by this change served no purpose.

0001-dfa-speed-up-handling-of-long-pattern.patch
Description: Text Data