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

From: Paolo Bonzini <[email-masked]>
Date: Tue, 01 Apr 2014 11:07:09 +0200

Il 15/03/2014 18:12, Jim Meyering ha scritto:
> 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.

Thanks Jim, I'll leave the review to you then!

Paolo