performance expectations #136
Replies: 1 comment 7 replies
-
It's really hard to say without an easy reproduction at my fingertips that I can experiment with. There are so many variables that don't come through a prose description that it's just really impossible to say too much. At the number of patterns you're talking about, this library doesn't have any particularly clever tricks up its sleeve. I believe Hyperscan does, and will use a SIMD algorithm called FDR. It's on my list of things to learn more about and potentially port, but I haven't gotten around to it yet. This library does use SIMD, but only when the number of literals is much smaller (say around 100 or less). So at least, with respect to Hyperscan, I wouldn't expect this library to beat it. Hyperscan is really best in class here. Otherwise, one thing that sticks out to me is that your C implementation appears to be a DFA, but you aren't configuring this library to use a DFA. You'll want to use I will say that the overlapping case tends to have less optimization work put into it, mostly because it's just not a mode that I use often. The leftmost-first match semantics have had the most effort put into them.
The number of patterns shouldn't be an issue for this library. (I regularly test it with millions of patterns.) This library has three different implementation of Aho-Corasick:
So perhaps if you switch over to the DFA explicitly, the search speed of this library will improve a bit. But if you stick with the contiguous NFA, you might get slightly slower search speeds, but memory usage is likely substantially better. I don't know if that matters to you or not, but it's a benefit worth pointing out IMO. |
Beta Was this translation helpful? Give feedback.
-
Hi, let me start out by saying that I appreciate the work that you're doing here. Thanks a lot!
In Suricata [1], a free and open source network IDS/IPS, we heavily use multi pattern matching (mpm) to reduce the work we have to do per packet. We have traditionally used our own Aho-Corasick implementations for this [2][3] but nowadays most of our users will use the much faster Hyperscan library support.
Since the aho-corasick crate is already a transitive dependency for us, I thought it might be worth checking if we can also use it for our prefiltering mpm needs. The results have been a bit disappointing, with my best implementation using this crate being between 2.5 and 3 times slower than Hyperscan, and between 1.5 times and 2 times than our own Aho-Corasick implementation (written in C) [2].
I guess I'm looking for some feedback on this. Do these numbers seems reasonable based on other feedback or are they perhaps indicative of issues in my implementation? Since Suricata is mixed C and Rust we do have the FFI border to cross, but I would be surprised if that plays a big role based on our other experiences.
Perhaps our use case is just not very well supported. We use multiple pattern sets and the largest (and most commonly executed) ones exceed 5k to 10k patterns of very mixed quality and size, heavily using the full 8 bit alphabet.
Appreciate any feedback on this.
Oh the PR to hook aho-corasick code into Suricata's logic can be found here:
OISF/suricata@bcb8b0a#diff-afa227151ac29b6f3c5955da7506281ec1539addaccf440df81ce57f3279044cR117
Regards,
Victor
[1] https://github.com/OISF/suricata
[2] https://github.com/OISF/suricata/blob/master/src/util-mpm-ac.c#L935
[3] https://github.com/OISF/suricata/blob/master/src/util-mpm-ac-ks.c
Beta Was this translation helpful? Give feedback.
All reactions