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

[Norihiro Tanaka]

Norihiro Tanaka wrote:
> By the way, I took into another bug by my previous patch.  If
> `kwsm.index < kwset_exact_matches', don't have to run DFA for whole a buffer.

I found a issue in the patch.

If failed in DFA after succeed in kwset, doesn't return to kwset until
reaches the end of the buffer or find a match.  By that, thought some
cases speed up, there is also a case slowdown.

Although A is speed-up, B is slowdown.

(A)
  yes abcdabc | head -50000000 >k
  env LC_ALL=C time -p src/grep abcd.bd k

(B)
  yes "abcdabc
    $(yes jjjjjjj | head -99)" | head -50000000 >k
  env LC_ALL=C time -p src/grep abcd.bd k

In A, KWset doesn't work at all, and it's harmful.
OTOH, in B, It works effectively in A.

I considered only the case of A, but it's necessary to consider how B
does not slowdown.

I wrote the patch for the master to return to KWset, after checking with
DFA about 30 line.  `30' is based on results of the tests.

However, I don't so like this patch, since the basis to 30 is weak...
Is there anyone that have any good ideas?

Norihiro

patch.txt
Description: Text document