The biggest gap in the references/history section is the failure to mention V. Glushkov, whose NFA construction has much appeal and certainly predates Thompsons

The biggest gap in the references/history section is the failure to mention V. Glushkov, whose NFA construction has much appeal and certainly predates Thompsons'. Reading the references, one might also draw the conclusion that regex implementation almost ceased between 1968 and 2007. In our experience, regex matching can be simple and fast, but only sometimes. RE2's approach is straightforward but naive; we built a considerably faster (on some metrics) and more scalable system in Hyperscan. The cost of this turned out to considerable complexity - and there are still many regexes and inputs that don't perform particularly well in either system.