GNU bug report logs - #17350
[PATCH] grep: speed up for a case to repeat failure in DFA after success in kwset

Previous Next

Full log

View this message in rfc822 format

From: help-debbugs <at> gnu.org (GNU bug Tracking System)
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Subject: bug#17350: closed (Re: bug#17350: [PATCH] grep: speed up for a
 case to repeat failure in DFA after success in kwset)
Date: Sun, 27 Apr 2014 01:09:02 +0000

[Message part 1 (text/plain, inline)]

Your bug report

#17350: [PATCH] grep: speed up for a case to repeat failure in DFA after success in kwset

which was filed against the grep package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to 17350 <at> debbugs.gnu.org.

-- 
17350: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=17350
GNU Bug Tracking System
Contact help-debbugs <at> gnu.org with problems

[Message part 2 (message/rfc822, inline)]

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>, 17350-done <at> debbugs.gnu.org
Subject: Re: bug#17350: [PATCH] grep: speed up for a case to repeat failure
 in DFA after success in kwset
Date: Sat, 26 Apr 2014 18:08:12 -0700

[Message part 3 (text/plain, inline)]

Thanks, I installed that patch with minor reworking of the ChangeLog 
entry and am marking this as done.  By the way, a minor point -- 
nowadays we prefer single-quoting 'like this' rather than the old style 
`like this' -- the GNU coding standards changed recently in this regard.

I noticed a mostly-theoretical read buffer overrun in the patch, along 
with some other opportunities for simplification and tuning, and 
installed the attached fixup patch as well.

[0001-dfa-fix-index-bug-in-previous-patch-and-simplify.patch (text/plain, attachment)]

[Message part 5 (message/rfc822, inline)]

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: bug-grep <at> gnu.org
Subject: [PATCH] grep: speed up for a case to repeat failure in DFA after
 success in kwset
Date: Sat, 26 Apr 2014 20:25:43 +0900

[Message part 6 (text/plain, inline)]

Patch#17230 causes slowdown for a case to repeat failure in DFA after
success in kwset, although it improves the performance for many cases.

In fact, the master without this patch is 3.5x slower than grep 2.18 for
below.

    $ yes abcdabc | head -50000000 >k
    $ env LC_ALL=C time -p src/grep -i 'abcd.bd' k

This patch fixes the degradation of the performance for such cases.  See
the commit log for details.

Norihiro

[patch.txt (text/plain, attachment)]

Previous Next

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