Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk