Regex engines exhibit O(n²) performance finding all matches since 1970s; linear-time guarantees apply only to single matches across RE2, Go, Rust, .NET.

finding all regex matches has always been O(n²). even in the engines built to prevent it | ian erik varatalu

search a document for a pattern and it takes a second. search one a hundred times larger and it doesn't take a hundred seconds - it can take almost three hours. every regex engine, in every language, has had this problem since the 1970s, and nobody fixed it. (this is a follow-up to RE#: how we built the world's fastest regex engine in F# and symbolic derivatives and the rust rewrite of RE#) every regex engine that advertises linear-time matching - RE2, Go's regexp, rust's regex crate, .NET's Non...