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: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: 17350 <at> debbugs.gnu.org
Cc: Paul Eggert <eggert <at> cs.ucla.edu>
Subject: bug#17350: [PATCH] grep: speed up for a case to repeat failure in DFA after success in kwset
Date: Tue, 29 Apr 2014 21:03:05 +0900

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

The previous version of 2nd patch wasn't so better still, because it was
slow for below in order that it never fills beg == prev_beg.

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

Accordingly, I have fixed it. It works below if dfafast is true.

  - If `beg - prev_beg' is small, overhead by calls of KWset and DFA is
    high.  So use constant 64 as minimum shift of the `end' pointer.

  - If ratio of `match - beg' to `beg - prev_beg' is large, KWset isn't
    effective.  So consider it.

As far as I have tested, It improves the performance of the worst cases
with little slowdown to others.

Thanks,
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.