Russ Cox: Regular Expression Matching Can Be Simple And Fast +

This is a tale of two approaches to regular expression matching. One of them is in widespread use in the standard interpreters for many languages, including Perl. The other is used only in a few places, notably most implementations of awk and grep. The two approaches have wildly different performance characteristics:

An awesome paper on regex performance and implementation details.