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

7 Sep 2009

      ----- Original Message ----- 
From: "vicente.botet" <vicente.botet@wanadoo.fr>
To: <boost@lists.boost.org>
Sent: Monday, September 07, 2009 10:32 PM
Subject: Re: [boost] Interest request for pointer+bit compressionoptimization
...
Hi Stephan,
----- Original Message ----- 
From: "Stefan Strasser" <strasser@uni-bremen.de>
To: <boost@lists.boost.org>
Sent: Monday, September 07, 2009 10:32 PM
Subject: Re: [boost] Interest request for pointer+bit compressionoptimization
...
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.
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 *));
Yes, this could be a valid alternative. I would try to implement it.
I have not compiled the code but here it is a first trial:

// Selects between a compressed and a regular class depending on whether 
// * the use wants the compression, 
// *the compilers has a unsigned integer type with the size of the a pointer and 
// *the alignement of the structure let an unsued  bit

template <typename Compressed, typename Regular, bool Compression=true>
struct best_of {
  typedef  boost::mpl::if_c<
    Compression&&
    has_uintptr_type::value&&
    (boost::alignment_of<Compressed>::value%2==0),
    Compressed,
    Regular
...
::type type;
};
// compressed version
template <typename Bit, typename Pointee>
class compressed_bit_pointer {
   uintptr_type ui_;    
public:
 regular _bit_pointer (): ui_(0);
 regular _bit_pointer (Bit b, Pointee* p);
  pointer_ref<Pointee> pointer()       {return pointer_ref(ui_);}
  Pointee*                      pointer() const {return pointer_ref(ui_);}
  bit_ref<Bit>                bit()           {return bit_ref(ui_);}
  Bit                               bit() const     {return bit_ref(ui_);}
};

// regular version
template <typename Bit, typename Pointee>
class regular_bit_pointer {
    Bit bit_;    
    Pointee pointer_;    
public:
 regular _bit_pointer ():pointer_(0),bit_(0);
 regular _bit_pointer (Bit b, Pointee* p);
  pointer_ref<Pointee>  pointer()       {return pointer_;}
  Pointee*                      pointer() const {return pointer_;}
  bit_ref<Bit>                 bit()           {return bit_;}
  Bit                               bit() const     {return bit_;}
};

// selects the best of the compressed or the regular version
template <typename Pointee, typename Bit, bool Compression=true>
struct optimized_pair : typename best_of<compressed_bit_pointer<Bit, Pointee>, 
                                                    regular_bit_pointer<Bit, Pointee>, 
                                    Compression>::type {};

The use is a little bit more simple, no need to declare two classes compressed and regular

  optimized_pair<color_type, rb_node> color_parent_;

  pointer_ref<rb_node>  color() {return color_parent_.pointer();}
  rb_node*   parent() const {return color_parent_.pointer();}
  color_type color()const{return color_parent_.bit();}
  bit_ref<color_type> color(){return color_parent_.bit();}

I think that I will put altogther in a package. Any sugestion on where this utility could be placed? A new library? Do you have suggestion to improve the namming and a namespace?

Best,
Vicente