Hyperscan: A Fast Multi-Pattern Regex Matcher for Modern CPUs

I like the UVa guys, but MNCaRT isn't very mature and was mostly there to support the Automata Processor. Since Micron kicked that product out the door (into a startup that might be charitably described as 'moribund', Natural Intelligence Semiconductor) there's not much point in starting with that codebase.

Some customers used Hyperscan as a primary matching engine with a secondary state machine / parser behind, but I'm not at liberty to discuss specifics. In any case these guys were interested in network threat detection, not generalized parsing.

I wouldn't use RE2::Set for language parsing, as it can only tell you that certain patterns occurred, but won't give you offsets, just a single bit.

The problem with the charmingly described 'hairy parser' is that it will just be 'one damn thing after another' - a lot of code, a lot of weird semantic corners, etc. Why not just use a parser that's intended for generality - something like ANTLR? What will taping all that stuff together accomplish?

We didn't set out to create a huge codebase with weird corners with Hyperscan either, and we still got one. If you go out with the intent of building something hairy from the start.... :-/

Ah, ok, thanks.

Let's see... I'm coming at this with objectives around programming experience, rather than around parser implementation. I want to be able to do grammar design that is tightly tied to problem domain expression, rather than to parser tech. The usual dance, of adapting a pretty problem-domain grammar to available parsers, by grammar uglification, transformation, and kludgery... I'd like that to be optional - a thing of optimization, not of minimum viable effort. I'd ideally like parser design choices to escape the parser only as performance variance.

So yes, I'd love a general parser generator, that accepts any grammar, and ideally does some reasonable best-effort transformation and compilation to subengines given the mess you've handed it. I've not seen that. But since I'd not seen RE2::Set, it's perhaps been a decade since I seriously looked around, so maybe there's new niftyness?

I've tried ANTLR a couple of times over the years, at least for toys, maybe a no-templates C++ parser. (It was weird - I never figured it out, and it's not a happened with anything else, but I just viscerally disliked working with it.) Others... None were without sacrifices that required them being wrapped in hair.

So I dreamed of someone creating a parser generator toolkit, a library of engines, reusable rather than inextricably tangled in yet another parser silo. I saw Hyperscan and thought, hmm... might a toolkit come with a regexp api? :)

A rich parser doesn't have to be complex, if you sacrifice speed. A Perl 5 compatible (some old version) regexp engine can be done in a page or two of prolog. So I used to focus on expressivity, and then scramble to get back to minimally tolerable performance.

Minimum-viable compiler performance is arguably dropping dramatically now. With cloud-parallel deterministic compilation, and community-scale caching. So maybe something simple could now have viable pragmatics.

I saw Hyperscan, and was hit by old dreams of speed. Multiple wizzy subengines woven together. I'd woven in GLRs before, but multiple patterns... oooh, what leverage might might be found there?! :)

> What will taping all that stuff together accomplish?

Extensible and scoped parsing... the immensely expensive Python 2 to 3 transition was in part a design choice to avoid scoped method dispatch and file-scoped parsing of both languages. I suggest it was the wrong call.

PCRE with parse-affecting code... say rather, each time you lose a feature, some set of problems gets harder. I'd prefer that to be the harder-slower of falling back to a less-specialized engine (which sometimes isn't a problem), to the harder-go-back-and-rewrite of nonimplementation (which always is). Grammar restriction as premature optimization.

N-ary multifix operators... lets you easily parse expressions of rich operators, from Smalltalk to math. Modern IDEs seem sufficient to address puzzlement over "how and why did this (not)parse".

A "sandwich" of regexp for tokens, operator precedence parser for extensible expressions, and something backtracking for an extensible list of statements, is one way to get a somewhat traditional language parser that's more nicely extensible and expressive.

> a lot of weird semantic corners

Yes, but... I'd like the choice to avoid semantic weirdness, or not, to happen at the application level, not at the parser api level. Because it's a tradeoff. I accept the PEG argument that often simplicity and composability is the right design choice, is worth the expressive cost. But not the argument that anything PEGs can't handle is a "legacy language" which people shouldn't be using anyway (fun conversation with a PEG person).

So yes, I'd like to see programming language parsing become far richer than currently, and thus somewhat hairier. Because avoiding that is, I suggest, inflicting far greater costs elsewhere.

glangdale can probably say more, but I think the high level answer is pretty easy: re2c is intensely focused on building state machines, in their entirety, ahead of time. There's also some cool stuff that lets you integrate the state machine with the rest of your code. AFAIK, re2c sticks fairly strictly to state machines and doesn't do sophisticated optimizations like Hyperscan, particularly with respect to literals. To me, they are fundamentally solving different problems. re2c is only viable if you can actually deal with the full size of the DFAs you build.

re2c is also notable for, AIUI, having a very principled solution to the problem of submatch extraction using tagged DFAs. They wrote a paper about it: http://re2c.org/2017_trofimovich_tagged_deterministic_finite...

Does the ARM version hyperscan work well? Can you describe the detailed steps? Thanks