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.
I know that boost.intrusive's rb-tree implements that, and below I quoted its way to decide if the pointer is aligned in a way to use the lower bits of the pointer. 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 *)); boost.intrusive: template <typename T> struct alignment_of; template <typename T> struct alignment_of_hack { char c; T t; alignment_of_hack(); }; template <unsigned A, unsigned S> struct alignment_logic { static const std::size_t value = A < S ? A : S; }; template< typename T > struct alignment_of { static const std::size_t value = alignment_logic < sizeof(alignment_of_hack<T>) - sizeof(T) , sizeof(T) >::value; }; //Inherit from the detail::link_dispatch depending on the embedding capabilities template<class VoidPointer, bool OptimizeSize = false> struct rbtree_node_traits : public rbtree_node_traits_dispatch < VoidPointer , OptimizeSize && (max_pointer_plus_bits < VoidPointer , detail::alignment_of<compact_rbtree_node<VoidPointer> >::value >::value >= 1) > {};