[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Paul Eggert
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
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.4.0

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.

Attachment: 17230.diff
Description: Text Data

reply via email to

[Prev in Thread] Current Thread [Next in Thread]