On empty member optimization on comparator in stl_tree...

["Sylvain Bougerel" <sylvain dot bougerel dot devel at gmail dot com>]

Hi,

I have 2 version of the STL installed on my machine. A not so recent
one (that came up with GCC4.2.3) and the latest one.

I was interested in a snippet of code within bits/stl_tree.h. This
snippet of code defines the "implementation" object for the red-black
tree used in (multi)set and (multi)map.

Here it is, in the older version (there are 2 struct, one being a
specialization... but with strictly the same code as the other...
???):

      template<typename _Key_compare,
	       bool _Is_pod_comparator = std::__is_pod<_Key_compare>::__value>
        struct _Rb_tree_impl : public _Node_allocator
        {
	  _Key_compare		_M_key_compare;
	  _Rb_tree_node_base 	_M_header;
	  size_type 		_M_node_count; // Keeps track of size of tree.

	  _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
			const _Key_compare& __comp = _Key_compare())
	  : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
	    _M_node_count(0)
	  {
	    this->_M_header._M_color = _S_red;
	    this->_M_header._M_parent = 0;
	    this->_M_header._M_left = &this->_M_header;
	    this->_M_header._M_right = &this->_M_header;
	  }
	};

      // Specialization for _Comparison types that are not capable of
      // being base classes / super classes.
      template<typename _Key_compare>
        struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator
	{
	  _Key_compare 		_M_key_compare;
	  _Rb_tree_node_base 	_M_header;
	  size_type 		_M_node_count; // Keeps track of size of tree.

	  _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
			const _Key_compare& __comp = _Key_compare())
	  : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
	    _M_node_count(0)
	  {
	    this->_M_header._M_color = _S_red;
	    this->_M_header._M_parent = 0;
	    this->_M_header._M_left = &this->_M_header;
	    this->_M_header._M_right = &this->_M_header;
	  }
	};

       _Rb_tree_impl<_Compare> _M_impl;


And below in the newest version (here the specialization has been
removed, so left with only the general case):

       template<typename _Key_compare,
            bool _Is_pod_comparator = __is_pod(_Key_compare)>
         struct _Rb_tree_impl : public _Node_allocator
         {
       _Key_compare      _M_key_compare;
       _Rb_tree_node_base    _M_header;
       size_type         _M_node_count; // Keeps track of size of tree.

       _Rb_tree_impl()
       : _Node_allocator(), _M_key_compare(), _M_header(),
         _M_node_count(0)
       { _M_initialize(); }

       _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
       : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
         _M_node_count(0)
       { _M_initialize(); }

     private:
       void
       _M_initialize()
       {
         this->_M_header._M_color = _S_red;
         this->_M_header._M_parent = 0;
         this->_M_header._M_left = &this->_M_header;
         this->_M_header._M_right = &this->_M_header;
       }
     };

       _Rb_tree_impl<_Compare> _M_impl;


As far as I know, the purpose of defining _Rb_tree_impl is to do an
empty member optimization of the base type _Node_allocator, that is
often empty, and would otherwise occupy 4 unnecessary bytes.

What I fail to see, is why isn't the same technique applied to the
_M_key_compare member. As far as I know, most of the comparator like
template<class T>std::less<T> have no members? So, why not write
something like that...

       template<typename _Key_compare,
            bool _Is_pod_comparator = __is_pod(_Key_compare)>
         struct _Rb_tree_impl : public _Node_allocator, public_Key_compare
         {
       _Rb_tree_node_base    _M_header;
       size_type         _M_node_count; // Keeps track of size of tree.

       _Rb_tree_impl()
       : _Node_allocator(), _M_key_compare(), _M_header(),
         _M_node_count(0)
       { _M_initialize(); }

       _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
       : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
         _M_node_count(0)
       { _M_initialize(); }
       };

And then redefine:

      _Compare
      key_comp() const
      { return _M_impl._M_key_compare; }

into:

      _Compare
      key_comp() const
      { return static_cast<_Compare>(_M_impl); }

Wouldn't that also save 4 bytes of memory for the _Rb_tree_impl,
wouldn't the static_cast<_Compare> get optimized away in most cases?
What are the reasons why it's not actually possible?


Besides in both version, the _Rb_tree_impl is a template defined by:
       template<typename _Key_compare,
            bool _Is_pod_comparator = __is_pod(_Key_compare)>
         struct _Rb_tree_impl : public _Node_allocator, protected _Key_compare

But later, it is only used as an instantiation of:

_Rb_tree_impl<_Compare> _M_impl;

So what is the reason why it's defined as a template in the first place?


Sorry for all these questions, I'm just looking for answers in order
to have a better understanding of the library and in order to get
better at coding C++.


Regards,

Sylvain