--- Begin Message ---
|
Subject: |
[PATCH] grep: optimization by using the Galil rule for Boyer-Moore algorithm in KWSet |
|
Date: |
Fri, 14 Mar 2014 21:21:21 +0900 |
Package: grep
Tags: patch
The Boyer-Moore algorithm runs in O(m n) in the worst case,
which perhaps it may be much slower than the DFA.
The Galil rule enables to change O(m n) into O(n) for its case without
overheads and/or slow-down for other cases by avoiding to compare more
than once for a position in the text. This patch implements it.
I prepare following string, which makes a worst case for Boyer-Moore
algorithm, to measure the performance.
yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 > ../k
I run the test with the patch (best-of-5 trials):
env LC_ALL=C time -p src/grep kjjjjjjjjjjjjjjjjjjj k
real 0.70 user 0.32 sys 0.38
Back out that commit (temporarily), recompile, and rerun the experiment:
env LC_ALL=C time -p src/grep kjjjjjjjjjjjjjjjjjjj k
real 3.97 user 3.56 sys 0.40
Norihiro
grep.patch
Description: Binary data
--- End Message ---
--- Begin Message ---
|
Subject: |
Re: bug#17013: [PATCH] grep: optimization by using the Galil rule for Boyer-Moore algorithm in KWSet |
|
Date: |
Mon, 07 Apr 2014 19:56:29 -0700 |
|
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.4.0 |
Norihiro Tanaka wrote:
In second patch, I changed so that Boyer-Moore algorithm could be used
also to case-insensitive matching if MB_CUR_MAX == 1.
Thanks, I merged this patch into the savannah git master (attachment 1),
applied a fixup patch for clarity and to fix some minor style issues
(attachment 2), and fixed some longstanding kwset memory-allocation
infelicities mostly having to do with unecessary code (attachment 3).
0001-grep-use-the-Galil-rule-for-Boyer-Moore-algorithm-in.patch
Description: Text document
0002-grep-minor-cleanups-for-Galil-speedups.patch
Description: Text document
0003-grep-simplify-memory-allocation-in-kwset.patch
Description: Text document
--- End Message ---