3 ms·
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
by pcwalton 12y ago
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.
- burntsushi 12y agoI 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#L237-L238 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.
- arthurtw 12y agoBingo. With `regex!(r"[a-zA-Z0-9_]+")`, Rust finally runs faster than Nim. I’ve updated the article.