Re: [boost] [ boost ] [ Trie ]

Subject: Re: [boost] [ boost ] [ Trie ]
From: Antony Polukhin (antoshkka_at_[hidden])
Date: 2015-03-14 04:18:10

2015-03-13 23:13 GMT+03:00 Cosmin Boaca <boost.cosmin.boaca_at_[hidden]>:

> 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].
>

+1

> 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.
>

OK. Not a problem, we're not in a rush.

By the way, think of making `parent` a private variable and adding
(get|set)_parent() functions. We can later try to make node even smaller by
removing `parent` variable and getting parent node by calling
intrusive::set::container_from_iterator(iterator);

> 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.
>

Good idea, but this must be done some time later. Currently there are more
essential optimizations for nodes.

> 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.

I'm thinking of a slightly different approach: we can make a specific
"leaf" node, that contains the remaining part of the value. For example, if
we have two values in trie "hello word" and "hell's bells", then the trie
would look like:

node['h']->node['e']->node['l']->node['l']->(leaf["o world"] | leaf['''s
bells']);

But this must be done only after the existing code would be polished enough.

One of the reasons for underperforming is a big size of the node. Node does
not fit in cache line. I hope that removing pred_node/next_node will help a
lot.

-- 
Best regards,
Antony Polukhin