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: Norihiro Tanaka <noritnk <at> kcn.ne.jp>, Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 17229 <at> debbugs.gnu.org
Subject: bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching
Date: Fri, 25 Apr 2014 10:22:42 -0600

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

On 04/25/2014 10:14 AM, Norihiro Tanaka wrote:
> grep 2.18 is slow for below, because always d == 1.
> 
>   $ env LANG=C src/grep jk k
> 
> Therefore, I wrote 0001-grep-speed-up-by-using-memchr-in-Boyer-Moore-searchi.patch.
> 
> When `d' is small, speeds up.  memchr() is faster than or as fast as
> delta1 search even when `d' is sufficiently large.
> 
> However, this patch can't apply to case-insensitive matching.
> In fast, when `d' is large as following case, memchr_trans() imitated
> memchr() will occur slowdown.

Gnulib includes a memchr2() interface, which efficiently searches for
one of two byte values across a known memory length.  It is not quite as
fast as optimized assembly memchr for a single byte search, but when
searching for two bytes in parallel, it is hands down faster than two
sequential memchr() operations or any naive byte-by-byte comparisons.  I
suspect that using memchr2() for case-insensitive searches may allow you
a speedup when searching for (the first byte of) two potential matches
in the search string to the first character of a case-insensitive pattern.

-- 
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.