Why GNU grep is so fast
Summary
Mike Haertel explains how GNU grep reduces search work, reads input efficiently and only examines the bytes that can affect the result. The fastest processing step is often the one an algorithm can provably skip. Performance comes from algorithm, data layout and operating system interface together.
Ideas
- Boyer-Moore-style searching skips large areas when a fixed part of the pattern is missing.
- Large buffered reads avoid unnecessary system calls and data copies.
- The implementation only looks for line ends where a possible match lies.
Recommendations
- Measure search tools with real patterns, file sizes and cache states.
- Compare algorithms by the work they avoid, not just by their inner loop.
References
Links to the original source and the Web Archive open in a new tab.