17 ms·

Multiple regex performance shootout: RE2 vs. Intel's Hyperscan

124 points by glangdale 9y ago

glangdale 9y ago
This post is by no means the definitive statement on RE2 and Hyperscan performance. We went very deep on subsets of one measurement case, but different patterns would yield a different set of behaviors for both engines. Single-pattern performance has been covered before: e.g. https://rust-leipzig.github.io/regex/2017/03/28/comparison-of-regex-engines/ https://rust-leipzig.github.io/regex/2017/03/28/comparison-o...
- Aissen 9y ago
  What's fascinating is that it shows here that Hyperscan is not matching the same (!) as the other engines. A piece of information conveniently forgotten in the Intel piece. Also note that the rust regex crate now uses the same SIMD algorithm(Teddy) invented as part of Hyperscan, see: http://blog.burntsushi.net/ripgrep/ http://blog.burntsushi.net/ripgrep/ (also ripgrep is awesome, and you should use it.)
  - glangdale 9y ago
    This is a surprisingly negative-sounding comment. We've been quite clear in our documentation and public language in the past about how 'all-matches' semantics differ from 'best match' semantics implemented by back-tracking engines, so we generally find a few more matches. Given the comparison with RE2 here is under circumstances where RE2::Set is not returning any offset at all, I'm not sure what your point is about the "Intel piece". Ripgrep is also awesome, and thanks (I guess) for mentioning Teddy, which nicely illustrates my favorite instruction (PSHUFB). There are still some bits of the Teddy algorithm that should be incorporated into ripgrep (the merging of literals when you have >8 literals is naive).
    - Aissen 9y ago
      It is negative, I should probably have toned it down even more. My mistake, sorry.
