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

On Tue, Jun 3, 2014 at 5:52 PM, Amos Jeffries <squid3_at_treenet.co.nz> wrote:
> 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.

er.. Trie doesn't support delete. Only add, find and findPrefix.

> So the worst-case areas are worse thay they would be for example in ACLs
> based on Trie.

Note I'm not suggesting to blindly replace TrieNode with this.
Assuming we don't go for something more complete (e.g. the ternary
search trie I'm tinkering with), and stick to this very simple API,
then the easiest thing to do is to make Trie a generic, taking as
argument the template to be used. So there'd be a FastTrie (aka
Trie<ArrayTrieNode>) and a CompactTrie (aka Trie<MapTrieNode>).

-- 
    Kinkie