Subject: bug#17700: [PATCH] dfa: speed-up for a pattern that many atoms are catenated

From: Paul Eggert <[email-masked]>
Date: Thu, 05 Jun 2014 17:49:23 -0700

Norihiro Tanaka wrote:
> after `grep: undo part of previous change', no longer faster.
>
> $ printf '%02048d\n' 0 | time -p src/grep -f - /dev/null
>
> master  : real 5.74  user 5.40  sys 0.17
> my patch: real 0.08  user 0.04  sys 0.04

This isn't matching the results I get on my platform.  If 
src/d5dfa69/grep is the old version, src/709e7e5/grep the current master 
(i.e., just use system strstr), and src/grep is the old version with 
your patch, I get:

$ printf '%02048d\n' 0 | time -p src/d5dfa69/grep -f - /dev/null
real 0.33
user 0.33
sys 0.00
$ printf '%02048d\n' 0 | time -p src/709e7e5/grep -f - /dev/null
real 0.04
user 0.04
sys 0.00
$ printf '%02048d\n' 0 | time -p src/grep -f - /dev/null
real 0.03
user 0.03
sys 0.00

So it looks like your patch confers some advantage, but on my platform 
almost all the speedup is achieved simply by switching to the system strstr.

> `lookfor' isn't terminated by `\-'\0' in istrstr(), but strstr() requires it.

Yes, that's why I needed to make the most recent change in the current 
master; it arranges for strstr's 2nd arg to be null-terminated.