bug#17230: [PATCH 1/2] grep: may also use Boyer-Moore algorithm for case-insensitive matching

[Norihiro Tanaka]

Paul, thanks for a lot of reviews and commits.  However, it may be wrong.
I ran several tests for the worst case.

$ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >../k
$ env LANG=C time -p src/grep -i kjjjjjjjjjjjjjjjjjjj ../k

My version:
real 0.74
user 0.43
sys 0.30

Simplified version:
real 2.06
user 1.74
sys 0.31

It's slower than DFA.

$ env LANG=C time -p src/grep -i 'a\|kjjjjjjjjjjjjjjjjjjj' ../k
real 1.26
user 0.96
sys 0.30

I ran the test on Solaris 10 (SPARC) and HP-UX 11v2 (Itanium)


- On HP-UX 11v2

$ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >../k
$ env LANG=C time -p src/grep -i kjjjjjjjjjjjjjjjjjjj ../k

My version:
real        2.9
user        2.6
sys         0.2

Simplified version:
real        7.5
user        7.3
sys         0.2

Using DFA:

$ env LANG=C time -p src/grep -i 'a\|kjjjjjjjjjjjjjjjjjjj' ../k

real        3.2
user        3.0
sys         0.2

- On Solaris 10

$ env LANG=C time -p src/grep -i kjjjjjjjjjjjjjjjjjjj ../k

My version:
real 7.61
user 6.89
sys 0.71

Simplified version:
real 24.44
user 23.71
sys 0.72

Using DFA:

$ env LANG=C time -p src/grep -i 'a\|kjjjjjjjjjjjjjjjjjjj' ../k

real 8.03
user 7.31
sys 0.71

Norihiro