I tried it on grep-2.14, and I confirmed that the patch is effective
certainly.  However, I see that it's fixed in bug#17377.

$ env LC_ALL=C time -p ../grep-2.19/src/grep -E -f regex.re input_lines.txt

grep-2.14
  before: real 7.66  user 7.56  sys 0.09
  after : real 2.06  user 1.96  sys 0.09

grep-2.18.146-ebf3
  before: real 1.59  user 1.50  sys 0.08
  after : real 1.99  user 1.86  sys 0.12

If my rewriting of the patch is right, it causes slowdown rather by
building heap.

Norihiro