Re: [boost] [ boost ] [ Trie ]

Subject: Re: [boost] [ boost ] [ Trie ]
From: Cosmin Boaca (boost.cosmin.boaca_at_[hidden])
Date: 2015-03-13 16:13:14

Hello,

I have added a new specialization for trie_node. Now trie_node is
specialized for single value node (like trie_map), no value node (trie_set)
and multiple value node (trie multimap).
Please give me some feedback about it [0].
The removal of pred_node / next_node it's a bit more complicated than I've
thought initially and I think it will slow down the iteration process a bit.

I have thought a little about the container used for children. I think that
a container with less insertion / find overhead would be better. I think
that maintaining a sorted intrusive list / vector of pointers would perform
better if the number of children for a node is small (something like < 50 ,
maybe < 100). We may tune this further on anyway, maybe using some kind of
policy for the container.

In the current implementation we have no memory locality of the nodes. I
think this may be a reason of underperforming for intrusive set. I was
thinking at preallocating the whole node path in the trie during insertion.
For instance if the key is something "abcde" 5 nodes may be allocated in
advance. This approach however has the downside that the hole path must be
deallocated in advance, so even the nodes are erased from they can't be
deallocated. Also, this implies to keep track of the allocated chains in an
additional data structure and deallocating all of the data in the
destructor. This was the only way to improve memory locality that I
could've thought but personally I think that this is not a good idea.

[0]
https://github.com/cosminBoaca/boost.trie/commit/61ba81b033d3a582c9f290955b90ea5c7a04de7d

Thank you,
Cosmin