4 ms·

FYI: ReJit, as of now, can match only on null-terminated strings. Most regexp engine support matching arbitrary byte sequences. What's the benefit of using ReJ

by ptspts 11y ago

FYI: ReJit, as of now, can match only on null-terminated strings. Most regexp engine support matching arbitrary byte sequences. What's the benefit of using ReJit over RE2? I can think of no C++ dependencies and the support for backward-references. Benchmarks 2...3 years ago: http://coreperf.com/update/rejit/2013/09/01/rejit_pcre_benchmarks.html http://coreperf.com/update/rejit/2013/09/01/rejit_pcre_bench... It looks like much faster than RE2 for various regexps. The documentation doesn't say if it's worst-case matching time is exponential. RE2 is always polynomial.

pcwalton 11y ago
These benchmarks point to the reason I don't like it when the "Regular Expression Matching Can Be Simple and Fast" article is linked to as though it's the last word on regex implementation. Unless you have pathological regexes, the re2 approach frequently loses to a simple recursive backtracking JIT.
- burntsushi 11y ago
  Rust's very own regexes should be besting PCRE now, even when PCRE's JIT is enabled. There are some benchmarks on the PR: https://github.com/rust-lang-nursery/regex/pull/164#issuecomment-184025147 https://github.com/rust-lang-nursery/regex/pull/164#issuecom... Also, FYI, but the rejit in the GP's benchmark link is not the same rejit in the OP. The rejit in the benchmark in the GP is actually based off of Russ Cox's articles. (It uses automata and doesn't support backreferences.) The places where PCRE is still winning come down to these things (I think): * Use of SIMD instructions with literal prefixes that have a small number of common leading bytes (greater than 1). I suspect this is what's going on with the "medium" benchmarks. I think the `jetscii` crate would help here, but it's only usable on the nightlies. * PCRE appears to be detecting a literal prefix of `\n` when the regex starts with `^` in multi-line mode. (The sherlock::line_boundary_sherlock_holmes benchmark.) We could do this too---I just haven't yet. * The sherlock::word_ending_n benchmark has a word boundary, which the lazy DFA in Rust's regex library doesn't support. (It will be hard to improve here unfortunately.) * In general, I think PCRE probably has less overhead per match, which I haven't worked on too much. (For one, every search requires acquiring and quickly releasing a mutex in Rust's library. All I really need to do is push/pop from a stack, so I bet we could avoid the mutex.) On the rest of the regexes, Rust's library is either competitive or completely smashes PCRE in throughput. There are even a few benchmarks that I had to omit because PCRE was too slow. These are strong words, so my goodness, do I hope I'm benchmarking PCRE right! :P And this was all work done based on what Russ Cox wrote. Actual benchmark code is here: https://github.com/rust-lang-nursery/regex/blob/master/benches/bench_pcre.rs https://github.com/rust-lang-nursery/regex/blob/master/bench...
kirbyfan64sos 11y ago
Hey, I'm the author of ReJit...and the one you linked is actually a different library! I haven't benchmarked my ReJit (not the one you linked) enough to know how it compares RE2, though so far it seems quite fast.

by ptspts 11y ago

pcwalton 11y ago

These benchmarks point to the reason I don't like it when the "Regular Expression Matching Can Be Simple and Fast" article is linked to as though it's the last word on regex implementation. Unless you have pathological regexes, the re2 approach frequently loses to a simple recursive backtracking JIT.

burntsushi 11y ago
Rust's very own regexes should be besting PCRE now, even when PCRE's JIT is enabled. There are some benchmarks on the PR: https://github.com/rust-lang-nursery/regex/pull/164#issuecomment-184025147 https://github.com/rust-lang-nursery/regex/pull/164#issuecom... Also, FYI, but the rejit in the GP's benchmark link is not the same rejit in the OP. The rejit in the benchmark in the GP is actually based off of Russ Cox's articles. (It uses automata and doesn't support backreferences.) The places where PCRE is still winning come down to these things (I think): * Use of SIMD instructions with literal prefixes that have a small number of common leading bytes (greater than 1). I suspect this is what's going on with the "medium" benchmarks. I think the `jetscii` crate would help here, but it's only usable on the nightlies. * PCRE appears to be detecting a literal prefix of `\n` when the regex starts with `^` in multi-line mode. (The sherlock::line_boundary_sherlock_holmes benchmark.) We could do this too---I just haven't yet. * The sherlock::word_ending_n benchmark has a word boundary, which the lazy DFA in Rust's regex library doesn't support. (It will be hard to improve here unfortunately.) * In general, I think PCRE probably has less overhead per match, which I haven't worked on too much. (For one, every search requires acquiring and quickly releasing a mutex in Rust's library. All I really need to do is push/pop from a stack, so I bet we could avoid the mutex.) On the rest of the regexes, Rust's library is either competitive or completely smashes PCRE in throughput. There are even a few benchmarks that I had to omit because PCRE was too slow. These are strong words, so my goodness, do I hope I'm benchmarking PCRE right! :P And this was all work done based on what Russ Cox wrote. Actual benchmark code is here: https://github.com/rust-lang-nursery/regex/blob/master/benches/bench_pcre.rs https://github.com/rust-lang-nursery/regex/blob/master/bench...

kirbyfan64sos 11y ago

Hey, I'm the author of ReJit...and the one you linked is actually a different library! I haven't benchmarked my ReJit (not the one you linked) enough to know how it compares RE2, though so far it seems quite fast.