On 4/06/2014 2:40 a.m., 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? >
Since this is in libTrie used for ESI message body parsing the major operations being done on it are insert and delete. These happen a relatively large number of times per-request as the XML payload/body gets parsed and a whole tree is constructed+destructed. So the worst-case areas are worse thay they would be for example in ACLs based on Trie. Amos
