do simple literal prefix scanning in regex!

[mkpankov]

Hi,

I saw the news of that regex got refactored and optimized and decided to check my old benchmark. I was very surprised it now runs twice as long!

How to reproduce (using multirust for versions as older regex doesn't compile with newer nightly Rust):

git clone https://github.com/mkpankov/parse-rust.git
cd parse-rust
multirust override nightly-2015-06-24
git checkout 4076c404caf1560a466e9f0799817035089fe841
cargo build --release
time zcat mp3-logs-with-fake-ips.log.gz | ./target/release/parse-rust
// outputs around 4s on my machine
multirust override nightly-2015-05-25
git checkout e33d410291fa7f134eef628b5591d605cd68b218
cargo clean
cargo build --release
time zcat mp3-logs-with-fake-ips.log.gz | ./target/release/parse-rust
// outputs around 2s on my machine

I'm sorry I can't pinpoint it more accurately (maybe it's Rust changes, not regex), but recent major changes of regex might be it. Two times degradation is severe in my opinion, and needs action.

regex versions:

• new, degraded:

 "regex 0.1.38 (registry+https://github.com/rust-lang/crates.io-index)",
 "regex_macros 0.1.20 (registry+https://github.com/rust-lang/crates.io-index)",

• old, fast:

 "regex 0.1.30 (registry+https://github.com/rust-lang/crates.io-index)",
 "regex_macros 0.1.18 (registry+https://github.com/rust-lang/crates.io-index)",

Some background: back when I did this I compared Rust version to C++ version (doing almost stupid translation) and Rust beat C++ by about 40% w/o using compile-time regex. This kind of degradation puts it back behind C++ 😞

[mkpankov]

Okay, seems the real problem is in regex! and regex_macros. Switching to regex::Regex::new instead gives me ~1s time, which is about twice as good as the best of regex! ones. 👍

If that means there's nothing to fix in this crate - feel free to close this, I'll refile the issue where appropriate.

[BurntSushi]

One of the major optimizations for dynamic regexes is in how it handles literal prefixes. Unfortunately, the added complexity of that makes it a little tricky to get it into the regex! macro, so it's no longer doing literal prefix matching. There's probably something simple we can do to at least recover the loss without encoding a full DFA (which is #26).

[BurntSushi]

@mkpankov Thank you for noticing this and reporting it!

[ArtemGr]

BTW, regarding the literal prefix matching, are you using tricks like https://github.com/shepmaster/jetscii (PCMPESTRI) to make them even faster?

[BurntSushi]

jetscii must run on nightly Rust, so no. (@shepmaster knows of my interest though!) I am using memchr though, which only works in the single-byte-prefix case. I suppose jetscii is a candidate for use in regex! though.

[ArtemGr]

That might shift the performance scales in favour of regex! once again. = )

[bluss]

FYI jetscii is limited to ascii at the moment but it could just as well be implemented to look for any byte values.

[shepmaster]

Perhaps of interest, jetscii 0.3.0 introduces support for finding substrings:

Method	Speed
str.find(Substring::new("xyzzy"))	5017 MB/s
str.find("xyzzy")	3837 MB/s

[JoeyAcc]

Out of curiosity, what is the status of this year-and-a-half old bug?

[BurntSushi]

@JoeyAcc I have zero plans to work on the regex! macro in the foreseeable future. I'd personally rather see it removed until there's a plausible way to make it work on stable Rust.

[BurntSushi]

Closing in favor of #26.