[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#17013: [PATCH] grep: optimization by using the Galil rule for Boyer-
|
From: |
Jim Meyering |
|
Subject: |
bug#17013: [PATCH] grep: optimization by using the Galil rule for Boyer-Moore algorithm in KWSet |
|
Date: |
Sat, 15 Mar 2014 10:12:56 -0700 |
On Fri, Mar 14, 2014 at 11:06 PM, Norihiro Tanaka <address@hidden> wrote:
> I changed the patch so that the delta2 shift is extracted from the trie,
> because it's very excellent.
Very nice.
I've begun to review these patches, and really like the
improved performance. Your first version (decreasing
worst-case O(M*N) to O(M+N)) gives 30x speed-up in
some cases. The delta2-from-trie change brings it
closer to 40x.