aho-corasick

transitions (and thus treat it as a trie), but the code is still there to deal with failure transitions. So that may have deleterious effects. * The contiguous NFA also specializes its transition function depending on the size of the node. It would be interesting to see whether these techniques would be useful for trie-hard to play with. But there is definitely a benefit to keeping one simple and fast code path for all node types. (Less branching.) * The aho-corasick crate does also expose a DFA directly: https://docs.rs/aho-corasick/latest/aho_corasick/dfa/struct.... --- In theory this should do less work per transition than trie-hard, and so it would be very interesting to measure its perf when compared to trie-hard. The main downside is that it's a DFA and can use up a lot more memory and take longer to build. It seems like Cloudflare cares less about that in favor of optimizing read perf though, so it's not clear why they didn't go this route. * The aho-corasick crate doesn't let you store arbitrary values. You only get back a PatternID when a match occurs. So to get equivalent functionality as trie-hard, you'd need a separate map of PatternID->YourValue. Since that isn't stored with the data in the trie, this alone might penalize you quite a bit with poorer CPU cache performance. * trie-hard seems to provide some customization options for its representation. i.e., Let's you use a `u8` to store its transitions versus a `u128` or `u256`. This might also help with cache usage for a small enough trie.

to setup failure transitions. Making construction substantially faster probably requires some kind of innovation in those two parts at a fundamental level. You can also cheat at this. That is, by designing your Aho-Corasick automaton to be zero-copy deserializable. The DFAs in regex-automata support this. I waver on whether to do this for aho-corasick, because it acts like a straight-jacket for evolving the internals of the library.

from a non-contiguous NFA to a contiguous NFA is, relatively speaking, pretty cheap. The only real reason to not use a contiguous NFA is that it can't represent as many patterns as a non-contiguous NFA. (Because of the compression tricks it uses.) The interesting bits start here: https://github.com/BurntSushi/aho-corasick/blob/f227162f7c56...

n that you know is less memory efficient. (What I'm talking about here is something I called a "non-contiguous NFA." The aho-corasick crate also has a "contiguous NFA" and a DFA. The "contiguous NFA" uses one contiguous `Vec` allocation with a bunch of bit-packing tricks.) But then someone actually reported an issue on the `ahocorasick_rs`[2] Python project (bindings to the `aho-corasick` crate) that the `pyahocorasick`[3] Python package (with a bespoke C implementation of Aho-Corasick) was using _substantially_ less memory. The contiguous NFA was still doing better, but the _peak_ memory usage of `ahocorasick_rs` was much much bigger than `pyahocorasick`. That prompted me to investigate and figure out what the heck was going wrong. (And this is one reason why benchmarks comparing tools or libraries are actually useful beyond just advertisements or flexing. They alert you to what is possible, and thus possibly push you to find bugs in your current implementation that might be otherwise easy to miss. In other words, benchmark comparisons can turn unknown unknowns into known unknowns.) So since this prompted me to look very carefully at memory usage, I noticed that the memory usage reported by `AhoCorasick::memory_usage`[4] was substantially smaller than peak RSS memory usage in a simple reproduction program of the original issue reported to `ahocorasick_rs`. I eventually figured out that was because of the excess capacity used by a zillion tiny `Vec`s in the non-contiguous representation. I fixed _most_ of that by calling `shrink_to_fit()`. But as the commit linked above notes, it wasn't really feasible to call `shrink_to_fit()` on all `Vec`s because that ended up with a non-trivial impact on construction time. And on top of all of that, memory usage was still worse than `pyahocorasick`. But why was I using a bunch of little `Vec`s in the first place? It's because this is the "non-contiguous" NFA. This is the thing that gets built from a list of patterns by first building a trie then filling in the failure transitions. That trie construction really demands random access mutation, which puts a constraint on your data structure choices. Plus, I had designed the contiguous NFA as a release valve of sorts that lifts this constraint. So I reasoned, "sure, the non-contiguous NFA isn't designed to be fast. It just needs to get us started." But still, `pyahocorasick` only has one Aho-Corasick implementation (the `aho-corasick` crate has 3). So it must be doing something differently. It turns out that `pyahocorasick` uses linked lists! THE HORROR! But actually, they are a really good solution to this problem. As a Rust programmer, I reach for `Vec` first. But a C programmer reaches for linked lists first. And it turns out that linked lists are a much better fit here. And so, I switched to linked lists[5]. (But using indices instead of pointers. Because of course. This is Rust. :-)) And now `ahocorasick_rs` uses less memory than `pyahocorasick`! [1]: https://old.reddit.com/r/rust/comments/199jycb/identifying_r... [2]: https://pypi.org/project/ahocorasick-rs/ [3]: https://pypi.org/project/pyahocorasick/ [4]: https://docs.rs/aho-corasick/latest/aho_corasick/struct.AhoC... [5]: https://github.com/BurntSushi/aho-corasick/commit/31bb1fc30d...

he core/alloc/std split). [1]: https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bf... [2]: https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bf... [3]: https://github.com/BurntSushi/aho-corasick/blob/f227162f7c56...

ng the regex.[4] Sadly, not all regex engines will be able to parse that regex due to its use of somewhat obscure Unicode properties. But the Rust regex crate can. :-) And of course, this somewhat shifts code size to heap size. So there's that too. But bottom line is, if you have a nice regex engine available to you, you can whip up a grapheme segmenter pretty quickly. And some regex engines even have grapheme segmentation built in via \X. [1]: https://github.com/BurntSushi/aho-corasick/issues/72 [2]: https://github.com/BurntSushi/bstr/blob/e38e7a7ca986f9499b30... [3]: https://github.com/BurntSushi/bstr/blob/e38e7a7ca986f9499b30... [4]: https://github.com/BurntSushi/bstr/blob/e38e7a7ca986f9499b30...