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

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/ (also ripgrep is awesome, and you should use it.)

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.

You can do things with these backtracking algorithms that are difficult (capturing subexpressions, start of match) or impossible (backreferences, arbitrary lookarounds) to do efficiently in an automata based algorithm.

Sometimes users want these features more than they want theoretical purity. Who are we to tell them they are wrong?

That said, we do have some projects in mind to try to bridge these two worlds (feature-rich backtracking world vs speedy/streamable automata-based). Anyone interested should contact the Hyperscan team. Make a nice project at undergraduate or even postgraduate level depending on scale.

>Why many language standard libraries use exponential algorithm is beyond my comprehension.

"Because it enables very useful features like backtracking" doesn't really sound beyond comprehension.

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.

There are some inaccuracies in this comment.

Firstly, that link shows PCRE2 and Rust's regex engine are neck-and-neck. And that's including the fact that the benchmark contains a regex that is hard for DFA engines but contains no regexes that are hard for backtrackers. (I lodged this criticism against the author of the benchmark before they published it.)

Secondly, Rust's regex crate is heavily inspired by RE2. They support roughly the same features. So if RE2 is limited, then so is Rust's regex library.

Rust's regex library tends to do a little better than RE2 in a wide variety of common use cases because of aggressive literal optimizations. But if you mask those out, performance will be comparable. (Also, if you benchmarked captures, I bet RE2 would win handedly. Rust's regex library needs some work in that area.)

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.

The complication occurs when you need to identify which sub-expression matched.

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.

std::regex does not work in half of distros, boost is disaster, qt is ok. never.

C++ says what the regex must do, but not how it should do it or what the performance should be.

To be honest, I have no idea if the "what the regex must do" description rules out particular algorithms. I suspect that, in keeping with Committee tradition, it's basically a new interface over POSIX ( http://pubs.opengroup.org/onlinepubs/7908799/xbd/re.html ). By "Committee tradition," I mean "compare 'catgets' with C++ message catalogs."

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'.

Well depends on how big and how fast.

This worked for me 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.

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.

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.

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.

Your comment is like "I don't need nails because I have screws".