Subject: bug#17576: [PATCH] dfa: speed-up at initial state

From: Paul Eggert <[email-masked]>
Date: Fri, 23 May 2014 22:01:36 -0700

Norihiro Tanaka wrote:
> I tested the patch, and got about 3x speed-up.

That, but unfortunately whan I timed that patch against the current grep 
trunk (879d86e6242eae688f9e72d42b230348d1c93a8f), it slowed things down 
on a similar test case (a test like yours, but 100x longer).

$ yes j | head -1000000000 >k
$ env LC_ALL=C time -p src/grep-old '\(a\|b\)' k
real 8.25
user 7.74
sys 0.50
$ env LC_ALL=C time -p src/grep '\(a\|b\)' k
real 11.11
user 10.63
sys 0.46
$ env LC_ALL=ja_JP.eucJP time -p src/grep-old '\(a\|b\)' k
real 8.74
user 8.27
sys 0.43
$ env LC_ALL=ja_JP.eucJP time -p src/grep '\(a\|b\)' k
real 8.95
user 8.44
sys 0.49

This is on my usual platform: Fedora 20 x86-64, AMD Phenum II X4 910e, 
GCC 4.9.0, default (-O2) optimization.