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

Previous Next

Full log

View this message in rfc822 format

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 17230 <at> debbugs.gnu.org
Subject: bug#17230: [PATCH 1/2] grep: may also use Boyer-Moore algorithm for case-insensitive matching
Date: Wed, 23 Apr 2014 13:47:35 -0700

[Message part 1 (text/plain, inline)]

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 (text/x-patch, attachment)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.