The comment does not accurately reflect the state of the benchmarks today. (I do not know whether it accurately reflects the state of the benchmarks at the tim

The comment does not accurately reflect the state of the benchmarks today. (I do not know whether it accurately reflects the state of the benchmarks at the time of posting.) While some of the implementations are backtracking, the #2 slot is currently held by a C++ implementation that uses RE2: https://code.google.com/p/re2/ https://code.google.com/p/re2/ which also provides the linear guarantee. Edit: Apparently I forgot that RE2 was also written by Russ Cox, so he should know well that it provides better performance with the same guarantee.