[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore s
From: |
Eric Blake |
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 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.4.0 |
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
Description: OpenPGP digital signature
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, (continued)
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, Norihiro Tanaka, 2014/04/10
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, Paul Eggert, 2014/04/10
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, Eric Blake, 2014/04/10
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, Norihiro Tanaka, 2014/04/10
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, Norihiro Tanaka, 2014/04/10
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, Paul Eggert, 2014/04/23
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, Norihiro Tanaka, 2014/04/23
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, Paul Eggert, 2014/04/24
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, Norihiro Tanaka, 2014/04/25
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, Norihiro Tanaka, 2014/04/25
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching,
Eric Blake <=
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, Norihiro Tanaka, 2014/04/25
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, Norihiro Tanaka, 2014/04/26
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, Paul Eggert, 2014/04/27
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, Norihiro Tanaka, 2014/04/27
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, Paul Eggert, 2014/04/27
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, Jim Meyering, 2014/04/28
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, Norihiro Tanaka, 2014/04/28
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, Paul Eggert, 2014/04/29
- bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching, Norihiro Tanaka, 2014/04/30