Re: [boost] Interest request for pointer+bit compression optimization

Subject: Re: [boost] Interest request for pointer+bit compression optimization
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2009-09-08 05:04:37

vicente.botet escribió:
> Hi,
> 
> I have recently found in the blog of Joaquin the following
> optimization consisting in embed a bit into the representation of a
> pointer. Please read it, it is not too long
> (http://bannalia.blogspot.com/2008/11/optimizing-red-black-tree-color-bits.html)
> 
> 
> I was wondering if it would be interesting to provide some generic
> template classes making easier this kind of optimization.

Take a look at 
http://www.boost.org/boost/boost/intrusive/pointer_plus_bits.hpp for 
some helper classes used in Intrusive that might be useful:

The method is being used to embed also N bits in offset_ptr and other 
smart pointers, see:

http://www.boost.org/boost/intrusive/pointer_plus_bits.hpp
http://www.boost.org/boost/interprocess/offset_ptr.hpp

then the container select the correct node depending on the alignment of 
the generic pointer type:

//Inherit from the detail::link_dispatch depending on the embedding 
capabilities
template<class VoidPointer, bool OptimizeSize = false>
struct rbtree_node_traits
    :  public rbtree_node_traits_dispatch
          < VoidPointer
          ,  OptimizeSize &&
            (max_pointer_plus_bits
             < VoidPointer
             , detail::alignment_of<compact_rbtree_node<VoidPointer> 
 >::value
             >::value >= 1)
          >
{};

the same happens with AVL trees but in this case we need 2 bits.

Best,

Ion