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

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
> <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.
>>
>
>
>
Received on Wed Jun 04 2014 - 14:11:08 MDT