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

[Norihiro Tanaka]

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

0001-dfa-speed-up-for-long-pattern.patch
Description: Binary data