Boost logo

Boost :

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


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