Some other details on GNU grep's performance: * The Boyer-Moore algorithm it uses has a skip loop, which is used to quickly search for the last byte in the nee

Some other details on GNU grep's performance: * The Boyer-Moore algorithm it uses has a skip loop, which is used to quickly search for the last byte in the needle before trying to do more checking. Specifically, the skip loop is implemented with memchr, which can be found in your libc and probably compiles down to SIMD instructions. (The trick here isn't actually skipping bytes, but processing many bytes in a single loop iteration.) This optimization works well in the common case, but can slow things down a bit if your skip byte is really common in the haystack. * When a pattern consists of an alternation of literals, like, `abc|mno|xyz`, then it uses an algorithm based on Commentz-Walter, which you can think of as a hybrid between Aho-Corasick and Boyer-Moore. That is, you get the byte skipping of Boyer-Moore even though you're searching for multiple patterns. The performance of Commentz-Walter degrades as the number of patterns increases because there's fewer opportunities for meaningful skips. Nevertheless, small/short alternations are probably the common case with GNU grep. (The state of the art has actually improved for this specific case and GNU grep could probably benefit. Specifically, the Hyperscan folks over at Intel have some really cool SIMD algorithms for matching multiple patterns. I implemented one here (the comments include a description with examples): https://github.com/rust-lang-nursery/regex/blob/master/src/simd_accel/teddy128.rs https://github.com/rust-lang-nursery/regex/blob/master/src/s...) * The actual regex engine is a lazy DFA (similar to RE2) in that its states are computed on-demand as needed. That is, some parts of the DFA that aren't used are never computed at all. If the DFA gets too big in memory, the existing states are dropped and re-computed as needed. In this way, GNU grep gets the performance of a DFA while preserving linear time matching. (At most one new DFA state is computed for each byte of input.) The inner DFA loop is unrolled. * To re-emphazie a point from the post: avoiding line-by-line matching is critical. This makes it much easier to extract literals from a pattern. For example, if your pattern is `\w+foobar\d+`, then GNU grep can still search for `foobar` because it can make an assumption that its haystack is generally a very small slice of the entire search space (i.e., a single line). This type of optimization is much harder to pull off in a general purpose regex engine. A general purpose regex engine might limit itself to looking for prefix or suffix literals only. * GNU grep really doesn't do all that well for multi-byte encodings. e.g., The time difference between `LC_ALL=C egrep -c '\w{5}'` and `LC_ALL=en_US.UTF-8 egrep -c '\w{5}'` on a large file is quite dramatic. (~3 seconds vs ~52 seconds for a ~2GB mostly-ASCII file that is warm in my page cache.) There's really no need for this slow down if you can bake UTF-8 decoding into your DFA (RE2 does this). However, you then lose the ability to `grep` over other character encodings without transcoding them to UTF-8 first. (In fact, GNU grep may be doing this transcoding step today anyway, so maybe baking UTF-8 into your DFA would be a strictly better solution since it would be much faster on a much larger number of inputs, but probably not slower than any inputs. However, I'm not terribly familiar with this part of GNU grep, so I could have this wrong.)