4 ms·
Intel Hyperscan is a high-performance multiple regex matching library
- gnfargbl 4y agoOne of the Hyperscan developers commented on HN slightly over a year ago [1] that Intel had basically abandoned Hyperscan due to lack of sufficiently vocal customer interest. I hope that has changed, or is in the process of changing, because Hyperscan remains amazing. [1] https://news.ycombinator.com/item?id=27421665 https://news.ycombinator.com/item?id=27421665
- jiggawatts 4y agoNot enough three letter agencies in the US to fund big brother at scale? (One if the use cases of this library is scanning through bulk intercept data streams for a set of key words.)
- deleted 4y ago[deleted]
- Lammy 4y agoBest throw away all your CPUs then too: https://groups.google.com/g/comp.arch/c/UXEi7G6WHuU/m/Z2z7fC7Xhr8J https://groups.google.com/g/comp.arch/c/UXEi7G6WHuU/m/Z2z7fC... https://vaibhavsagar.com/blog/2019/09/08/popcount/ https://vaibhavsagar.com/blog/2019/09/08/popcount/ https://arxiv.org/abs/1611.07612 https://arxiv.org/abs/1611.07612
- jandrese 4y agoThe official repo[1] is looking pretty dead. Edit: This is a surprisingly heavy build. Over 15 minutes on my somewhat older i5. I suggest using make -j instead of cmake -build to speed it up. Decent number of compiler warnings too. [1] https://github.com/intel/hyperscan https://github.com/intel/hyperscan
- Cu3PO42 4y agoIn sufficiently new versions of cmake you can use cmake --build -j as well. It will be translated to whatever argument is required for the underlying build system to use parallel compilation, e.g. -j for make and -m for msbuild.
- jandrese 4y agoIt just seemed excessive for a regular expression library. For comparison the most recent version of PCRE built in almost exactly 26 seconds. Sadly the hyperscan build crapped out for me in the linking phase, failing to find a bunch of coreX and avx optimized memset functions.
- KerrAvon 4y agoThat post and the ensuing discussion are somewhat depressing. I am curious as to how the team's progress was measured; did the team's manager not know they needed to solicit user testimonials? Someone had to be responsible for the existence of the team and their productivity. What was the disconnect?
- fred123 4y agoSomewhat related: I built a library to speed up matching many regexes with mostly mismatches by adding non-regex pre matchers. https://github.com/Quantco/multiregex https://github.com/Quantco/multiregex
- cl0ckt0wer 4y agoC# has also recently put a lot of work into speeding up regex. MS put up a post about it a while ago going into the specifics. I expected the vectorization. I did not expect source code generation. https://devblogs.microsoft.com/dotnet/regular-expression-improvements-in-dotnet-7/ https://devblogs.microsoft.com/dotnet/regular-expression-imp...
- neonsunset 4y agoSeconding the comment, .NET 7 has seen massive improvements to Regex performance on all platforms supported by .NET. Char sequence matching will use respective SSE4/AVX2/AdvSimd instruction sets and for compiled regexes, efficient automata will be emitted. Those two combined produce state-of-the-art regex matching performance.
- vinkelhake 4y agoThere's also Vectorscan[1], which is a fork of Hyperscan that runs on more platforms. [1] https://github.com/VectorCamp/vectorscan https://github.com/VectorCamp/vectorscan
- smoldesu 4y agoI'd be really curious to see how it optimizes for ARM. x86 is great for kitchen-sink optimizations like this, but with ARM you have a much smaller extension set to target. Hell, you'd probably be stuck with NEON unless you figured out a way to GPU-accelerate the process.
- rurban 4y agoEsp. AMD, as Intel refused to accept AMD patches. So Hyperscan is effectively dead, the maintainer is also long gone. VectorScan is its successor.
- twhitmore 4y agoCapturing is not supported. That eliminates many normal regex usecases, where you want to be able to capture & interpret the data.
- pritambaral 4y agoCapturing can be supported by using another regex library in conjunction. Use Vectorscan/Hyperscan to eliminate most of the search space, then run a (slower) more featureful regex matcher where the former tells you is a match to extract information. After all, Hyperscan's original objective was to be able to find where, in a large input, any of many patterns may match. It doesn't really make sense to use it as a general purpose regex library, because it wasn't built for that.
- ramblerman 4y agoAt scale though? And even if that were the case you could grab your sentences from the 1TB file in front of you with hyperscan, and then do a capture on the results.
- dang 4y agoRelated: Hyperscan: High-performance multiple regex matching library from Intel - https://news.ycombinator.com/item?id=21873557 https://news.ycombinator.com/item?id=21873557 - Dec 2019 (53 comments) Hyperscan: A Fast Multi-Pattern Regex Matcher for Modern CPUs - https://news.ycombinator.com/item?id=19270199 https://news.ycombinator.com/item?id=19270199 - Feb 2019 (36 comments) Multiple regex performance shootout: RE2 vs. Intel's Hyperscan - https://news.ycombinator.com/item?id=14608663 https://news.ycombinator.com/item?id=14608663 - June 2017 (55 comments) Hyperscan, a high-performance multiple regex matching library - https://news.ycombinator.com/item?id=10420295 https://news.ycombinator.com/item?id=10420295 - Oct 2015 (19 comments)
- kissgyorgy 4y agoIn our firmware extraction suite, we started searching patterns with Yara, but it was so slow we switched to Hyperscan: https://github.com/onekey-sec/unblob/blob/main/unblob/finder.py https://github.com/onekey-sec/unblob/blob/main/unblob/finder... We are quite happy with the huge performance boost, never looking back :) Yara was even segfaulted when we tried to extract an Ubuntu ISO image with it, never had problems like that with Hyperscan. The only problem with Hyperscan is that it only supports Intel CPUs (it has some hand-crafted assembly), so it doesn't work on Apple M1 Macs, but there is a fork called VectorScan, which is working on ARM: https://github.com/VectorCamp/vectorscan https://github.com/VectorCamp/vectorscan We implemented a couple of small DSL classes in Python to be able to define YARA-like rules, it might be useful for you too, check it out here: https://github.com/onekey-sec/unblob/blob/cdd7a46667ffdfdfae7bba8254ec8b38ac47c01f/unblob/models.py#L222 https://github.com/onekey-sec/unblob/blob/cdd7a46667ffdfdfae...
- mattewong 4y agoSecond the support for vectorscan. And FWIW, I have posted issues in both hyperscan and vectorscan repos, and the only responses came from vectorscan (and quite quickly).
- JackC 4y agoPSA that the python bindings for hyperscan need maintainers: https://github.com/darvid/python-hyperscan/issues/44 https://github.com/darvid/python-hyperscan/issues/44