Re: [boost] Interest request for pointer+bit compressionoptimization

Subject: Re: [boost] Interest request for pointer+bit compressionoptimization
From: vicente.botet (vicente.botet_at_[hidden])
Date: 2009-09-08 15:25:54

Hi Ion,
----- Original Message ----- 
From: "Ion Gaztañaga" <igaztanaga_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Tuesday, September 08, 2009 11:04 AM
Subject: Re: [boost] Interest request for pointer+bit compressionoptimization

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
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Thanks Ion, I was unaware this trick was included from the begining on Boost.Intrusive.

With the optimized_pair class (or a variant taking care of the number of bits), instead of defining compressed and compact classes rbtree_node and rbtree_node_traits you could just do the following

template<class VoidPointer, bool OptimizeSize = false>
struct rbtree_node
{
   typedef typename pointer_to_other
      <VoidPointer
      ,compact_rbtree_node<VoidPointer> >::type node_ptr;
   enum color { red_t, black_t };
   node_ptr left_, right_;
   optimized_pair<node_ptr, color, 1, OptimizeSize> parent_plus_color_; // (1)
};

template<class VoidPointer, bool OptimizeSize = false>
struct rbtree_node_traits 
{
   typedef rbtree_node<VoidPointer, OptimizeSize> node;

   typedef typename boost::pointer_to_other
      <VoidPointer, node>::type          node_ptr;
   typedef typename boost::pointer_to_other
      <VoidPointer, const node>::type    const_node_ptr;

   typedef typename node::color color;

   static node_ptr get_parent(const_node_ptr n)
   {  return n->parent_plus_color_.get_pointer();  } // (2)

   static void set_parent(node_ptr n, node_ptr p)
   {  n->parent_plus_color_.set_pointer(p);  }  // (2)

   static node_ptr get_left(const_node_ptr n)
   {  return n->left_;  }

   static void set_left(node_ptr n, node_ptr l)
   {  n->left_ = l;  }

   static node_ptr get_right(const_node_ptr n)
   {  return n->right_;  }

   static void set_right(node_ptr n, node_ptr r)
   {  n->right_ = r;  }

   static color get_color(const_node_ptr n)
   {  return n->parent_plus_color_.get_bits();  }  // (2)

   static void set_color(node_ptr n, color c)
   {  n->parent_plus_color_.set_bits(c);  }  // (2)

   static color black()
   {  return node::black_t;  }

   static color red()
   {  return node::red_t;  }
};

The main advantages are 
A. Avoids duplication of common parts between the regular and the compressed implementations.
B. the user of the optimized_pair would not care on the condition
            OptimizeSize &&
            (max_pointer_plus_bits
             < VoidPointer
             , detail::alignment_of<compact_rbtree_node<VoidPointer>
C. The single differences with a regular class are minimal (1) the declaration and (2) the getters and setters.

I think that we can rename optimized_pair by pointer_plus_bits which i more specific.

Do you think that it is worth include this class in Boost?

Best,
Vicente