4 ms·

We're interested in how the Hyperscan library (full disclosure: I am an Intel employee and Hyperscan designer) stacks up in this comparison. From what I underst

We're interested in how the Hyperscan library (full disclosure: I am an Intel employee and Hyperscan designer) stacks up in this comparison. From what I understand there are Go and Rust bindings for Hyperscan out there as 3rd party projects (although I don't know much about them). We find Rust intriguing and the fine-grained control would be a good match for what our run-time needs; it would be a interesting project to re-implement parts of Hyperscan in Rust.

steveklabnik 11y ago
Oh neat! I hadn't heard of hyperscan before. I will have to check this out.
burntsushi 11y ago
I'm interested too. I'm looking into adding hyperscan to Rust's benchmark harness (which already has PCRE1, PCRE2, RE2, Tcl and Oniguruma). I'm trying to figure out how best to wrap the API. The callback function in `hs_scan` is something I haven't seen in a regex library before (although I bet I can understand why it's used), but for example, Rust's wrapper cripples the callback in comparison to C by dropping the `void *context` parameter: http://flier.github.io/rust-hyperscan/doc/hyperscan/type.MatchEventCallback.html http://flier.github.io/rust-hyperscan/doc/hyperscan/type.Mat... I'm happy to wrap the C directly (in fact, that's what I've done for most of the other regex engines I benchmark against). Before I try to wrangle the callback-style API, is there an alternate API with a more explicit iterator-like interface?
- glangdale 11y ago
  Thanks for looking into this; we like to see benchmarks run by other people to avoid the prospect that we're just benchmarking the things we already know about and like doing (which are often also the things which we've optimized). There are no other interfaces outside of the callback API. It's an interesting prospect to have an iterator-like API but a naive implementation of an iterator API would involve us having to save out all of our state somehow (in an explicit fashion, as opposed to a bunch of stack frames). Our system is pretty complex and so it's not just a case of saving out a couple DFA states...
  - burntsushi 11y ago
    I've done a tiny bit of hacking around on the command line. I'm essentially comparing your `simplegrep` utility with my own utility that operates similarly using `time`. The first thing I noticed was that hyperscan wasn't lining up with match counts from the rest of the regex engines. I dug into your docs a bit more, and indeed, your engine reports all matches, whereas traditionally, most regex engines offer an iterator over successive non-overlapping leftmost-first matches (including start+end). Of course, that's not to say you're wrong or anything---it's just going to be a real bear to accurately benchmark them. All in all, hyperscan looks pretty fast. Some of your docs suggest you're doing even smarter literal detection than I am. Prefix literals and literals "near the front" are easy enough to figure out (the latter is on my list of things to do), but literals at the end or middle of a regex seem much trickier. In particular, it seems very easy to fall into worst case quadratic behavior. If you felt like expanding on some implementation details there, that would be awesome. :-) In any case, I'll share some timings. I ran all of the following regexes on a ~2GB file containing a concatenation of some large sample of Project Gutenberg. It's my goto for "feeling" out regexes and collecting large samples for profiling. I modified simplegrep.c to not print every match and instead increment a single static `count`. I also modified it to mmap the file, so that it is comparable to my utility in Rust which also mmaps the file. The count of total matches is printed at the end. I tried to limit the regexes to ones that had the same number of matches in all regex engines, but on some of them, hyperscan reported slightly more. I then modified simplegrep.c to use the HS_FLAG_SOM_LEFTMOST flag. I did this because that's what Rust's regex engine does (and so do most others). Thus, the benchmark is flawed. But knowing this... Benchmarks are reported in seconds. I tried to take the best of 3 where appropriate, but overall, I saw very little variation run to run. pattern rust pcre2-jit hs hs-start-end \w+\s+Holmes 4.4 17.0 0.5 3.4 [1] 4.4 4.0 0.5 0.5 (?i)Sherlock|Holmes|Watson 4.6 7.5 0.5 0.5 Sher[a-z]+|Hol[a-z]+ 0.9 0.6 0.6 0.6 (?i)Sher[a-z]+|Hol[a-z]+ 4.6 7.0 0.6 0.7 [2] 0.9 2.0 0.5 0.5 [3] 1.0 --- 0.5 0.5 [a-zA-Z]+ing 5.1 7.2 1.3 2.2 \s[a-zA-Z]{0,12}ing\s 4.9 20.0 1.6 2.6 \w{7}\s\w{7} 5.0 32.6 7.0 7.1 [0-9]+[a-z]+[0-9]+[a-z]+[0-9]+ 2.1 2.1 0.5 0.5 [1] Sherlock|Holmes|Watson|Irene|Adler|John|Baker [2] Holmes.{0,25}Watson|Watson.{0,25}Holmes [3] Holmes(?:\s*.+\s*){0,10}Watson|Watson(?:\s*.+\s*){0,10}Holmes That's a pretty impressive showing! I'll have to learn your secrets. :-)
