6 ms·

Hyperscan, a high-performance multiple regex matching library

48 points by jsnell 11y ago

jonstewart 11y ago
Neat! There's also Lightgrep. https://github.com/LightboxTech/liblightgrep https://github.com/LightboxTech/liblightgrep Lightgrep also supports a subset of PCRE and scales pretty well with the number of patterns (has done millions of fixed strings). Lightgrep is designed for digital forensics, so it searches data as a binary stream. Lightgrep also supports searching for patterns in multiple encodings, with no requirements on the underlying data. Lightgrep is GPL. (I'm one of the authors of Lightgrep.)
- mebrahim 11y ago
  Does lightgrep return which one(s) of the millions of patterns has matched the input?
rch 11y ago
The docs state that it's comparable to RE2, and others, but I don't see benchmarks yet. Is it fair to assume it's faster, or is there a tradeoff to emphasize the streaming features?
- jonstewart 11y ago
  RE2 isn't a multipattern engine. That's the big difference. You can join a bunch of patterns together with | in RE2, but there's a precedence so it will only tell you about the first one to hit and won't tell you which one. Also, RE2 hits the wall with joining patterns together like this (depends on the patterns, of course). Comparing multipattern and single pattern engines is a bit apples and oranges. I haven't run HyperScan but it looks like it should be very fast. It greatly depends on the patterns selected. It also looks like HyperScan has pragmatically sacrificed some aspects of PCRE compatibility/correctness wrt/ matching in order to achieve performance.
  - glangdale 11y ago
    We sacrifice features and compatibility. We have sacrificed zero correctness as far as we are aware. We maintain wart-for-wart compatibility with libpcre in order to have a good basis for comparison for fuzzing and we believe we 100% recognize libpcre constructs even when ww don't support them. Our semantics differ, but roughly speaking, we provide the set of matches that libpcre would if you hook up a callout to libpcre that rejects each match and sends libpcre back to look for another match (our ordering will be different, but is also well defined).
    - jonstewart 11y ago
      If a pattern uses quantification and the match extends successfully, won't two matches be reported (instead of one)? That's what I mean--not that it's buggy. As I'm sure you know quite well, deciding when matches can be reported is quite tricky, especially with Perl's ordered alternation rules. A few questions: - What kind of overhead is actually implied by using start of matches in streaming mode? - Is the backend a machine code JIT of the automaton, an interpreter, a table-driven search, or...? - Why not lazy quantifiers? They're almost always preferable to greedy quantification in a streaming scenario. cheers, Jon
      - glangdale 11y ago
        Sorry - might have sounded a bit defensive there. We've seen a few systems that have a tendency to sweep correctness under the carpet with shortcuts, especially when you hit nasties like "large bounded repeats in streaming mode". Start of Match (SoM) in streaming mode is a real bear for some patterns. It really depends on the pattern - some are free, others (that we would otherwise support) are very expensive or impossible. Our SoM is fully general (i.e. it doesn't time out or give up after N bytes or K stream writes) so the worst case means tracking lots of 64-bit offsets through our automata. The backend is a big pile of code that coordinates the efforts of many different automata and subsystems, most of which are a combination of a C implementation plus a big table of some sort to implement NFA/DFA/literal matcher/whatever. This isn't something of which we are particularly proud. We would like to make this a lot simpler and more interpreter-based. A JIT would be really cool but we had some reluctance in our user base to run arbitrary code. I would be fascinated to support a JIT project even if it's not on our mainline. I respectfully differ on lazy vs greedy. In streaming mode, both require information that's expensive to maintain and imply that you can 'predict the future' (especially once you put a complex pattern after the lazy quantifier). We've been using "automata semantics" for a long time and this is simple and easy to keep track of in streaming mode. Capturing semantics and lazy/greedy simulation are a work in progress for us. We used to have more work in this area but we did't have a strong demand for it. We do have some IP in this that isn't in Hyperscan - I may blog about this soon. We did have a subsystem that got 100% compatibility for some patterns ("100% right, 50% of the time"?) in block mode for libpcre that covered quantifer semantics and capturing subexpressions.
- glangdale 11y ago
  Hi - Hyperscan lead architect here. Performance numbers will follow but we do need to be careful about sweeping claims. With the variety of regular expression workloads making a blanket claim about performance is like saying "my C compiler always produces code that's 25% faster than yours". That being said, we don't pay that much performance cost for generality relative to non streaming, single pattern engines in terms of performance. Mainly the cost is complexity of our solution and pattern support.
trishume 11y ago
One application this could work really well for is syntax highlighting. Textmate/Sublime syntax files are basically lists of hundreds of regexes that have to be matched very quickly over the same content. With this library it might be possible for an open source editor beat Sublime text at highlighting using the same grammars. Which is saying something since Sublime is crazy fast and the highlighter is even parallelized.
- finnh 11y ago
  even if Sublime doesn't need it ... vim sure does!
- glangdale 11y ago
  Hyperscan is likely a bit heavyweight for this application. Anything that only needs to keep up with user input for a small number of patterns would probably be better off with a lightweight solution with wider pattern support. Although we would be interested in seeing the integration...
- varunramesh 11y ago
  Atom needs something like this - it often hangs on very large files. For now, syntax highlighting performance is still an open issue - https://github.com/atom/atom/issues/979 https://github.com/atom/atom/issues/979
- jonstewart 11y ago
  Interactive highlighting is probably not the right thing, but it would be good when first opening a large file. I suspect most of the overhead, though, is just in maintaining state related to the highlighted sections and not in the initial matching, but maybe. Another neat application might be ad blocking extensions, where there are bajillions of rules. The text is small, but the rules update infrequently enough to make it worthwhile and there are so many repeated requests from a page load that a smidgen improvement in evaluation could lead to a perceptible page load decrease.

