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
> (
> I was wondering if it would be interesting to provide some generic
> template classes making easier this kind of optimization.

Take a look at 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:

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
template<class VoidPointer, bool OptimizeSize = false>
struct rbtree_node_traits
    : public rbtree_node_traits_dispatch
          < VoidPointer
          , OptimizeSize &&
             < VoidPointer
             , detail::alignment_of<compact_rbtree_node<VoidPointer>
>::value >= 1)

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


Unsubscribe & other changes:

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
      ,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 &&
             < 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?


Boost list run by bdawes at, gregod at, cpdaniel at, john at