The first benchmark is primarily a comparison of Nim's PEG package to Rust's libregex package. The two have very different algorithms, and libregex is optimized to avoid exponential blowup on pathological regexes. It's missing a fallback to the backtracking algorithm at present.
Using rust-pcre would probably mitigate this problem.
I was still pretty surprised that `regex` was getting killed. It turns out, I think, that `\w+` in Rust is Unicode friendly, but it's not in Nim. In cases where most matches fail, checking the full spectrum of Unicode "word" characters becomes pretty expensive (although it is at least doing a binary search on contiguous ranges of characters: https://github.com/rust-lang/regex/blob/master/src/vm.rs#L23...). When I switched `\w+` to `[a-zA-Z0-9_]+` in the Rust program, I saw a ~60% performance increase.
> and libregex is optimized to avoid exponential blowup on pathological regexes. It's missing a fallback to the backtracking algorithm at present.
Maybe. RE2/C++ doesn't do any backtracking AFAIK, but it appears near the top of any benchmark I think.
Using rust-pcre would probably mitigate this problem.