On 06/04/2014 02:06 AM, Kinkie wrote: > there are use cases > for using a Trie (e.g. prefix matching for dstdomain ACL); these may > be served by other data strcutures, but none we could come up with on > the spot.
std::map and StringIdentifier are the ones we came up with on the spot. Both may require some adjustments to address the use case you are after. Alex. > A standard trie uses quite a lot of RAM for those use cases. > There are quite a lot of areas where we can improve so this one is not > urgent. Still I'd like to explore it as it's synchronous code (thus > easier for me to follow) and it's a nice area to tinker with. > > On Tue, Jun 3, 2014 at 10:12 PM, Alex Rousskov > <rouss...@measurement-factory.com> wrote: >> On 06/03/2014 08:40 AM, Kinkie wrote: >>> Hi all, >>> as an experiment and to encourage some discussion I prepared an >>> alternate implementation of TrieNode which uses a std::map instead of >>> an array to store a node's children. >>> >>> The expected result is a worst case performance degradation on insert >>> and delete from O(N) to O(N log R) where N is the length of the >>> c-string being looked up, and R is the size of the alphabet (as R = >>> 256, we're talking about 8x worse). >>> >>> The expected benefit is a noticeable reduction in terms of memory use, >>> especially for sparse key-spaces; it'd be useful e.g. in some lookup >>> cases. >>> >>> Comments? >> >> >> To evaluate these optimizations, we need to know the targeted use cases. >> Amos mentioned ESI as the primary Trie user. I am not familiar with ESI >> specifics (and would be surprised to learn you want to optimize ESI!), >> but would recommend investigating a different approach if your goal is >> to optimize search/identification of strings from a known-in-advance set. >> >> >> Cheers, >> >> Alex. >> > > >