netheril96 9y ago
It is a pity that regex engines based on regex theory have just come into widespread use when the theory has been in place for decades. Why many language standard libraries use exponential algorithm is beyond my comprehension.
- pcwalton 9y ago
  Because the exponential algorithm (1) easily supports backtracking and (2) can often be implemented with less constant factor overhead than the Thompson NFA. Building the NFA and doing NFA to DFA conversion takes time. The simplicity and resulting speed in non-pathological cases is why JS regex engines all use the exponential algorithm. Think about quicksort. Quicksort is O(n^2) worst case, so it must be awful, right? Well, no, not really, because with a sensible choice of pivot you rarely hit that case, and the constant overhead is significantly better than the guaranteed O(n log n) mergesort for common input. Regex algorithms have a similar dynamic. My understanding is that re2 and rust-regex manage parity with the backtracking algorithm for non-pathological regexes, much as the complicated mergesort-based Timsort can achieve parity with quicksort, but they have to do a lot of work to get there.
  - glangdale 9y ago
    This sounds reasonable, but is simply not correct. There's nothing inherently slow about either algorithm in the average case and there's absolutely no reason that Thompson (or the One True NFA, Glushkov) should be slower than backtracking algorithms. The exponential algorithms are commonly used because (a) they rarely hit their exponential behavior in practice, (b) they offer huge numbers of features that automata based algorithms cannot easily supply (capturing subexpressions and backreferences are the most obvious - yes, you can do capturing in automata but it's pretty hard) and (c) they are simpler than building something like Hyperscan. Our codebase is enormous compared to a relatively feature-rich back-tracker. Partly this is because we've been at this a while and under constant pressure to do well on lots of cases and metrics (a cleaner, 'toy' system would look nicer but maybe we wouldn't have survived as a startup if we hadn't optimized 'that one case'). But if you want to build out a Glushkov NFA graph and do a ton of optimizations, you're already more complex than a backtracking engine and you're just getting started.
VHRanger 9y ago
How do both of those compare to the C++11 std::regex or Boost::regex? At what point is it worth the switch?
- glangdale 9y ago
  If you really need the backtracking features in those other systems, the point is "never". Similarly, if you have short-lived regexes that are compiled, used for a small amount of data, and discarded, you might never see a performance benefit. Multiple regexes, scanning a substantial amount of data and/or having a requirement to 'stream' (i.e. process successive writes of input data when you can't hold on to old data) are the sort of things that make Hyperscan use more sensible. We see a lot of use in network security where these assumptions all generally hold.
  - Blackthorn 9y ago
    Also, if you're taking in user input into a regex you want to use something like RE2 or Hyperscan. To do otherwise is to expose yourself to DoS.
    - anentropic 9y ago
      is that just because they don't support the features which can be used to make pathological regexes in other engines? or they have additional sanitisation or security features?
      - glangdale 9y ago
        Neither. There are regexes that can be written in the common subset supported by (say) libpcre, RE2 and Hyperscan that will induce exponential backtracking with libpcre but not with the other libraries. I'm not aware of any difference in terms of sanitisation or security.
- mtve 9y ago
  std::regex does not work in half of distros, boost is disaster, qt is ok. never.
phunge 9y ago
If you're interested in getting parse trees from regexes (ie all the submatch locations), check out Kleenex, it looks really interesting and is based on some new research. Full parse trees are a harder problem than matching, and one that is not a primary focus in RE2 performance AFAICS.
- nly 9y ago
  Isn't it true that once you have backtracking in your regex engine that there's no longer a guarantee that there's only a single parse tree? I've found the hardest part of using e.g. a recursive descent parser is having to correct captured state while backtracking.
strictfp 9y ago
Limiting the benchmark to engines supporting matching sets of regexes seems unnecessarily narrow to me. Is matching a set of regexes not equivalent to matching a single combined regex? Something like "(?:a)|(?:b)|(?:c)"? If so, why not run the test with that regex instead, and include other engines?
- glangdale 9y ago
  For engines like Hyperscan and RE2's underlying algorithms, alternation works the way you describe. However, for backtracking engines, alternation does not do a search in parallel for all the patterns. Instead, it winds up first looking for the first, then the second, etc., finds the first match, and declares victory. There are particular patterns and inputs where this behavior will be similar to parallel matchers like RE2::Set and Hyperscan, but the general case just won't work.
- rwj 9y ago
  The complication occurs when you need to identify which sub-expression matched.
rurban 9y ago
The summary is very easy: * Hyperscan is by far the fastest, but has only limited platform and regex support. * Next is pcre2 (with the jit), which is a bit faster than the new rust regex. These support all options, everywhere. * Then RE2 and all the others. RE2 has very limited regex support. Why they compare the fastest with one of the slower and limited ones is beyond my understanding. The best overview is still https://rust-leipzig.github.io/regex/2017/03/28/comparison-of-regex-engines/ https://rust-leipzig.github.io/regex/2017/03/28/comparison-o...
- glangdale 9y ago
  This summary was "very easy", because it is wrong. This assessment is unfair to RE2, and we're comparing to RE2 because it's the only one of these that can do multiple regex. Both Hyperscan and RE2 throw a good deal of regex under the bus in order to get multiple regex support, performance and/or streaming capability.
  - burntsushi 9y ago
    Rust's regex library has had support for regex sets for quite some time, and it's based on the same "tricks" that RE2 uses: https://docs.rs/regex/0.2.2/regex/struct.RegexSet.html https://docs.rs/regex/0.2.2/regex/struct.RegexSet.html
    - glangdale 9y ago
      Oops. We're out of date in our thinking then. If the implementation is similar to re2, you'll probably see similar performance, although I hear good things about your small group literal matcher. :-)
      - burntsushi 9y ago
        :P Yeah, I would expect performance characteristics to be very similar to RE2! I actually think RegexSet disables literal optimizations in more cases than the standard regex, but it's been a while since I've touched that.
jmnicolas 9y ago
Maybe I'm not normal but I'd rather write 30 lines of readable and debugable code than use a regex. Would you embed Brainfuck in your code ? Then why do you use regexes ?
- glangdale 9y ago
  Regex syntax is fairly gross, I agree. That being said I'd be surprised to your open-coded version of simple regexes like /hatstand.*teakettle/ or /badgerbrush\s{12}/ was clearer than the regex, and it would almost certainly be dismally slow relative to a tuned regex implementation - unless you wrote a lot of one-off SIMD code. Further, if given a bunch of different regexes to match simultaneously, your code would have to run them one by one. Finally, quite frequently our customers/users are in a situation where they don't know what the regex is going to be, and they aren't going to let people inject arbitrary code into their applications.
  - ohyes 9y ago
    A lot of the grossness is syntactic sugar, if one were so inclined they could get by with a handful of operators, and end up with something fairly clear as you demonstrated. So if anything I blame lack of good taste for regular expressions bad rep.
- Xophmeister 9y ago
  How do you match arbitrarily repeating patterns, which may/probably have a combinatoric expansion, without effectively writing your own parser? If you're using a language where writing a parser is relatively easy (e.g., Lisp, Haskell, etc.) or your patterns are trivial, then fair enough. Otherwise, good luck with that. For example, in Python, if I want to match "foo" followed by any number of "bar"s and/or "quux"s at the end of the string, I could write this: if re.match(r"foo(bar|quux)*$", my_string): ... ...without going to the trouble writing a recursive-descent parser or state machine, your way would be something like this: def ends_with_foo_etc(s): if s.endswith("foo"): return True after_last = len(s) - s[::-1].find("oof") if after_last > len(s): return False good_tail = True while good_tail and after_last < len(s): if s[after_last:after_last + 3] == "bar": after_last += 3 elif s[after_last:after_last + 4] == "quux": after_last += 4 else: good_tail = False return good_tail if ends_with_foo_etc(my_string): ... That's both excessively terse -- for a really simple pattern -- almost certainly slower and, most importantly, brittle in that it couples your pattern to your implementation in a non-trivial way. If your pattern changes, you may have to completely rewrite your matching function. It's also worth noting that a typical regex API will do more than just match patterns; e.g., extracting subpatterns/groups, splitting, etc.
bterlson 9y ago
Wow, oddly relevant - I've been working on a RegExp implementation in JavaScript using similar techniques (minus vectorization of course, RIP SIMD.js). There is no efficient way in JavaScript to replace many patterns (e.g. a list of sentence fragments with optional whitespace, capitalization, pluralization, etc.) against a large document where the replacement requires metadata about the subpattern that was matched (e.g. to replace a term with a link to the term's definition). I wonder if I should switch gears and try to write a native Node module for this instead. This looks really great.
- glangdale 9y ago
  Thanks for the kind words. You'll have to roll your own 'replace', and the all-matches semantics of Hyperscan may give you some headaches - you'll need a careful reading of our Start of Match semantics and to craft patterns that yield "less surprising results". If you can share your workload, or want assistance in figuring out whether to do this and/or how to do it, please contact us on the mailing list or on the email link for Hyperscan on 01.org. We're always interested in sample patterns, especially ones that fall outside our normal wheelhouse of 'network security and then some more network security'.
