[libc++] Remove vector base class

[philnik]

Summary

Remove the vector base class as suggested by @ldionne

[ldionne]

Given that we end up with a lot of conditionals when removing this, I don't think this is worth doing. We don't gain anything performance wise, and we actually lose something clarity wise because this makes the code more complicated. If we had been able to move the members out of __vector_base without breaking the ABI, I think this would have been compelling, but now I'm not sure. WDYT?

libcxx/include/vector

311

vector.cpp should not export the functions if _LIBCPP_ABI_NO_VECTOR_BASE_CLASS is not defined.

316

I was trying to convince myself that it wouldn't be ABI breaking to do the following:

template <bool> struct __vector_base_common { ... };
template <class, class> struct __vector_base : private __vector_base_common<true> { /* nothing here */ };

template <class _Tp, class _Allocator>
class vector
#if !defined(_LIBCPP_ABI_NO_VECTOR_BASE_CLASS)
  : private __vector_base<_Tp, _Allocator>
#endif
{
  pointer                                                      __begin_;
  pointer                                                      __end_;
  __compressed_pair<pointer, allocator_type>                   __end_cap_;

  // use members normally here, unconditionally
};

However, the usual pitfall of multiply inheritting from vector<T> applies here too. Let's assume we have:

struct IntVector1 : std::vector<int> { };
struct IntVector2 : std::vector<int> { };
struct Foo : IntVector1, IntVector2 { };

Before the change, the layout should be:

+---------------------------------+
| __vector_base_common<true>      | 0 bytes, EBO'd
| __vector_base<int>::__begin_    | 8 bytes
| __vector_base<int>::__end_      | 8 bytes
| __vector_base<int>::__end_cap_  | 8 bytes (disregarding allocator)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| __vector_base_common<true>      | 1 byte, can't EBO
| __vector_base<int>::__begin_    | 8 bytes
| __vector_base<int>::__end_      | 8 bytes
| __vector_base<int>::__end_cap_  | 8 bytes (disregarding allocator)
+---------------------------------+

After the change, the layout should be:

+---------------------------------+
| __vector_base_common<true>      | 0 bytes, EBO'd
| __vector_base<int>              | 0 bytes, EBO'd
| vector<int>::__begin_           | 8 bytes
| vector<int>::__end_             | 8 bytes
| vector<int>::__end_cap_         | 8 bytes (disregarding allocator)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| __vector_base_common<true>      | 1 byte, can't EBO
| __vector_base<int>              | 1 byte, can't EBO <<-- this is the ABI break
| vector<int>::__begin_           | 8 bytes
| vector<int>::__end_             | 8 bytes
| vector<int>::__end_cap_         | 8 bytes (disregarding allocator)
+---------------------------------+

Since __vector_base<int> would now be empty, it would get EBO'd the first time it's a base class, but not the second time, so there would be one extra byte because of that "spurious" base class.

Long story short, my suggestion doesn't work because it would break multiple inheritance of std::vector.

[philnik]

• Address comments

libcxx/include/vector

316

https://godbolt.org/z/rdMfbchKq seems to suggest that something with your tables is wrong. My current diff has still the same size with your example.

[ldionne]

libcxx/include/vector

316

Of course!!!! Thanks for challenging this, my tables were wrong indeed. See for example https://godbolt.org/z/Wdz1Kasxn.

What I did wrong is that I blindly did as if the EBO would stop kicking in for a duplicate base class. In reality, EBO doesn't kick in if it would cause the two base classes (or base class and first member) to have the same address. Basically, EBO always kicks in except if it would cause two objects to have the same address.