- pettou 11y ago
  Do you perhaps happen to have a link to the results of these benchmarks? I'm desperately looking for some, and http://lh3lh3.users.sourceforge.net/reb.shtml http://lh3lh3.users.sourceforge.net/reb.shtml seems to be quite date. And, impressive work on the regex engine!
  - burntsushi 11y ago
    The benchmarks aren't quite ready to be widely disseminated yet. With that said, I do record benchmarks from time to time in the repo to track progress, which you can see here: https://github.com/rust-lang-nursery/regex/tree/master/bench/log/04 https://github.com/rust-lang-nursery/regex/tree/master/bench... --- You'll have to do the comparison yourself though. There is some analysis---only for Rust's regex engine---with the definition of the benchmarks themselves: https://github.com/rust-lang-nursery/regex/blob/master/bench/src/sherlock.rs https://github.com/rust-lang-nursery/regex/blob/master/bench... (If you fish around there, you'll also see how everything is wired up.) My plan at the moment is to publish something more comprehensive, but it will take time. And yes, the benchmarks you linked are not only outdated, but misleading, and parts of the conclusion I do not agree with. It also doesn't include PCRE2, which is very fast.
    - pettou 11y ago
      Exactly what I was looking for, thanks a lot! Btw., there is also https://github.com/openresty/sregex https://github.com/openresty/sregex which you might find interesting.
      - burntsushi 11y ago
        Yup, I've seen that. Haven't had a chance to play with it yet though.

steveklabnik 11y ago

Oh neat! I hadn't heard of hyperscan before. I will have to check this out.

burntsushi 11y ago

I'm interested too. I'm looking into adding hyperscan to Rust's benchmark harness (which already has PCRE1, PCRE2, RE2, Tcl and Oniguruma). I'm trying to figure out how best to wrap the API. The callback function in `hs_scan` is something I haven't seen in a regex library before (although I bet I can understand why it's used), but for example, Rust's wrapper cripples the callback in comparison to C by dropping the `void *context` parameter: http://flier.github.io/rust-hyperscan/doc/hyperscan/type.MatchEventCallback.html http://flier.github.io/rust-hyperscan/doc/hyperscan/type.Mat... I'm happy to wrap the C directly (in fact, that's what I've done for most of the other regex engines I benchmark against). Before I try to wrangle the callback-style API, is there an alternate API with a more explicit iterator-like interface?

