5 ms·
> Go's standard library provides a regex library that provides certain O() guarantees, but has a significantly larger constant factor than PCRE-like regexs. Wh
by _ek94 8y ago
> Go's standard library provides a regex library that provides certain O() guarantees, but has a significantly larger constant factor than PCRE-like regexs.
While that is true, Rust's regex library makes the same guarantees.
I'd also like to push back on the idea that perf comparisons are meaningless if one implementation has degenerate cases. Pathological behavior in a backtracking engine happens very rarely, and backtrackers typically come with features that are not supplied by O(n) engines. Someone in the PCRE camp might complain that the benchmark isn't fair because go's engine can't handle backreferences. The different approaches come with different features (backreferences vs garenteed O(n) running time), but they do have a place where their problem domains overlap. It is not useless to examine how they perform in that area.
- jerf 8y ago"I'd also like to push back on the idea that perf comparisons are meaningless if one implementation has degenerate cases." That's not what I said. I said, you can't use "X times faster" comparisons if the O() of the two algorithms in question are not more-or-less the same. That does not prevent you from still characterizing performance differences. You just can't do it via "X times faster" statements, because those are only well-defined for things separated by linear factors, and practically defined for things separated by practically linear factors. f(x) = x^2 is not "2 times bigger" than g(x) = x, or any number of "times bigger", whereas h(x) = 3x + 5 can be reasonably said to be "3 times bigger" than i(x) = x + 50, even though it is not the case that h(x) = 3i(x).