48 points by jsnell 11y ago

Neat! There's also Lightgrep. https://github.com/LightboxTech/liblightgrep https://github.com/LightboxTech/liblightgrep Lightgrep also supports a subset of PCRE and scales pretty well with the number of patterns (has done millions of fixed strings). Lightgrep is designed for digital forensics, so it searches data as a binary stream. Lightgrep also supports searching for patterns in multiple encodings, with no requirements on the underlying data. Lightgrep is GPL. (I'm one of the authors of Lightgrep.)

mebrahim 11y ago
Does lightgrep return which one(s) of the millions of patterns has matched the input?

rch 11y ago

The docs state that it's comparable to RE2, and others, but I don't see benchmarks yet. Is it fair to assume it's faster, or is there a tradeoff to emphasize the streaming features?

jonstewart 11y ago
RE2 isn't a multipattern engine. That's the big difference. You can join a bunch of patterns together with | in RE2, but there's a precedence so it will only tell you about the first one to hit and won't tell you which one. Also, RE2 hits the wall with joining patterns together like this (depends on the patterns, of course). Comparing multipattern and single pattern engines is a bit apples and oranges. I haven't run HyperScan but it looks like it should be very fast. It greatly depends on the patterns selected. It also looks like HyperScan has pragmatically sacrificed some aspects of PCRE compatibility/correctness wrt/ matching in order to achieve performance.
- glangdale 11y ago
  We sacrifice features and compatibility. We have sacrificed zero correctness as far as we are aware. We maintain wart-for-wart compatibility with libpcre in order to have a good basis for comparison for fuzzing and we believe we 100% recognize libpcre constructs even when ww don't support them. Our semantics differ, but roughly speaking, we provide the set of matches that libpcre would if you hook up a callout to libpcre that rejects each match and sends libpcre back to look for another match (our ordering will be different, but is also well defined).
  - jonstewart 11y ago
    If a pattern uses quantification and the match extends successfully, won't two matches be reported (instead of one)? That's what I mean--not that it's buggy. As I'm sure you know quite well, deciding when matches can be reported is quite tricky, especially with Perl's ordered alternation rules. A few questions: - What kind of overhead is actually implied by using start of matches in streaming mode? - Is the backend a machine code JIT of the automaton, an interpreter, a table-driven search, or...? - Why not lazy quantifiers? They're almost always preferable to greedy quantification in a streaming scenario. cheers, Jon
    - glangdale 11y ago
      Sorry - might have sounded a bit defensive there. We've seen a few systems that have a tendency to sweep correctness under the carpet with shortcuts, especially when you hit nasties like "large bounded repeats in streaming mode". Start of Match (SoM) in streaming mode is a real bear for some patterns. It really depends on the pattern - some are free, others (that we would otherwise support) are very expensive or impossible. Our SoM is fully general (i.e. it doesn't time out or give up after N bytes or K stream writes) so the worst case means tracking lots of 64-bit offsets through our automata. The backend is a big pile of code that coordinates the efforts of many different automata and subsystems, most of which are a combination of a C implementation plus a big table of some sort to implement NFA/DFA/literal matcher/whatever. This isn't something of which we are particularly proud. We would like to make this a lot simpler and more interpreter-based. A JIT would be really cool but we had some reluctance in our user base to run arbitrary code. I would be fascinated to support a JIT project even if it's not on our mainline. I respectfully differ on lazy vs greedy. In streaming mode, both require information that's expensive to maintain and imply that you can 'predict the future' (especially once you put a complex pattern after the lazy quantifier). We've been using "automata semantics" for a long time and this is simple and easy to keep track of in streaming mode. Capturing semantics and lazy/greedy simulation are a work in progress for us. We used to have more work in this area but we did't have a strong demand for it. We do have some IP in this that isn't in Hyperscan - I may blog about this soon. We did have a subsystem that got 100% compatibility for some patterns ("100% right, 50% of the time"?) in block mode for libpcre that covered quantifer semantics and capturing subexpressions.
glangdale 11y ago
Hi - Hyperscan lead architect here. Performance numbers will follow but we do need to be careful about sweeping claims. With the variety of regular expression workloads making a blanket claim about performance is like saying "my C compiler always produces code that's 25% faster than yours". That being said, we don't pay that much performance cost for generality relative to non streaming, single pattern engines in terms of performance. Mainly the cost is complexity of our solution and pattern support.

trishume 11y ago

One application this could work really well for is syntax highlighting. Textmate/Sublime syntax files are basically lists of hundreds of regexes that have to be matched very quickly over the same content. With this library it might be possible for an open source editor beat Sublime text at highlighting using the same grammars. Which is saying something since Sublime is crazy fast and the highlighter is even parallelized.

finnh 11y ago
even if Sublime doesn't need it ... vim sure does!
glangdale 11y ago
Hyperscan is likely a bit heavyweight for this application. Anything that only needs to keep up with user input for a small number of patterns would probably be better off with a lightweight solution with wider pattern support. Although we would be interested in seeing the integration...
varunramesh 11y ago
Atom needs something like this - it often hangs on very large files. For now, syntax highlighting performance is still an open issue - https://github.com/atom/atom/issues/979 https://github.com/atom/atom/issues/979
jonstewart 11y ago
Interactive highlighting is probably not the right thing, but it would be good when first opening a large file. I suspect most of the overhead, though, is just in maintaining state related to the highlighted sections and not in the initial matching, but maybe. Another neat application might be ad blocking extensions, where there are bajillions of rules. The text is small, but the rules update infrequently enough to make it worthwhile and there are so many repeated requests from a page load that a smidgen improvement in evaluation could lead to a perceptible page load decrease.