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

Previous Next

Full log

Message #26 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>
Cc: 17229 <at> debbugs.gnu.org
Subject: Re: bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in
 Boyer-Moore searching
Date: Wed, 23 Apr 2014 00:08:52 -0700

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

Norihiro Tanaka wrote:
> Now I wrote the additional patch.

Sorry, I don't understand that patch.  I applied your earlier patch 
(attachment 1) and then merged that patch (attachment 2), but the 
resulting 'grep' failed 'make check'; I got a "FAIL: fedora" and the 
test after "file" never finished.  This was on Fedora 20 x86-64 with my 
own installation of GCC 4.9.0.

Instead of trying to understand that patch, I wrote a different patch 
(attachment 3) that simplifies the code and removes the part that is 
x86-specific.  This improves the performance quite a bit for the test 
case given in the ChangeLog entry.  I also tested performance on Sparc 
Solaris 10, and memchr was a big win there.  Perhaps there are platforms 
where memchr is a big loss, but we can cross that bridge if we come to it.

Perhaps I merged that patch incorrectly, so I'll leave this bug open for 
now.  To be honest I hope that patch doesn't improve performance 
significantly if we get it to work correctly, as it looks tricky.

[0001-grep-speed-up-by-using-memchr-in-Boyer-Moore-searchi.patch (text/plain, attachment)]

[0001-grep-speed-up-by-replacing-incr-to-add-in-x86-and-x8.patch (text/plain, attachment)]

[0002-kwset-simplify-and-speed-up-Boyer-Moore-unibyte-i-in.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.