[PATCH] dfa: save memory for states

[Norihiro Tanaka]

Hi,

dfa matcher is not good at matching for long patterns as following.

  seq -f '%g bottles of beer on the wall' 2400 >in
  env LC_ALL=C src/grep -vf in in

In fact, for this case GNU grep is considerably slower than ripgrep
which is released recently.  I think that it is cased by some reasons
and one of them is in memory allocation.

This patch checks number of states in beginning of dfa execution, and if
there are a lot of states, release them.  it can not only save memory,
but may improve performance, as when the number of the state becomes
large, it takes time to find the same state from caches of states.

Thanks.
Norihiro

0001-dfa-save-memory-for-states.patch
Description: Text document