Hi Ion, ----- Original Message ----- From: "Ion Gaztañaga" <igaztanaga@gmail.com> To: <boost@lists.boost.org> Sent: Tuesday, September 08, 2009 11:04 AM Subject: Re: [boost] Interest request for pointer+bit compressionoptimization vicente.botet escribió:
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.ht...)
I was wondering if it would be interesting to provide some generic template classes making easier this kind of optimization.
Take a look at http://www.boost.org/boost/boost/intrusive/pointer_plus_bits.hpp for some helper classes used in Intrusive that might be useful: The method is being used to embed also N bits in offset_ptr and other smart pointers, see: http://www.boost.org/boost/intrusive/pointer_plus_bits.hpp http://www.boost.org/boost/interprocess/offset_ptr.hpp then the container select the correct node depending on the alignment of the generic pointer type: //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) > {};
the same happens with AVL trees but in this case we need 2 bits. Best, Ion _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost Thanks Ion, I was unaware this trick was included from the begining on Boost.Intrusive. With the optimized_pair class (or a variant taking care of the number of bits), instead of defining compressed and compact classes rbtree_node and rbtree_node_traits you could just do the following template<class VoidPointer, bool OptimizeSize = false> struct rbtree_node { typedef typename pointer_to_other <VoidPointer ,compact_rbtree_node<VoidPointer> >::type node_ptr; enum color { red_t, black_t }; node_ptr left_, right_; optimized_pair<node_ptr, color, 1, OptimizeSize> parent_plus_color_; // (1) }; template<class VoidPointer, bool OptimizeSize = false> struct rbtree_node_traits { typedef rbtree_node<VoidPointer, OptimizeSize> node; typedef typename boost::pointer_to_other <VoidPointer, node>::type node_ptr; typedef typename boost::pointer_to_other <VoidPointer, const node>::type const_node_ptr; typedef typename node::color color; static node_ptr get_parent(const_node_ptr n) { return n->parent_plus_color_.get_pointer(); } // (2) static void set_parent(node_ptr n, node_ptr p) { n->parent_plus_color_.set_pointer(p); } // (2) static node_ptr get_left(const_node_ptr n) { return n->left_; } static void set_left(node_ptr n, node_ptr l) { n->left_ = l; } static node_ptr get_right(const_node_ptr n) { return n->right_; } static void set_right(node_ptr n, node_ptr r) { n->right_ = r; } static color get_color(const_node_ptr n) { return n->parent_plus_color_.get_bits(); } // (2) static void set_color(node_ptr n, color c) { n->parent_plus_color_.set_bits(c); } // (2) static color black() { return node::black_t; } static color red() { return node::red_t; } }; The main advantages are A. Avoids duplication of common parts between the regular and the compressed implementations. B. the user of the optimized_pair would not care on the condition OptimizeSize && (max_pointer_plus_bits < VoidPointer , detail::alignment_of<compact_rbtree_node<VoidPointer> C. The single differences with a regular class are minimal (1) the declaration and (2) the getters and setters. I think that we can rename optimized_pair by pointer_plus_bits which i more specific. Do you think that it is worth include this class in Boost? Best, Vicente