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

[Norihiro Tanaka]

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
Description: Text document