why GNU grep is fast

[Mike Haertel]

Dag-Erling Smørgrav <des at des.no> writes:
> Mike Haertel <mike at ducky.net> writes:
> > For example if your regex is /foo.*bar/, the initial Boyer-Moore search
> > is (probably) searching for foo.
> >
> > If the initial search succeeds, GNU grep isolates the containing line,
> > and then runs the full regex matcher on that line to make sure.
> 
> You don't really need to "isolate the containing line" unless you have
> an actual match, do you?  There are two cases:

Theoretically no.  However, suppose the pattern was /foo.*blah/.
The Boyer-Moore search will be for "blah", since that's the longest
fixed substring.  But verifying a match for the full regexp either
requires a regexp matcher with the feature "start here, at THIS point
in the middle of the RE and THAT point in the middle of the buffer,
and match backwards and forwards", or else running a more standard
RE matcher starting from the beginning of the line.

So, in practice you pretty much have to at least search backwards
for the preceding newline.

As you mentioned, you can avoid searching forwards for the next
newline if your RE matcher supports using newline as an exit marker.
But if the workload characteristics are that matching lines are
scarce compared to the input, this is an optimization that just
won't matter much either way.