GNU bug report logs - #17229
[PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching

Previous Next

Full log

Message #52 received at 17229 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>, 17229 <at> debbugs.gnu.org
Subject: Re: bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in
 Boyer-Moore searching
Date: Sat, 26 Apr 2014 21:04:13 -0700

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

Thanks for the test cases and patch.  In my tests, switching to macros 
does not help performance, and that SWITCH macro's implementation 
actually slows things down a bit, which is what I'd expect.  If there is 
a reason to use macros I'd like to see a patch that simply changes 
functions to macros without changing the algorithm, so that we can 
measure this effect separately from the algorithm change.

I attempted to suss out the performance improvements in that patch 
without using macros, and installed the attached changes.  With these 
changes grep performs about as well as it does with that patch, on the 
benchmarks you mentioned that I tried (as before, I'm using the default 
optimization with GCC 4.9.0 x86-64 on an AMD Phenom II X4 910e).  Quite 
possibly I've missed something, of course.  The two "advance_*" 
constants used in the heuristics are guesses: I haven't measured 
rigorously to try to come up with good values.

[0001-kwset-improve-performance-when-large-Boyer-Moore-key.patch (text/plain, attachment)]

[0002-kwset-speed-up-by-using-memchr2.patch (text/plain, attachment)]

Previous Next

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