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

Previous Next

Full log

View this message in rfc822 format

From: Eric Blake <eblake <at> redhat.com>
To: Paul Eggert <eggert <at> cs.ucla.edu>, Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 17229 <at> debbugs.gnu.org
Subject: bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching
Date: Thu, 10 Apr 2014 15:33:10 -0600

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

On 04/10/2014 03:11 PM, Paul Eggert wrote:
> On 04/10/2014 04:37 AM, Norihiro Tanaka wrote:
>> The patch requires below. bug#17230 [PATCH 1/2] grep: may also use
>> Boyer-Moore algorithm for case-insensitive matching
> 
> OK, thanks, I'll work on Bug #17230 first, before worrying about 17229.
> 
>> It'd be simpler to use memchr on all platforms;
>> is there a major performance downside to that?
>> Yes.  As far as I was confirmed, it's slow in HP-UX on Itanium and
>> Solaris on SPARC.  I think that that it depends on the implementation of
>> memchr() and the rate of the increment instruction for the `add'
>> instruction on the platform.
> 
> If it's *way* slower with memchr and HP-UX/Itanium or Solaris/SPARC we
> may need to complicate the code, but if it's just a bit slower then it's
> probably better to use the simpler implementation. There's a tradeoff
> between simplified maintenance and performance on non-GNU hosts;
> sometimes the former is more important than the latter, and this may be
> one of those times.

In the past, we've used gnulib to work around painfully slow
implementations.  Remember that many platforms have a quadratic
strstr(); gnulib has the ability to replace it with a guaranteed-linear
version written in straight C code (side note - glibc has since taken
gnulib's implementation and further optimized it; maybe we should
consider feeding the glibc improvements back to gnulib).  If the native
memchr can be demonstrated to be slower on certain platforms in
comparison to an implementation that we can write in straight C, then
having gnulib supply the faster replacement is so much easier to
maintain than to special-case non-GNU hosts in the main body of grep code.

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org

[signature.asc (application/pgp-signature, attachment)]

Previous Next

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