GNU Grep has been around for decades. This is a common *nix tool for searching named input files for lines containing a match to a given pattern. The original author, Mike Haertel, has a post on the FreeBSD mailing list describing why its so far compared to the BSD implementation of Grep. There are a couple of tricks that GNU Grep performs, namely the use of the well known Boyer-Moore algorithm. This algorithm looks for the last letter of a target string and then uses a lookup table to see how far ahead it can skip in the input when it finds a non-matching character. In addition, GNU Grep avoids breaking the input into lines, which would slow grep down because it has to look for every byte. There are more details on why GNU Grep is so fast; check out the links and other resources below.

Check out the full message here via the FreeBSD mailing list archives.

Additional Information:

• Boyer-Moore String Search Algorithm
• GNU grep man page
• "Fast String Searching", by Andrew Hume and Daniel Sunday