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

Previous Next

Package: grep;

Reported by: Norihiro Tanaka <noritnk <at> kcn.ne.jp>

Date: Fri, 14 Mar 2014 12:22:02 UTC

Severity: normal

Tags: patch

Done: Paul Eggert <eggert <at> cs.ucla.edu>

Bug is archived. No further changes may be made.

Full log

Message #14 received at 17013 <at> debbugs.gnu.org (full text, mbox):

From: Paolo Bonzini <bonzini <at> gnu.org>
To: Jim Meyering <jim <at> meyering.net>, Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 17013 <at> debbugs.gnu.org
Subject: Re: bug#17013: [PATCH] grep: optimization by using the Galil rule
 for Boyer-Moore algorithm in KWSet
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 <noritnk <at> kcn.ne.jp> 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
This bug report was last modified 11 years and 100 days ago.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.