Subject: Re: bug#17013: [PATCH] grep: optimization by using the Galil rule for Boyer-Moore algorithm in KWSet

From: Jim Meyering <[email-masked]>
Date: Sat, 15 Mar 2014 10:12:56 -0700

On Fri, Mar 14, 2014 at 11:06 PM, Norihiro Tanaka <[email-masked]> 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.