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

Hi,
  to align the others on what we discussed about on IRC (feel free to
correct me if I'm remembering inappropriately): 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. 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
<rousskov_at_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.
>

-- 
    Francesco