Boost logo

Boost :

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
  


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