Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

branchfree.org

Post reply on HN
Print view View original

21–30 of 37 posts

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

#21

Post by glangdale »

bratao wrote: post #5
glangdale wrote: post #2

Author here, in case anyone wants to question, abuse, argue, etc.

Thank you! I' m very excited to test in my projects ( I found a working Python extension here https://github.com/shenfe/python-hyperscan ) Let me seize the opportunity. I have a problem where I need to match multiple person names (hundreds of thousands) in huge texts. Aho-Corasick works good for exact matches. Could HyperScan works for approximated matches?

We have both Levenstein and Hamming distance parameters. Do note that putting large distance numbers is not expected to perform well (i.e. matching "Smith" at Levenstein distance = 3 won't be a happy experience).

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

#22

Post by glangdale »

burntsushi wrote: post #10
hlieberman wrote: post #8

This appears to be the same algorithm used by ripgrep ( https://github.com/BurntSushi/ripgrep ) for searching when SIMD/AVX is enabled. Specifically, it uses the algorithm Teddy from the library that’s derived from this paper.

ripgrep author here. Yes, the Teddy algorithm was originally extracted from Hyperscan. But this is a teeny tiny piece of Hyperscan. And AFAIK, ripgrep's implementation (which is actually in the underlying regex library) doesn't carry over the full Teddy algorithm. Or so I've been told. :-)

Imma keep telling you until you grab my merge logic. :-)

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

#23

Post by glangdale »

classichasclass wrote: post #15

"Hyperscan Things That Didn’t Make It Into Open Source Hyperscan ... Ports to non-x86 platforms." This is a big shame, and undercuts the title. Is there any way to release the older stuff so that interested folks can work on it to bring the other arches up to parity? I'm a Power ISA bigot in particular but not having an ARM port seems like a big gap.

I suppose "Some Modern CPUs" was too long-winded a title?

As I said, it doesn't take a genius to understand Intel's motivations. They bought the project, after all.

Not being @ Intel anymore, I don't have access to the older stuff, and even if I did, the codebase has diverged significantly since.

Without going on too much of a tirade - the experience of developing for all those platforms really sucked. Almost all the non-x86 platforms had significant bugs in their toolchains. One of the MIPS variants (particular architecture elided to spare the guilty) had bugs in their gcc intrinsics in a way that suggested that no-one had ever done any significant third-party dev on the platform.

Big-endian was also a huge PITA.

It was a ton of work to keep all those systems alive, and our machine rack looked like a zoo of dev boards and weirdo devices.

In the "ure3" system I mention, I would make retargetability/portability to other systems a first-class goal.

One way of achieving this is not having such a huge profusion of methods and complexity. Hyperscan is over-engineered for many use cases if you aren't a network company looking to scan 5,000 complex regexes in streaming mode at hopefully maximal performance.

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

#25

Post by glangdale »

acuozzo wrote: post #17
glangdale wrote: post #2

Author here, in case anyone wants to question, abuse, argue, etc.

I ported Hyperscan to ARM several months ago with help from the following project: https://github.com/nemequ/simde Would you be interested in working together to get an ARM port that's a bit cleaner and author-approved?

I understand this possibility, but it's not the way I would do an ARM port in an ideal world.

Being the original designer of Hyperscan isn't much help; I don't work at Intel any more and wouldn't have all that much clout in trying to get an ARM port into the codebase.

I'm thinking about building a followup regex matcher - considerably smaller scale, and starting with a Hyperscan code base for the tools/infrastructure/boring bits - ("ure3"). This would definitely have ARM as a first-class architecture. Anyone 64-bit and little-endian can play, I would think (legacy stuff like 32-bit, etc can go somewhere else).

I just with the ARM guys would get their shit together and support their own much ballyhooed SVE. The idea of announcing something in 2016 and not supporting it in a server chip that's due for mid-2020 is... novel.

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

#26

Post by glangdale »

ianhowson wrote: post #7
j0hnml wrote: post #6

Earlier quoted context omitted.

Well, it kinda is. AFAIK, that’s exactly what this was made for, and Intel/McAfee was going to create a DPI device using this tech. That never happened, and now Snort uses/will use hyperscan for its pattern matcher

Hello, fellow Sensory employee!

We are everywhere...

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

#27

Post by taleinat »

bratao wrote: post #19
taleinat wrote: post #18

Earlier quoted context omitted.

Have you tried some existing Python libraries which support fuzzy searching, such as regex and fuzzysearch?

Yes. Both grow the complexity linearly/exponentially based on the number of patterns to be searched.

Ah. You should likely use a different algorithmic approach.

If you add contact details to your user info I'll be happy to get in touch and help.

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

#28

Post by mncharity »

I'm drawn to hairy parsers for implementing DSL-rich syntactically-extensible programming languages. Hairy, as in, extensible and scoped; full-ish Perl-compatible RE, including parse-influencing code execution; n-ary multifix operator precedence; backtrack/operator-precedence/regex sandwiches. Subengines can be used to variously strength reduce parts of the grammar, and to dynamically prune search. It's been some years, so I'm out of date...

Does anyone have experience with MNCaRT? [1] I've long wished for a toolkit for doing grammar analysis and building assemblages of specialized high-performance engines into relatively performant parsers.

Has there been work on using multiple-pattern RE engines (like RE2::Set or Hyperscan) in some context similar to language parsing? Or as subengines of a larger parser?

Thanks.

[1] https://web.eecs.umich.edu/~weimerw/p/weimer-mncart.pdf https://github.com/kevinaangstadt/MNCaRT

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

#29

Post by femto »

glangdale wrote: post #2

Author here, in case anyone wants to question, abuse, argue, etc.

The reference to "Australian-free" has piqued my curiosity. Do you care to elaborate? In my imagination you had an Australian collaborator that you fell out with and have been busy expunging all "Australian" code from the project!

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

#30

Post by glangdale »

femto wrote: post #29
glangdale wrote: post #2

Author here, in case anyone wants to question, abuse, argue, etc.

The reference to "Australian-free" has piqued my curiosity. Do you care to elaborate? In my imagination you had an Australian collaborator that you fell out with and have been busy expunging all "Australian" code from the project!

I am Australian, as is the original technical team for Hyperscan. As of March 2018, no member of that team is still at Intel.

Expunging Australian code from Hyperscan would be a non-trivial task.

Post reply on HN