- time4tea 9y ago
  Well depends on how big and how fast. This worked for me https://github.com/time4tea/glossary/blob/master/README.md https://github.com/time4tea/glossary/blob/master/README.md Its a very simple Aho-Corasick text search with replacement. A similar thing in Java using Ropes rather than Strings was also ok, for some value of ok.

124 points by glangdale 9y ago

This post is by no means the definitive statement on RE2 and Hyperscan performance. We went very deep on subsets of one measurement case, but different patterns would yield a different set of behaviors for both engines. Single-pattern performance has been covered before: e.g. https://rust-leipzig.github.io/regex/2017/03/28/comparison-of-regex-engines/ https://rust-leipzig.github.io/regex/2017/03/28/comparison-o...

Aissen 9y ago
What's fascinating is that it shows here that Hyperscan is not matching the same (!) as the other engines. A piece of information conveniently forgotten in the Intel piece. Also note that the rust regex crate now uses the same SIMD algorithm(Teddy) invented as part of Hyperscan, see: http://blog.burntsushi.net/ripgrep/ http://blog.burntsushi.net/ripgrep/ (also ripgrep is awesome, and you should use it.)
- glangdale 9y ago
  This is a surprisingly negative-sounding comment. We've been quite clear in our documentation and public language in the past about how 'all-matches' semantics differ from 'best match' semantics implemented by back-tracking engines, so we generally find a few more matches. Given the comparison with RE2 here is under circumstances where RE2::Set is not returning any offset at all, I'm not sure what your point is about the "Intel piece". Ripgrep is also awesome, and thanks (I guess) for mentioning Teddy, which nicely illustrates my favorite instruction (PSHUFB). There are still some bits of the Teddy algorithm that should be incorporated into ripgrep (the merging of literals when you have >8 literals is naive).
  - Aissen 9y ago
    It is negative, I should probably have toned it down even more. My mistake, sorry.

netheril96 9y ago

It is a pity that regex engines based on regex theory have just come into widespread use when the theory has been in place for decades. Why many language standard libraries use exponential algorithm is beyond my comprehension.

