Re: [boost] [ boost ] [ Trie ]

Subject: Re: [boost] [ boost ] [ Trie ]
From: Cosmin Boaca (boost.cosmin.boaca_at_[hidden])
Date: 2015-03-08 05:45:21

On 8 March 2015 at 11:27, Antony Polukhin <antoshkka_at_[hidden]> wrote:

> 2015-03-07 20:10 GMT+03:00 Cosmin Boaca <boost.cosmin.boaca_at_[hidden]>:
>
Yep, methods create_node/destroy_node are required

I am thinking at creating a new class something like node_factory that
would handle this. I think it's more like the OOP way.

> That's a bad idea: iterators must know nothing about erasure. Convert those
> __erase_self_value_node() methods into a free functions in detail
> namespace. Those functions will be accepting allocator and will be
> overloaded by node pointers.
>

Ok. I will change this one.

Many optimizations may be applied there:
> * key_ends_here is a boolean value, that actually could be hidden in one of
> the pointers. In all cases our nodes are at least 2 bytes aligned, so all
> the parent, pred_node, next_node guaranteed to have first bit set to 0.
> so we can hide that `key_ends_here` bit in pointer just like this: pointer
> | (key_ends_here ? 1u : 0u). This will probably require addition of
> set_parent(). parent(), <...> functions to all the trie_nodes.
>

Can you give me some further explanations about this ? Why are the nodes at
least 2 bytes aligned and why does this imply that the first bit of the
pointers is set to 0 ? When you're saying the first bit you mean the least
significant one (index 0) don't you ?

> * children_type is not good. We get problems (like having additional
> child_iter_of_parent in node), because the key is not stored in node. So
> the plan is following: make trie_node to be usable in intrusive set, and
> use the nodes directly in children. Here are some steps: use
> boost::intrusive::set for children_type, derive trie_node from
> set_base_hook
> and make it intrusive-set compatible, remove child_iter_of_parent and store
> key in trie_node directly. This will significally reduce memory usage by
> nodes and memory allocations (unlike intrusive set, std::map allocates
> memory for nodes).
>

I think I will start with this. The idea of intrusive containers seems
pretty interesting to me. I have never heard of something like this until
now.

Thank you,
Cosmin