Kaznov
Kaznov

Reputation: 1163

Is there a reason for 8 bytes of size overhead in libstdc++ std::(multi)set/map?

Lately I've been analyzing red-black tree implementations in different standard library implementations. What struck me as odd, is that libstdc++ seems to have unnecessary size overhead.

Simplifying a little, the classes are composed like that:

// std::set
template </*...*/>
class set {
    _Rb_tree</*...*/> _M_t;
};

// stl_tree.h:434
template </*...*/>
class _Rb_tree {
    // stl_tree.h:670
    template </*...*/>
    struct _Rb_tree_impl
        : public _Node_allocator
        , public _Rb_tree_key_compare<_Key_compare>
        , public _Rb_tree_header {};

    _Rb_tree_impl</*...*/> _M_impl;
};

Header has 40 bytes: 1 size_type of the container, and 32 bytes for stack-allocated sentinel node.

Now, what really was a surprise for me, is how _Rb_tree_key_compare is defined:

  // stl_tree.h:140
  // Helper type offering value initialization guarantee on the compare functor.
  template <typename _Key_compare>
    struct _Rb_tree_key_compare
    {
      _Key_compare      _M_key_compare;

      _Rb_tree_key_compare()
      _GLIBCXX_NOEXCEPT_IF(
    is_nothrow_default_constructible<_Key_compare>::value)
      : _M_key_compare()
      { }

      _Rb_tree_key_compare(const _Key_compare& __comp)
      : _M_key_compare(__comp)
      { }

#if __cplusplus >= 201103L
      // Copy constructor added for consistency with C++98 mode.
      _Rb_tree_key_compare(const _Rb_tree_key_compare&) = default;

      _Rb_tree_key_compare(_Rb_tree_key_compare&& __x)
    noexcept(is_nothrow_copy_constructible<_Key_compare>::value)
      : _M_key_compare(__x._M_key_compare)
      { }
#endif
    };

With it defined like that, _Rb_tree_impl cannot use empty base optimization, and due to alignment requirements it means that this class with no non-empty members (for stateless comparators) takes up 8 bytes of space (on x64 builds).

Why wasn't it defined like that?

template <typename _Key_compare>
struct _Rb_tree_key_compare : _Key_compare
{
  _Rb_tree_key_compare()
    : _Key_compare()
  { }

  _Rb_tree_key_compare(const _Key_compare& __comp)
    : _Key_compare(__comp)
  { }

  /* ... */
};

(I removed macros and noexcept specifiers for clarity)

According to standard (if I understand it correctly), the rules for initializing base classes are roughly the same as for initializing members, so as a base class it will be value-initialized as well.

Is there some reason I'm missing, that forced the use of composition instead of inheritance here? It seems like simply wasted 8 bytes in standard container, and it's not something I would suspect. (I know it can't be fixed either due to ABI break).

Upvotes: 4

Views: 201

Answers (0)

Related Questions