pcwalton 9y ago
Because the exponential algorithm (1) easily supports backtracking and (2) can often be implemented with less constant factor overhead than the Thompson NFA. Building the NFA and doing NFA to DFA conversion takes time. The simplicity and resulting speed in non-pathological cases is why JS regex engines all use the exponential algorithm. Think about quicksort. Quicksort is O(n^2) worst case, so it must be awful, right? Well, no, not really, because with a sensible choice of pivot you rarely hit that case, and the constant overhead is significantly better than the guaranteed O(n log n) mergesort for common input. Regex algorithms have a similar dynamic. My understanding is that re2 and rust-regex manage parity with the backtracking algorithm for non-pathological regexes, much as the complicated mergesort-based Timsort can achieve parity with quicksort, but they have to do a lot of work to get there.
- glangdale 9y ago
  This sounds reasonable, but is simply not correct. There's nothing inherently slow about either algorithm in the average case and there's absolutely no reason that Thompson (or the One True NFA, Glushkov) should be slower than backtracking algorithms. The exponential algorithms are commonly used because (a) they rarely hit their exponential behavior in practice, (b) they offer huge numbers of features that automata based algorithms cannot easily supply (capturing subexpressions and backreferences are the most obvious - yes, you can do capturing in automata but it's pretty hard) and (c) they are simpler than building something like Hyperscan. Our codebase is enormous compared to a relatively feature-rich back-tracker. Partly this is because we've been at this a while and under constant pressure to do well on lots of cases and metrics (a cleaner, 'toy' system would look nicer but maybe we wouldn't have survived as a startup if we hadn't optimized 'that one case'). But if you want to build out a Glushkov NFA graph and do a ton of optimizations, you're already more complex than a backtracking engine and you're just getting started.

VHRanger 9y ago

How do both of those compare to the C++11 std::regex or Boost::regex? At what point is it worth the switch?

glangdale 9y ago
If you really need the backtracking features in those other systems, the point is "never". Similarly, if you have short-lived regexes that are compiled, used for a small amount of data, and discarded, you might never see a performance benefit. Multiple regexes, scanning a substantial amount of data and/or having a requirement to 'stream' (i.e. process successive writes of input data when you can't hold on to old data) are the sort of things that make Hyperscan use more sensible. We see a lot of use in network security where these assumptions all generally hold.
- Blackthorn 9y ago
  Also, if you're taking in user input into a regex you want to use something like RE2 or Hyperscan. To do otherwise is to expose yourself to DoS.
  - anentropic 9y ago
    is that just because they don't support the features which can be used to make pathological regexes in other engines? or they have additional sanitisation or security features?
    - glangdale 9y ago
      Neither. There are regexes that can be written in the common subset supported by (say) libpcre, RE2 and Hyperscan that will induce exponential backtracking with libpcre but not with the other libraries. I'm not aware of any difference in terms of sanitisation or security.
mtve 9y ago
std::regex does not work in half of distros, boost is disaster, qt is ok. never.

phunge 9y ago

If you're interested in getting parse trees from regexes (ie all the submatch locations), check out Kleenex, it looks really interesting and is based on some new research. Full parse trees are a harder problem than matching, and one that is not a primary focus in RE2 performance AFAICS.

nly 9y ago
Isn't it true that once you have backtracking in your regex engine that there's no longer a guarantee that there's only a single parse tree? I've found the hardest part of using e.g. a recursive descent parser is having to correct captured state while backtracking.

strictfp 9y ago

Limiting the benchmark to engines supporting matching sets of regexes seems unnecessarily narrow to me. Is matching a set of regexes not equivalent to matching a single combined regex? Something like "(?:a)|(?:b)|(?:c)"? If so, why not run the test with that regex instead, and include other engines?

glangdale 9y ago
For engines like Hyperscan and RE2's underlying algorithms, alternation works the way you describe. However, for backtracking engines, alternation does not do a search in parallel for all the patterns. Instead, it winds up first looking for the first, then the second, etc., finds the first match, and declares victory. There are particular patterns and inputs where this behavior will be similar to parallel matchers like RE2::Set and Hyperscan, but the general case just won't work.
rwj 9y ago
The complication occurs when you need to identify which sub-expression matched.

rurban 9y ago

The summary is very easy: * Hyperscan is by far the fastest, but has only limited platform and regex support. * Next is pcre2 (with the jit), which is a bit faster than the new rust regex. These support all options, everywhere. * Then RE2 and all the others. RE2 has very limited regex support. Why they compare the fastest with one of the slower and limited ones is beyond my understanding. The best overview is still https://rust-leipzig.github.io/regex/2017/03/28/comparison-of-regex-engines/ https://rust-leipzig.github.io/regex/2017/03/28/comparison-o...

glangdale 9y ago
This summary was "very easy", because it is wrong. This assessment is unfair to RE2, and we're comparing to RE2 because it's the only one of these that can do multiple regex. Both Hyperscan and RE2 throw a good deal of regex under the bus in order to get multiple regex support, performance and/or streaming capability.
- burntsushi 9y ago
  Rust's regex library has had support for regex sets for quite some time, and it's based on the same "tricks" that RE2 uses: https://docs.rs/regex/0.2.2/regex/struct.RegexSet.html https://docs.rs/regex/0.2.2/regex/struct.RegexSet.html
  - glangdale 9y ago
    Oops. We're out of date in our thinking then. If the implementation is similar to re2, you'll probably see similar performance, although I hear good things about your small group literal matcher. :-)
    - burntsushi 9y ago
      :P Yeah, I would expect performance characteristics to be very similar to RE2! I actually think RegexSet disables literal optimizations in more cases than the standard regex, but it's been a while since I've touched that.

jmnicolas 9y ago

Maybe I'm not normal but I'd rather write 30 lines of readable and debugable code than use a regex. Would you embed Brainfuck in your code ? Then why do you use regexes ?

glangdale 9y ago
Regex syntax is fairly gross, I agree. That being said I'd be surprised to your open-coded version of simple regexes like /hatstand.*teakettle/ or /badgerbrush\s{12}/ was clearer than the regex, and it would almost certainly be dismally slow relative to a tuned regex implementation - unless you wrote a lot of one-off SIMD code. Further, if given a bunch of different regexes to match simultaneously, your code would have to run them one by one. Finally, quite frequently our customers/users are in a situation where they don't know what the regex is going to be, and they aren't going to let people inject arbitrary code into their applications.
- ohyes 9y ago
  A lot of the grossness is syntactic sugar, if one were so inclined they could get by with a handful of operators, and end up with something fairly clear as you demonstrated. So if anything I blame lack of good taste for regular expressions bad rep.
Xophmeister 9y ago
How do you match arbitrarily repeating patterns, which may/probably have a combinatoric expansion, without effectively writing your own parser? If you're using a language where writing a parser is relatively easy (e.g., Lisp, Haskell, etc.) or your patterns are trivial, then fair enough. Otherwise, good luck with that. For example, in Python, if I want to match "foo" followed by any number of "bar"s and/or "quux"s at the end of the string, I could write this: if re.match(r"foo(bar|quux)*$", my_string): ... ...without going to the trouble writing a recursive-descent parser or state machine, your way would be something like this: def ends_with_foo_etc(s): if s.endswith("foo"): return True after_last = len(s) - s[::-1].find("oof") if after_last > len(s): return False good_tail = True while good_tail and after_last < len(s): if s[after_last:after_last + 3] == "bar": after_last += 3 elif s[after_last:after_last + 4] == "quux": after_last += 4 else: good_tail = False return good_tail if ends_with_foo_etc(my_string): ... That's both excessively terse -- for a really simple pattern -- almost certainly slower and, most importantly, brittle in that it couples your pattern to your implementation in a non-trivial way. If your pattern changes, you may have to completely rewrite your matching function. It's also worth noting that a typical regex API will do more than just match patterns; e.g., extracting subpatterns/groups, splitting, etc.

bterlson 9y ago

Wow, oddly relevant - I've been working on a RegExp implementation in JavaScript using similar techniques (minus vectorization of course, RIP SIMD.js). There is no efficient way in JavaScript to replace many patterns (e.g. a list of sentence fragments with optional whitespace, capitalization, pluralization, etc.) against a large document where the replacement requires metadata about the subpattern that was matched (e.g. to replace a term with a link to the term's definition). I wonder if I should switch gears and try to write a native Node module for this instead. This looks really great.

glangdale 9y ago
Thanks for the kind words. You'll have to roll your own 'replace', and the all-matches semantics of Hyperscan may give you some headaches - you'll need a careful reading of our Start of Match semantics and to craft patterns that yield "less surprising results". If you can share your workload, or want assistance in figuring out whether to do this and/or how to do it, please contact us on the mailing list or on the email link for Hyperscan on 01.org. We're always interested in sample patterns, especially ones that fall outside our normal wheelhouse of 'network security and then some more network security'.
time4tea 9y ago
Well depends on how big and how fast. This worked for me https://github.com/time4tea/glossary/blob/master/README.md https://github.com/time4tea/glossary/blob/master/README.md Its a very simple Aho-Corasick text search with replacement. A similar thing in Java using Ropes rather than Strings was also ok, for some value of ok.