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-07 18:40:31

----- Original Message ----- 
From: "vicente.botet" <vicente.botet_at_[hidden]>
To: <boost_at_[hidden]>
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_at_[hidden]>
> To: <boost_at_[hidden]>
> 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