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

View this message in rfc822 format

From: Jim Meyering <jim <at> meyering.net>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 17013 <at> debbugs.gnu.org
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 <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.
This bug report was last modified 11 years and 99 days ago.

Previous Next

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