Re: [code] [for discussion] map-trie

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
Received on Tue Jun 03 2014 - 15:52:33 MDT