GNU bug report logs - #17448
[PATCH] grep: retry DFA superset after matched with multiple lines by it

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 17448 in the body.
You can then email your comments to 17448 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

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

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: bug-grep <at> gnu.org
Subject: [PATCH] grep: retry DFA superset after matched with multiple lines by
 it
Date: Fri, 09 May 2014 23:40:48 +0900

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

Currently, when matched with multiple lines by DFA superset, return to
KWset.  However, it won't be wrong probably, because if matches with
multiple lines by DFA superset, also matches with single line there with
high probability.  Further more, if return to KWset after matched with
multiple line by DFA superset, dfafast won't work effectively.

This patch changes to retry DFA superset immediately after matched with
multiple lines by it.

I confirmed the patch by following tests.

  $ yes abcdabc | head -50000000 >k
  $ env LC_ALL=C time -p src/grep '\(ab\)cd\1d' k

  before:
    real 3.48       user 3.41       sys 0.06

  after:
    real 2.14       user 2.07       sys 0.06

Norihiro

[0001-grep-retry-DFA-superset-after-matched-with-multiple-.patch (text/plain, attachment)]

Message #10 received at 17448-done <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>, 17448-done <at> debbugs.gnu.org
Subject: Re: bug#17448: [PATCH] grep: retry DFA superset after matched with
 multiple lines by it
Date: Fri, 09 May 2014 14:52:58 -0700

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

Thanks, I installed that, along with the attached patch which improves 
it slightly by avoiding a test of the returned value of memrchr in a 
context where memrchr cannot return NULL, plus I redid the while-control 
to make it a bit clearer when the loop terminates.

[0001-grep-minor-improvements-to-retry-DFA-superset-patch.patch (text/plain, attachment)]

Previous Next

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