How does grep run so fast?

by

Assuming your question regards GNU grep specifically. Here’s a note from the author, Mike Haertel:

GNU grep is fast because it AVOIDS LOOKING AT EVERY INPUT BYTE.

GNU grep is fast because it EXECUTES VERY FEW INSTRUCTIONS FOR EACH
BYTE that it
does look at.

GNU grep uses the well-known Boyer-Moore algorithm, which looks first
for the final letter of the target string, and uses a lookup table to
tell it how far ahead it can skip in the input whenever it finds a
non-matching character.

GNU grep also unrolls the inner loop of Boyer-Moore, and sets up the
Boyer-Moore delta table entries in such a way that it doesn’t need to
do the loop exit test at every unrolled step. The result of this is
that, in the limit, GNU grep averages fewer than 3 x86 instructions
executed for each input byte it actually looks at (and it skips many
bytes entirely).

GNU grep uses raw Unix input system calls and avoids copying data
after reading it. Moreover, GNU grep AVOIDS BREAKING THE INPUT INTO
LINES. Looking for newlines would slow grep down by a factor of
several times, because to find the newlines it would have to look at
every byte!

So instead of using line-oriented input, GNU grep reads raw data into
a large buffer, searches the buffer using Boyer-Moore, and only when
it finds a match does it go and look for the bounding newlines
(Certain command line options like
-n disable this optimization.)

This answer is a subset of the information taken from here.

More Related Contents:

  1. How can I grep for a string that begins with a dash/hyphen?
  2. Grep for literal strings
  3. Use grep –exclude/–include syntax to not grep through certain files
  4. How to grep for the whole word
  5. Print lines in one file matching patterns in another file
  6. Using grep for multiple search patterns
  7. Display filename before matching line
  8. grep a tab in UNIX
  9. grep for special characters in Unix
  10. Grepping for exact words with UNIX
  11. Remove carriage return in Unix
  12. Canonical vs. non-canonical terminal input
  13. Why does my tool output overwrite itself and how do I fix it?
  14. What does ^M character mean in Vim?
  15. How do I grep for all non-ASCII characters?
  16. Why is 1/1/1970 the “epoch time”?
  17. How to make grep only match if the entire line matches?
  18. Is there a Unix utility to prepend timestamps to stdin?
  19. How do I use the nohup command without getting nohup.out?
  20. nginx error connect to php5-fpm.sock failed (13: Permission denied)
  21. How to concatenate multiple lines of output to one line?
  22. Explain awk command
  23. Why always ./configure; make; make install; as 3 separate steps?
  24. What is special about /dev/tty? [closed]
  25. Unix:merge multiple CSV files with same header by keeping the header of the first file
  26. unix command line execute with . (dot) vs. without
  27. How to strip leading “./” in unix “find”?
  28. How do I change a shell scripts character encoding?
  29. How to pipe list of files returned by find command to cat to view all the files
  30. Unix find: multiple file types

Leave a Comment