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

Subject: Re: [boost] Interest request for pointer+bit compression optimization
From: Stefan Strasser (strasser_at_[hidden])
Date: 2009-09-07 16:32:32

Am Monday 07 September 2009 19:00:14 schrieb vicente.botet:
> 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.

I know that boost.intrusive's rb-tree implements that, and below I quoted its 
way to decide if the pointer is aligned in a way to use the lower bits of the 
pointer.
if you wanted to implement that as a generic template I guess the best way is 
to hide it behind a class that models the concept of a std::pair, or a 
boost::tuple.

e.g.
optimized_pair<void *,bool> p(0,false);
assert(sizeof(p) == sizeof(void *));

boost.intrusive:

template <typename T> struct alignment_of;

template <typename T>
struct alignment_of_hack
{
    char c;
    T t;
    alignment_of_hack();
};

template <unsigned A, unsigned S>
struct alignment_logic
{
   static const std::size_t value = A < S ? A : S;
};

template< typename T >
struct alignment_of
{
   static const std::size_t value = alignment_logic
            < sizeof(alignment_of_hack<T>) - sizeof(T)
            , sizeof(T)
            >::value;
};

//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)
         >
{};