4 ms·

There is definitely some room. As usual, it depends. I'm away from the computer, so I haven't had a chance to look and see if the OP's benchmarks are published.

There is definitely some room. As usual, it depends. I'm away from the computer, so I haven't had a chance to look and see if the OP's benchmarks are published. So it's hard for me to say anything specific at the moment. In the literature, there are generally two different variants of Aho-Corasick. The traditional formulation follows failure transitions during search, which comes with overhead. In effect, it's an NFA since search can traverse through multiple states for each byte of input that it sees. The other variant is the "advanced" form, which is just effectively turning the NFA into a DFA by precomputing all of the failure transitions into a single table. This can be quite a bit faster depending on the workload, but obviously uses more memory and takes more time to build. My library supports the DFA version, but it had a bug (which has now been fixed) which prevented the OP from effectively benchmarking it. The OP hints that some substantial number of samples use a very small number of patterns. Sometimes only one. In that case, it probably wouldn't be best to use Aho-Corasick at all. Instead, it should use an optimized single substring search algorithm, such as Two Way. Even for multiple patterns, if there aren't that many of them, it might be better to use Teddy from Hyperscan. This article is fairly timely. I'm almost done a rewrite of my Aho-Corasick library. It will bring some small performance improvements (but more importantly a simpler API), and I hope to move the Teddy algorithm into it at some point. As always, specific workloads can often have their performance improved quite a bit.

wuschel 8y ago
Dear burntsushi, many thanks for your contribution. I was not expecting to see such an extensive elaboration. Looking forward to see your rewrite, and learn something from it! Cheers!
ruuda 8y ago
Thanks for the elaborate reply! Our benchmark input data contains customer data which we cannot share, but we could share the benchmark program. The DFA approach is something that I had not heard about before (I never looked into what "full" meant), but we should definitely try it; we reuse the automaton against possibly millions of haystacks, so extra memory or preprocessing time is likely worth it. Thanks for pointing this out! An adaptive approach would indeed work better for fewer needles, but the threshold depends a lot on the data. We compared Alfred–Margaret against ICU regexes for case-insensitive replaces, and we found that even for a single needle, ours was faster in half of the cases. (It is a bit unfair because of FFI call overhead.)
glangdale 8y ago
You should borrow "FDR" from Hyperscan as well. :-) AC sucks. It's simple enough, but it's always going to be either slow or big - sometimes both. I'd say that's a source of frustration to me, but it's not really, as we made a lot of money selling string matching to customers back when Hyperscan was closed-source. It's so much easier to sell string matching than regex matching as regexes are full of surprises, but strings are quite tractable. I'm not delighted with where we left string matching in Hyperscan - "FDR" was wheezing under load in a bunch of ways, and I had some better things in the pipeline. But it still should generally murder AC barring some corner cases. Unfortunately, Hyperscan has moved away from having a pure-play literal matcher in it (what remains is really more of a specialist 1- to 8-char literal matcher), which I regard as a semi-mistake (so there may be more corner cases than there used to be).
- burntsushi 8y ago
  I thought FDR was for single literals only? One of the hurdles for using the algorithms from Hyperscan is that it's not always clear when particular algorithms are used and in what conditions. I have the same problem in my regex library, but Hyperscan takes it to another level because it's so much more sophisticated. :)
  - glangdale 8y ago
    (see other response) FDR is for > literals than Teddy. It's Noodle that's for single literals. Hard to imagine how you could get confused given that the names we chose are so transparent. :-)
    - burntsushi 8y ago
      Hah. I've only made it halfway through your paper so far. Excited to read the rest. :)

wuschel 8y ago

Dear burntsushi, many thanks for your contribution. I was not expecting to see such an extensive elaboration. Looking forward to see your rewrite, and learn something from it! Cheers!

ruuda 8y ago

Thanks for the elaborate reply! Our benchmark input data contains customer data which we cannot share, but we could share the benchmark program. The DFA approach is something that I had not heard about before (I never looked into what "full" meant), but we should definitely try it; we reuse the automaton against possibly millions of haystacks, so extra memory or preprocessing time is likely worth it. Thanks for pointing this out! An adaptive approach would indeed work better for fewer needles, but the threshold depends a lot on the data. We compared Alfred–Margaret against ICU regexes for case-insensitive replaces, and we found that even for a single needle, ours was faster in half of the cases. (It is a bit unfair because of FFI call overhead.)

glangdale 8y ago

You should borrow "FDR" from Hyperscan as well. :-) AC sucks. It's simple enough, but it's always going to be either slow or big - sometimes both. I'd say that's a source of frustration to me, but it's not really, as we made a lot of money selling string matching to customers back when Hyperscan was closed-source. It's so much easier to sell string matching than regex matching as regexes are full of surprises, but strings are quite tractable. I'm not delighted with where we left string matching in Hyperscan - "FDR" was wheezing under load in a bunch of ways, and I had some better things in the pipeline. But it still should generally murder AC barring some corner cases. Unfortunately, Hyperscan has moved away from having a pure-play literal matcher in it (what remains is really more of a specialist 1- to 8-char literal matcher), which I regard as a semi-mistake (so there may be more corner cases than there used to be).

burntsushi 8y ago
I thought FDR was for single literals only? One of the hurdles for using the algorithms from Hyperscan is that it's not always clear when particular algorithms are used and in what conditions. I have the same problem in my regex library, but Hyperscan takes it to another level because it's so much more sophisticated. :)
- glangdale 8y ago
  (see other response) FDR is for > literals than Teddy. It's Noodle that's for single literals. Hard to imagine how you could get confused given that the names we chose are so transparent. :-)
  - burntsushi 8y ago
    Hah. I've only made it halfway through your paper so far. Excited to read the rest. :)