glangdale 11y ago
Thanks for looking into this; we like to see benchmarks run by other people to avoid the prospect that we're just benchmarking the things we already know about and like doing (which are often also the things which we've optimized). There are no other interfaces outside of the callback API. It's an interesting prospect to have an iterator-like API but a naive implementation of an iterator API would involve us having to save out all of our state somehow (in an explicit fashion, as opposed to a bunch of stack frames). Our system is pretty complex and so it's not just a case of saving out a couple DFA states...
- burntsushi 11y ago
  I've done a tiny bit of hacking around on the command line. I'm essentially comparing your `simplegrep` utility with my own utility that operates similarly using `time`. The first thing I noticed was that hyperscan wasn't lining up with match counts from the rest of the regex engines. I dug into your docs a bit more, and indeed, your engine reports all matches, whereas traditionally, most regex engines offer an iterator over successive non-overlapping leftmost-first matches (including start+end). Of course, that's not to say you're wrong or anything---it's just going to be a real bear to accurately benchmark them. All in all, hyperscan looks pretty fast. Some of your docs suggest you're doing even smarter literal detection than I am. Prefix literals and literals "near the front" are easy enough to figure out (the latter is on my list of things to do), but literals at the end or middle of a regex seem much trickier. In particular, it seems very easy to fall into worst case quadratic behavior. If you felt like expanding on some implementation details there, that would be awesome. :-) In any case, I'll share some timings. I ran all of the following regexes on a ~2GB file containing a concatenation of some large sample of Project Gutenberg. It's my goto for "feeling" out regexes and collecting large samples for profiling. I modified simplegrep.c to not print every match and instead increment a single static `count`. I also modified it to mmap the file, so that it is comparable to my utility in Rust which also mmaps the file. The count of total matches is printed at the end. I tried to limit the regexes to ones that had the same number of matches in all regex engines, but on some of them, hyperscan reported slightly more. I then modified simplegrep.c to use the HS_FLAG_SOM_LEFTMOST flag. I did this because that's what Rust's regex engine does (and so do most others). Thus, the benchmark is flawed. But knowing this... Benchmarks are reported in seconds. I tried to take the best of 3 where appropriate, but overall, I saw very little variation run to run. pattern rust pcre2-jit hs hs-start-end \w+\s+Holmes 4.4 17.0 0.5 3.4 [1] 4.4 4.0 0.5 0.5 (?i)Sherlock|Holmes|Watson 4.6 7.5 0.5 0.5 Sher[a-z]+|Hol[a-z]+ 0.9 0.6 0.6 0.6 (?i)Sher[a-z]+|Hol[a-z]+ 4.6 7.0 0.6 0.7 [2] 0.9 2.0 0.5 0.5 [3] 1.0 --- 0.5 0.5 [a-zA-Z]+ing 5.1 7.2 1.3 2.2 \s[a-zA-Z]{0,12}ing\s 4.9 20.0 1.6 2.6 \w{7}\s\w{7} 5.0 32.6 7.0 7.1 [0-9]+[a-z]+[0-9]+[a-z]+[0-9]+ 2.1 2.1 0.5 0.5 [1] Sherlock|Holmes|Watson|Irene|Adler|John|Baker [2] Holmes.{0,25}Watson|Watson.{0,25}Holmes [3] Holmes(?:\s*.+\s*){0,10}Watson|Watson(?:\s*.+\s*){0,10}Holmes That's a pretty impressive showing! I'll have to learn your secrets. :-)
pettou 11y ago
Do you perhaps happen to have a link to the results of these benchmarks? I'm desperately looking for some, and http://lh3lh3.users.sourceforge.net/reb.shtml http://lh3lh3.users.sourceforge.net/reb.shtml seems to be quite date. And, impressive work on the regex engine!
- burntsushi 11y ago
  The benchmarks aren't quite ready to be widely disseminated yet. With that said, I do record benchmarks from time to time in the repo to track progress, which you can see here: https://github.com/rust-lang-nursery/regex/tree/master/bench/log/04 https://github.com/rust-lang-nursery/regex/tree/master/bench... --- You'll have to do the comparison yourself though. There is some analysis---only for Rust's regex engine---with the definition of the benchmarks themselves: https://github.com/rust-lang-nursery/regex/blob/master/bench/src/sherlock.rs https://github.com/rust-lang-nursery/regex/blob/master/bench... (If you fish around there, you'll also see how everything is wired up.) My plan at the moment is to publish something more comprehensive, but it will take time. And yes, the benchmarks you linked are not only outdated, but misleading, and parts of the conclusion I do not agree with. It also doesn't include PCRE2, which is very fast.
  - pettou 11y ago
    Exactly what I was looking for, thanks a lot! Btw., there is also https://github.com/openresty/sregex https://github.com/openresty/sregex which you might find interesting.
    - burntsushi 11y ago
      Yup, I've seen that. Haven't had a chance to play with it yet though.