Boost logo

Boost :

Subject: [boost] Interest request for pointer+bit compression optimization
From: vicente.botet (vicente.botet_at_[hidden])
Date: 2009-09-07 13:00:14


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.

We can define two templates (See below)
template <typename E> struct bit_ref;
template <typename T> struct pointer_ref;

So instead of having

enum color_type{red=false,black=true};
class rb_node {
private:
    color_type color_;
    regular_rb_node_header* parent;

     color_type& color(){return color_;}?
     color_type color()const{return color_;}?
     rb_node*& parent(){return parent_;}?
     rb_node* parent() const{return parent_;}

}

we can compress the colot_type and the rb_node* as follows

class rb_node {
private:
    uintptr_type parentcolor_;
public:
   bit_ref<color_type> color(){return bit_ref<color_type>(&parentcolor_);}
   color_type color()const{return bit_ref<color_type>(&parentcolor_);}
   pointer_ref<rb_node> parent(){return pointer_ref<rb_node>(&parentcolor_);}
   rb_node* parent() const {return pointer_ref<rb_node>(&parentcolor_);}
};

Next follows the definition of the template classes
  template <typename E>
  struct bit_ref {
    bit_ref(uintptr_type* r_):r(r_){}
    operator E() const {
      return E(*r&uintptr_type(1));
    }
    bit_ref& operator=(E c) {
      *r&=~uintptr_type(1);
      *r|=uintptr_type(c);
      return *this;
    }
    bit_ref& operator=(const bit_ref& x) {
      return operator=(x.operator T());
    }
  private:
    uintptr_type* r;
  };
  
  template <typename T>
  struct pointer_ref {
    pointer_ref(uintptr_type* r_):r(r_){}
    operator T*() const {
      return (T*)(void*)(*r&~uintptr_type(1));
    }
    pointer_ref& operator=(T* p) {
      *r=((uintptr_type)(void*)p)|(*r&uintptr_type(1));
      return *this;
    }
    pointer_ref& operator=(const pointer_ref& x) {
      return operator=(x.operator T*());
    }
    pointer_ref operator->()const {
      return operator T*();
    }
  private:
    uintptr_type* r;
  };

Thanks Joaquin for sharing simple things like this one, stable_vector and others in your Bannalia blog.
_____________________
Vicente Juan Botet Escribá


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