Re: [boost] [ boost ] [ Trie ]

2015-03-08 12:45 GMT+03:00 Cosmin Boaca :

...

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

On 8 March 2015 at 11:27, Antony Polukhin wrote: Many optimizations may be applied there: 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