4 ms·

Let me start by saying that I am a big fan of BurntSushi’s work, and this post was by no means intended to detract from that. If anything, it set a high bar for

by ruuda 8y ago

Let me start by saying that I am a big fan of BurntSushi’s work, and this post was by no means intended to detract from that. If anything, it set a high bar for us. I don’t have much to add to BurntSushi’s reply. I studied the implementation briefly to take inspiration from when we decided to write our own, and there is no obvious low-hanging fruit. One small thing is that it uses a Vec of transitions per state. In Alfred–Margaret we pack all transition tables together in one array (with a separate array that maps state to start index), so it can use the cache more efficiently. There are ways to do parallel automaton traversal with SIMD, but it only works for a very small number of states.

burntsushi 8y ago
Thanks for the kind words. :) Yeah, the DFA packs everything into a single table. The NFA keeps them distinct so that it can support a dense representation near the root of the trie (for speed) but a sparse representation farther away from the root (for smaller memory footprint). (Confusingly, "dense" and "sparse" are flipped in the source code, much to my chagrin.) It would be possible to convert this into contiguous memory, but I'm not sure it's worth it. Beyond that, the other possible (maybe micro) optimizations in this realm are: 1. Use equivalence classes of bytes for your state transitions instead of all possible byte values. However, this is only applicable in a dense representation, and even then, if your alphabet is 2^16 instead of 2^8, it's not clear how much this helps. Byte classes require an extra lookup at search time, but the decreased size of the automaton can be dramtic, which has means better locality and overall better performance. But again, this is compared to the typical dense representation which is probably not relevant in your case. 2. Premultiply state identifiers. Again, probably only pertinent for a dense representation. Although, it sounds like this could eliminate your extra table that maps state identifiers to start indices. The only real downside of this is that it potentially increases the minimum required integer size to represent state identifiers. But that's only relevant if you support using smaller integer sizes for state identifiers in the first place. 3. Rearrange the states such that all match states precede all non-match states (with perhaps an exception or two for the fail/dead states, depending on how you implement Aho-Corasick). In the core match loop, a match state can be determined with a comparison against a fixed integer that's probably in a register instead of a memory access. With all that said, the best possible next step for y'all is to probably switch to a dense representation. But that might imply finding a way to efficiently use UTF-8 since a dense representation with a 2^16 sized alphabet is tricky. All of this stuff should be available in my rewrite of the crate. It's also in my regex-automata crate.
unhammer 8y ago
Cf. parallel automaton traversal, there's a talk on doing that in Haskell at https://www.youtube.com/watch?v=b4bb8EP_pIE&feature=youtu.be&list=PLOvRW_utVPVlMaey1LnM1FWGnJwztEz5O https://www.youtube.com/watch?v=b4bb8EP_pIE&feature=youtu.be... slides: https://github.com/Gabriel439/slides/blob/master/zurihac/slides.md https://github.com/Gabriel439/slides/blob/master/zurihac/sli... based on a very readable paper https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...

by ruuda 8y ago

burntsushi 8y ago

Thanks for the kind words. :) Yeah, the DFA packs everything into a single table. The NFA keeps them distinct so that it can support a dense representation near the root of the trie (for speed) but a sparse representation farther away from the root (for smaller memory footprint). (Confusingly, "dense" and "sparse" are flipped in the source code, much to my chagrin.) It would be possible to convert this into contiguous memory, but I'm not sure it's worth it. Beyond that, the other possible (maybe micro) optimizations in this realm are: 1. Use equivalence classes of bytes for your state transitions instead of all possible byte values. However, this is only applicable in a dense representation, and even then, if your alphabet is 2^16 instead of 2^8, it's not clear how much this helps. Byte classes require an extra lookup at search time, but the decreased size of the automaton can be dramtic, which has means better locality and overall better performance. But again, this is compared to the typical dense representation which is probably not relevant in your case. 2. Premultiply state identifiers. Again, probably only pertinent for a dense representation. Although, it sounds like this could eliminate your extra table that maps state identifiers to start indices. The only real downside of this is that it potentially increases the minimum required integer size to represent state identifiers. But that's only relevant if you support using smaller integer sizes for state identifiers in the first place. 3. Rearrange the states such that all match states precede all non-match states (with perhaps an exception or two for the fail/dead states, depending on how you implement Aho-Corasick). In the core match loop, a match state can be determined with a comparison against a fixed integer that's probably in a register instead of a memory access. With all that said, the best possible next step for y'all is to probably switch to a dense representation. But that might imply finding a way to efficiently use UTF-8 since a dense representation with a 2^16 sized alphabet is tricky. All of this stuff should be available in my rewrite of the crate. It's also in my regex-automata crate.

unhammer 8y ago

Cf. parallel automaton traversal, there's a talk on doing that in Haskell at https://www.youtube.com/watch?v=b4bb8EP_pIE&feature=youtu.be&list=PLOvRW_utVPVlMaey1LnM1FWGnJwztEz5O https://www.youtube.com/watch?v=b4bb8EP_pIE&feature=youtu.be... slides: https://github.com/Gabriel439/slides/blob/master/zurihac/slides.md https://github.com/Gabriel439/slides/blob/master/zurihac/sli... based on a very readable paper https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...