Re: [boost] [ boost ] [ Trie ]

Subject: Re: [boost] [ boost ] [ Trie ]
From: Antony Polukhin (antoshkka_at_[hidden])
Date: 2015-03-08 08:47:38

2015-03-08 12:45 GMT+03:00 Cosmin Boaca <boost.cosmin.boaca_at_[hidden]>:

> On 8 March 2015 at 11:27, Antony Polukhin <antoshkka_at_[hidden]> wrote:
> 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 ?
>

All the allocators must return storage that is aligned appropriately for
objects of type value_type. We construct trie_nodes on storage returned
from allocator. In other words we can count on that trie_nodes are aligned.

trie_node::node_ptrs point to trie_node. trie_node contains many pointers,
so probably the structure will have the pointer alignment or bigger (this
can be statically asserted). According to the alignment definition, 2 bytes
aligned addresses have modulo 2 equal to 0 (in other words they are
represented by even numbers/addresses). It means that the the least
significant bit is zero.

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

Good. That's the most important one!

-- 
Best regards,
Antony Polukhin