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

[Paul Eggert]

On 04/23/2014 10:51 AM, Norihiro Tanaka wrote:
> 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.

That's odd, as I'm not observing this slowdown.  I'm running on Fedora 
20 x86-64 with GCC 4.9.0.  The current master 
(b0a087b4c7196782d8e76f00c45de1540daf5b91) runs a bit faster on your 
benchmark than the branch with your patch 
(dd0de0dce596add9098e1fb6e294c190c9b04f18): about 1.167 seconds versus 
about 1.230 seconds real time, both in the C locale.  I'm not using any 
special compiler flags, just the -g -O2 that 'configure' deduces.  I'll 
attach the exact difference between these two versions, as the two 
branches have diverged with time and perhaps something else is affecting 
these numbers.

More generally, I don't even understand why your patch would speed 
things up.  To my mind, it should slow things down a bit, which is what 
I'm observing.  And (as I mentioned) it causes 'make check' to fail.  
Possibly I'm simply not understanding the proposed change.

As far as Solaris and HP-UX goes, I'd like to wait until we've figured 
out the GNU situation.  Those platforms are lower priority, and the 
code's correct for them, it's just a performance issue.

17230.diff
Description: Text Data