Why GNU grep is fast

Monday, August 8th, 2011

Mike Haertel, original author of GNU grep:

#1 trick: GNU grep is fast because it AVOIDS LOOKING AT EVERY INPUT BYTE.

#2 trick: GNU grep is fast because it EXECUTES VERY FEW INSTRUCTIONS FOR EACH BYTE that it *does* look at.

Fantastic knowledge dump. I wasn’t aware of the Boyer-Moore algorithm that GNU grep uses, but it’s definitely being filed away for future use.

Reminds me of this post by Peter Ammon, about optimizing searching in Hex Fiend, which is also worth reading.

(Via Anant Narayanan.)