This is an issue with e.g. std::reverse_iterator (as explained in https://quuxplusone.github.io/blog/2021/05/07/std-iterator-as-a-base-class/) because std::reverse_iterator inherits from std::iterator (which is empty and hence EBO'd), and then its first member is also something that might inherit from std::iterator (making the two std::iterator subobjects overlap if EBO is used).

However, since std::vector is never an empty class, the address of __vector_base_common is never going to overlap, because there's always a couple of pointers between one __vector_base and the next. So EBO can always be used.

Hence, I don't think this is an ABI break at all, and in fact I now believe we can even remove the base class altogether, without any check. In that case, I would move

template <bool>
struct __vector_base_common;

template <>
struct __vector_base_common<true> {
    // Both are defined in vector.cpp
    _LIBCPP_NORETURN _LIBCPP_EXPORTED_FROM_ABI void __throw_length_error() const;
    _LIBCPP_NORETURN _LIBCPP_EXPORTED_FROM_ABI void __throw_out_of_range() const;
};

To the .cpp file and wouldn't define it in the headers at all. Then, we can rename _LIBCPP_ABI_NO_VECTOR_BASE_CLASS to _LIBCPP_ABI_NO_VECTOR_BASE_COMMON and have it control only whether the library provides those symbols.

I'd like to have the logic above counter checked, @Quuxplusone maybe?

Also, the same logic should apply to std::basic_string.

[• Quuxplusone]

libcxx/include/vector

316

That sounds right to me.
So the new <vector> header would unconditionally not call into the dylib to throw exceptions; but we'd keep the exception-throwing functions present in the dylib (under !defined(_LIBCPP_ABI_NO_VECTOR_BASE_COMMON)) for the benefit of old .o files that were compiled against the previous release's <vector> header.

Also, the same logic should apply to std::basic_string.

So I'd say the name of the ABI macro should be more general, and control both base class types together? Right now we have _LIBCPP_ABI_NO_BASIC_STRING_BASE_CLASS and _LIBCPP_ABI_NO_VECTOR_BASE_CLASS. We could make it _LIBCPP_ABI_NO_COMMON_CONTAINER_BASE_EXPORTS or something like that.

[philnik]

• Remove all of vector base

libcxx/include/vector

316

I would keep them seperate. There is no technical reason, but I think _LIBCPP_ABI_NO_COMMON_CONTAINER_BASE_EXPORTS sounds too much like 'there are no more common base classes in containers'. That might be true, but I didn't check and don't want to guarantee it. There might be an actual use case somewhere, and having two macros doesn't really hurt anything.

[philnik]

• Rebased
• Fix CI

[• Quuxplusone]

LGTM but possibly significant comment.

libcxx/include/vector

704–707

I'd feel slightly better if this unrelated NSDMI-ification were done in a separate commit; but if CI is happy then I'm happy.

libcxx/src/vector.cpp

18–26 ↗

(On Diff #405008)

These member functions are now implicitly inline, because they appear in the body of a class. FWLIW I'd feel vastly safer if they appeared outside the body of the class, so that they would not be inline.
I'm guessing that _LIBCPP_EXPORTED_FROM_ABI is some kind of magic "anti-inline" keyword that will cause them to be generated anyway, on relevant platforms? @ldionne you think this is OK (and better than defining them out-of-line)?

[ldionne]

libcxx/include/vector

316

Thanks for counter checking the logic, @Quuxplusone. I am neutral on renaming the macros, but I suggest we keep them separate at this point because it doesn't really hurt, the patches are written, and I'd like to ship + cherry-pick them.

704–707

I don't mind doing it in this patch, however I do wonder why we're using __compressed_pair<pointer, allocator_type>(nullptr, allocator_type()) instead of doing

__compressed_pair<pointer, allocator_type> __end_cap_(nullptr, __default_init_tag());

which is what we used to do in the default constructor of the base class. @philnik any reason?

libcxx/src/vector.cpp

18–26 ↗

(On Diff #405008)

_LIBCPP_EXPORTED_FROM_ABI doesn't do anything special with respect to the inline-ness of the function. So indeed, they are not getting generated and that's why the CI is failing. I suggest we be consistent with D118733 and instead do:

template <bool>
struct __vector_base_common {
  _LIBCPP_NORETURN _LIBCPP_EXPORTED_FROM_ABI void __throw_length_error() const;
  _LIBCPP_NORETURN _LIBCPP_EXPORTED_FROM_ABI void __throw_out_of_range() const;
};

template <>
void __vector_base_common<true>::__throw_length_error() const {
  _VSTD::__throw_length_error("vector");
}

template <>
void __vector_base_common<true>::__throw_out_of_range() const {
  _VSTD::__throw_out_of_range("vector");
}

[philnik]

• Rebased
• Address comments
• Rename macro to be consistent with basic_string

[ldionne]

Thanks a lot, this LGTM.

libcxx/include/vector

1105

I think it's weird that we're default initializing the allocator instead of value initializing it here, but it's definitely consistent with what we did before this patch.

Actually, this leads me to believe that we don't implement the C++20 vector properly. Indeed, in C++20, this constructor is specified as:

constexpr explicit vector(size_type n, const Allocator& = Allocator());

Unless mistake, this means that we should be value-initializing the allocator here to be equivalent to the default argument. This seems to have changed in C++14 (https://en.cppreference.com/w/cpp/container/vector/vector). @Quuxplusone, do you happen to know what paper changed this? Does this look suspicious to you too?

This comment doesn't affect this review since it's not a behavior change with this patch, but we should rectify the situation in a follow-up patch if my suspicion above is confirmed.

[• Quuxplusone]

libcxx/include/vector

1105

This seems to have changed in C++14. @Quuxplusone, do you happen to know what paper changed this? Does this look suspicious to you too?

Whenever you see default arguments (which are the devil) and the shuffling-around of ctor overload sets, it's almost certainly due to p1163... but maybe actually not, in this case. :) According to timsong-cpp.github.io, C++11 had

explicit vector(const Allocator& = Allocator());
explicit vector(size_type n);
vector(size_type n, const T& value, const Allocator& = Allocator());

and C++14 had

vector();
explicit vector(const Allocator&);
explicit vector(size_type n, const Allocator& = Allocator());
vector(size_type n, const T& value, const Allocator& = Allocator());

That (n, alloc) ctor was added to C++14 via LWG2210.

Anyway, yeah, I think "value-initialize" is the correct answer. And I assume we agree that the extra move-construct is not observable.

If you're going to mess with the overload set here, now would be a great time to eliminate the default arguments entirely. ;)

libcxx/include/__config

 #  define _LIBCPP_ABI_SPAN_POINTER_ITERATORS
 // Re-worked external template instantiations for std::string with a focus on
 // performance and fast-path inlining.
 #  define _LIBCPP_ABI_STRING_OPTIMIZED_EXTERNAL_INSTANTIATION
 // Enable clang::trivial_abi on std::unique_ptr.
 #  define _LIBCPP_ABI_ENABLE_UNIQUE_PTR_TRIVIAL_ABI
 // Enable clang::trivial_abi on std::shared_ptr and std::weak_ptr
 #  define _LIBCPP_ABI_ENABLE_SHARED_PTR_TRIVIAL_ABI
+// Remove vector base class
+#  define _LIBCPP_ABI_NO_VECTOR_BASE_CLASS
 #elif _LIBCPP_ABI_VERSION == 1
 #  if !defined(_LIBCPP_OBJECT_FORMAT_COFF)
 // Enable compiling copies of now inline methods into the dylib to support
 // applications compiled against older libraries. This is unnecessary with
 // COFF dllexport semantics, since dllexport forces a non-inline definition
 // of inline functions to be emitted anyway. Our own non-inline copy would
 // conflict with the dllexport-emitted copy, so we disable it.
 #    define _LIBCPP_DEPRECATED_ABI_LEGACY_LIBRARY_DEFINITIONS_FOR_INLINE_FUNCTIONS

libcxx/include/vector

 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <bool>
 struct __vector_base_common;
 
 template <>
 struct __vector_base_common<true> {
     // Both are defined in vector.cpp
     _LIBCPP_NORETURN _LIBCPP_EXPORTED_FROM_ABI void __throw_length_error() const;
     _LIBCPP_NORETURN _LIBCPP_EXPORTED_FROM_ABI void __throw_out_of_range() const;
 };
 
 template <class _Tp, class _Allocator>
 class __vector_base
     : protected __vector_base_common<true> // This base class is historical, but it needs to remain for ABI compatibility
 {
     typedef _Allocator                                           allocator_type;
     typedef typename allocator_traits<allocator_type>::pointer   pointer;
 
 protected:
     pointer                                                      __begin_;
     pointer                                                      __end_;
_LIBCPP_INLINE_VISIBILITY __vector_base(allocator_type&& __a) _NOEXCEPT
       : __begin_(nullptr),
         __end_(nullptr),
         __end_cap_(nullptr, _VSTD::move(__a)) {}
 #endif
 };
 
 template <class _Tp, class _Allocator /* = allocator<_Tp> */>
 class _LIBCPP_TEMPLATE_VIS vector
+#ifndef _LIBCPP_ABI_NO_VECTOR_BASE_CLASS
     // This base class is historical, but it needs to remain for ABI compatibility.
     : private __vector_base<_Tp, _Allocator>
+#endif
 {
 private:
     typedef __vector_base<_Tp, _Allocator>                  __base;
     typedef allocator<_Tp>                                  __default_allocator_type;
 public:
     typedef vector                                          __self;
     typedef _Tp                                             value_type;
     typedef _Allocator                                      allocator_type;
vector() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
         _VSTD::__debug_db_insert_c(this);
     }
     _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a)
 #if _LIBCPP_STD_VER <= 14
         _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
 #else
         _NOEXCEPT
 #endif
+#ifdef _LIBCPP_ABI_NO_VECTOR_BASE_CLASS
+        : __end_cap_(nullptr, __a)
+#else
         : __base(__a)
+#endif
     {
         _VSTD::__debug_db_insert_c(this);
     }
     explicit vector(size_type __n);
 #if _LIBCPP_STD_VER > 11
     explicit vector(size_type __n, const allocator_type& __a);
 #endif
     vector(size_type __n, const value_type& __x);
 
     template <class = __enable_if_t<__is_allocator<_Allocator>::value> >
     vector(size_type __n, const value_type& __x, const allocator_type& __a)
+#ifdef _LIBCPP_ABI_NO_VECTOR_BASE_CLASS
+        : __end_cap_(nullptr, __a)
+#else
         : __base(__a)
+#endif
     {
       _VSTD::__debug_db_insert_c(this);
       if (__n > 0)
       {
           __vallocate(__n);
           __construct_at_end(__n, __x);
       }
     }
#if _LIBCPP_DEBUG_LEVEL == 2
     bool __dereferenceable(const const_iterator* __i) const;
     bool __decrementable(const const_iterator* __i) const;
     bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
 
 #endif // _LIBCPP_DEBUG_LEVEL == 2
 
 private:
+#ifdef _LIBCPP_ABI_NO_VECTOR_BASE_CLASS
+    pointer __begin_ = nullptr;
+    pointer __end_ = nullptr;
+    __compressed_pair<pointer, allocator_type> __end_cap_ =
+        __compressed_pair<pointer, allocator_type>(nullptr, allocator_type());
+#endif
+
     _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
     _LIBCPP_INLINE_VISIBILITY void __invalidate_iterators_past(pointer __new_last);
     void __vallocate(size_type __n);
     void __vdeallocate() _NOEXCEPT;
     _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
     void __construct_at_end(size_type __n);
     _LIBCPP_INLINE_VISIBILITY
     void __construct_at_end(size_type __n, const_reference __x);
void __move_assign_alloc(vector& __c)
       _NOEXCEPT_(
           !__alloc_traits::propagate_on_container_move_assignment::value ||
           is_nothrow_move_assignable<allocator_type>::value)
       {__move_assign_alloc(__c, integral_constant<bool,
                     __alloc_traits::propagate_on_container_move_assignment::value>());}
 
   _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI
   void __throw_length_error() const {
-#ifndef _LIBCPP_NO_EXCEPTIONS
-    __vector_base_common<true>::__throw_length_error();
-#else
-    _VSTD::abort();
-#endif
+      _VSTD::__throw_length_error("vector");
   }
 
   _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI
   void __throw_out_of_range() const {
-#ifndef _LIBCPP_NO_EXCEPTIONS
-    __vector_base_common<true>::__throw_out_of_range();
-#else
-    _VSTD::abort();
-#endif
+      _VSTD::__throw_out_of_range("vector");
   }
 
   _LIBCPP_INLINE_VISIBILITY
   void __copy_assign_alloc(const vector& __c, true_type)
   {
     if (__alloc() != __c.__alloc())
     {
       __clear();
else
         allocator_type& __a = this->__alloc();
         __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
         __v.__construct_at_end(__n, __x);
         __swap_out_circular_buffer(__v);
     }
 }
 
 template <class _Tp, class _Allocator>
 vector<_Tp, _Allocator>::vector(size_type __n)
 {
     _VSTD::__debug_db_insert_c(this);
     if (__n > 0)
     {
         __vallocate(__n);
         __construct_at_end(__n);
     }
 }
 
 #if _LIBCPP_STD_VER > 11
 template <class _Tp, class _Allocator>
 vector<_Tp, _Allocator>::vector(size_type __n, const allocator_type& __a)
+#ifdef _LIBCPP_ABI_NO_VECTOR_BASE_CLASS
+    : __end_cap_(nullptr, __a)
+#else
     : __base(__a)
+#endif
 {
     _VSTD::__debug_db_insert_c(this);
     if (__n > 0)
     {
         __vallocate(__n);
         __construct_at_end(__n);
     }
 }

 template <class _Tp, class _Allocator>
 template <class _InputIterator>
 vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
        typename enable_if<__is_cpp17_input_iterator  <_InputIterator>::value &&
                          !__is_cpp17_forward_iterator<_InputIterator>::value &&
                          is_constructible<
                             value_type,
                             typename iterator_traits<_InputIterator>::reference>::value>::type*)
+#ifdef _LIBCPP_ABI_NO_VECTOR_BASE_CLASS
+    : __end_cap_(nullptr, __a)
+#else
     : __base(__a)
+#endif
 {
     _VSTD::__debug_db_insert_c(this);
     for (; __first != __last; ++__first)
         __emplace_back(*__first);
 }
 
 template <class _Tp, class _Allocator>
 template <class _ForwardIterator>

 
 template <class _Tp, class _Allocator>
 template <class _ForwardIterator>
 vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
                                 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value &&
                                 is_constructible<
                                    value_type,
                                    typename iterator_traits<_ForwardIterator>::reference>::value>::type*)
+#ifdef _LIBCPP_ABI_NO_VECTOR_BASE_CLASS
+    : __end_cap_(nullptr, __a)
+#else
     : __base(__a)
+#endif
 {
     _VSTD::__debug_db_insert_c(this);
     size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
     if (__n > 0)
     {
         __vallocate(__n);
         __construct_at_end(__first, __last, __n);
     }
 }
 
 template <class _Tp, class _Allocator>
 vector<_Tp, _Allocator>::vector(const vector& __x)
+#ifdef _LIBCPP_ABI_NO_VECTOR_BASE_CLASS
+    : __end_cap_(nullptr, __alloc_traits::select_on_container_copy_construction(__x.__alloc()))
+#else
     : __base(__alloc_traits::select_on_container_copy_construction(__x.__alloc()))
+#endif
 {
     _VSTD::__debug_db_insert_c(this);
     size_type __n = __x.size();
     if (__n > 0)
     {
         __vallocate(__n);
         __construct_at_end(__x.__begin_, __x.__end_, __n);
     }
 }
 
 template <class _Tp, class _Allocator>
 vector<_Tp, _Allocator>::vector(const vector& __x, const __identity_t<allocator_type>& __a)
+#ifdef _LIBCPP_ABI_NO_VECTOR_BASE_CLASS
+    : __end_cap_(nullptr, __a)
+#else
     : __base(__a)
+#endif
 {
     _VSTD::__debug_db_insert_c(this);
     size_type __n = __x.size();
     if (__n > 0)
     {
         __vallocate(__n);
         __construct_at_end(__x.__begin_, __x.__end_, __n);
     }
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY
 vector<_Tp, _Allocator>::vector(vector&& __x)
 #if _LIBCPP_STD_VER > 14
         _NOEXCEPT
 #else
         _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
 #endif
+#ifdef _LIBCPP_ABI_NO_VECTOR_BASE_CLASS
+    : __end_cap_(nullptr, _VSTD::move(__x.__alloc()))
+#else
     : __base(_VSTD::move(__x.__alloc()))
+#endif
 {
     _VSTD::__debug_db_insert_c(this);
 #if _LIBCPP_DEBUG_LEVEL == 2
     __get_db()->swap(this, _VSTD::addressof(__x));
 #endif
     this->__begin_ = __x.__begin_;
     this->__end_ = __x.__end_;
     this->__end_cap() = __x.__end_cap();
     __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
 }
 
 template <class _Tp, class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY
 vector<_Tp, _Allocator>::vector(vector&& __x, const __identity_t<allocator_type>& __a)
+#ifdef _LIBCPP_ABI_NO_VECTOR_BASE_CLASS
+    : __end_cap_(nullptr, __a)
+#else
     : __base(__a)
+#endif
 {
     _VSTD::__debug_db_insert_c(this);
     if (__a == __x.__alloc())
     {
         this->__begin_ = __x.__begin_;
         this->__end_ = __x.__end_;
         this->__end_cap() = __x.__end_cap();
         __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
if (__il.size() > 0)
         __vallocate(__il.size());
         __construct_at_end(__il.begin(), __il.end(), __il.size());
     }
 }
 
 template <class _Tp, class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY
 vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
+#ifdef _LIBCPP_ABI_NO_VECTOR_BASE_CLASS
+    : __end_cap_(nullptr, __a)
+#else
     : __base(__a)
+#endif
 {
     _VSTD::__debug_db_insert_c(this);
     if (__il.size() > 0)
     {
         __vallocate(__il.size());
         __construct_at_end(__il.begin(), __il.end(), __il.size());
     }
 }