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

[Norihiro Tanaka]

Paul Eggert wrote:
> I guess that grep needs a performance test suite, so that we can find
> problems like this in a more-disciplined way.

I agree, but I have no idea to perform it.

BTW, I retried them on Fedora 20, but I couldn't confirm significant
slowdown.

  Intel(R) Core(TM)2 Duo CPU     E8500  @ 3.16GHz
  Fedora 20  GCC 4.8.2 20131017 (Red Hat 4.8.2-1) (x86-64)

$ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >k
$ yes j | head -100000000 >l

[ before 0001-dfa-speed-up-at-initial-state.patch ]

$ env LC_ALL=C src/grep '\(a\|b\)' k
real 0.96
user 0.85
sys 0.10
$ env LC_ALL=C src/grep '\(a\|b\)' l
real 0.64
user 0.60
sys 0.03

[ after 0001-dfa-speed-up-at-initial-state.patch ]

$ env LC_ALL=C src/grep '\(a\|b\)' k
real 0.58
user 0.52
sys 0.05
$ env LC_ALL=C src/grep '\(a\|b\)' l
real 0.75
user 0.69
sys 0.05

However, I could confirm slowdown on RHEL6 GCC 4.4.7.  According to the
result, I see that GCC fails in inlination.  In addition to
0001-dfa-speed-up-at-initial-state.patch, I applied an attached patch,
and retried them.  Then I confirmed speed-up.

$ env LC_ALL=C src/grep '\(a\|b\)' k
real 0.46
user 0.35
sys 0.10
$ env LC_ALL=C src/grep '\(a\|b\)' l
real 0.54
user 0.49
sys 0.04

Thanks,
Norihiro

0001-dfa-separate-dfaexec-function-to-help-optimization-b.patch
Description: Text document