From 6f00ccbad3d72a39d9e2bc0d500dbd62d1abc60f Mon Sep 17 00:00:00 2001 From: =?utf8?q?Fran=C3=A7ois=20Dumont?= Date: Tue, 21 Jan 2020 07:18:08 +0100 Subject: [PATCH] libstdc++: Fix and improve std::vector implementation. Do not consider allocator noexcept qualification for vector move constructor. Improve swap performance using TBAA like in main vector implementation. Bypass _M_initialize_dispatch/_M_assign_dispatch in post-c++11 modes. libstdc++-v3/ChangeLog: * include/bits/stl_bvector.h [_GLIBCXX_INLINE_VERSION](_Bvector_impl_data::_M_start): Define as _Bit_type*. (_Bvector_impl_data(const _Bvector_impl_data&)): Default. (_Bvector_impl_data(_Bvector_impl_data&&)): Delegate to latter. (_Bvector_impl_data::operator=(const _Bvector_impl_data&)): Default. (_Bvector_impl_data::_M_move_data(_Bvector_impl_data&&)): Use latter. (_Bvector_impl_data::_M_reset()): Likewise. (_Bvector_impl_data::_M_swap_data): New. (_Bvector_impl::_Bvector_impl(_Bvector_impl&&)): Implement explicitely. (_Bvector_impl::_Bvector_impl(_Bit_alloc_type&&, _Bvector_impl&&)): New. (_Bvector_base::_Bvector_base(_Bvector_base&&, const allocator_type&)): New, use latter. (vector::vector(vector&&, const allocator_type&, true_type)): New, use latter. (vector::vector(vector&&, const allocator_type&, false_type)): New. (vector::vector(vector&&, const allocator_type&)): Use latters. (vector::vector(const vector&, const allocator_type&)): Adapt. [__cplusplus >= 201103](vector::vector(_InputIt, _InputIt, const allocator_type&)): Use _M_initialize_range. (vector::operator[](size_type)): Use iterator operator[]. (vector::operator[](size_type) const): Use const_iterator operator[]. (vector::swap(vector&)): Add assertions on allocators. Use _M_swap_data. [__cplusplus >= 201103](vector::insert(const_iterator, _InputIt, _InputIt)): Use _M_insert_range. (vector::_M_initialize(size_type)): Adapt. [__cplusplus >= 201103](vector::_M_initialize_dispatch): Remove. [__cplusplus >= 201103](vector::_M_insert_dispatch): Remove. * python/libstdcxx/v6/printers.py (StdVectorPrinter._iterator): Stop using start _M_offset. (StdVectorPrinter.to_string): Likewise. * testsuite/23_containers/vector/bool/allocator/swap.cc: Adapt. * testsuite/23_containers/vector/bool/cons/noexcept_move_construct.cc: Add check. --- libstdc++-v3/include/bits/stl_bvector.h | 140 +++++++++++------- libstdc++-v3/python/libstdcxx/v6/printers.py | 5 +- .../vector/bool/allocator/swap.cc | 22 ++- .../bool/cons/noexcept_move_construct.cc | 32 +++- 4 files changed, 130 insertions(+), 69 deletions(-) diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h index a365e7182eb..d6f5435bdfb 100644 --- a/libstdc++-v3/include/bits/stl_bvector.h +++ b/libstdc++-v3/include/bits/stl_bvector.h @@ -427,53 +427,75 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER struct _Bvector_impl_data { - _Bit_iterator _M_start; - _Bit_iterator _M_finish; - _Bit_pointer _M_end_of_storage; +#if !_GLIBCXX_INLINE_VERSION + _Bit_iterator _M_start; +#else + // We don't need the offset field for the start, it's always zero. + struct { + _Bit_type* _M_p; + // Allow assignment from iterators (assume offset is zero): + void operator=(_Bit_iterator __it) { _M_p = __it._M_p; } + } _M_start; +#endif + _Bit_iterator _M_finish; + _Bit_pointer _M_end_of_storage; _Bvector_impl_data() _GLIBCXX_NOEXCEPT : _M_start(), _M_finish(), _M_end_of_storage() { } #if __cplusplus >= 201103L + _Bvector_impl_data(const _Bvector_impl_data&) = default; + _Bvector_impl_data& + operator=(const _Bvector_impl_data&) = default; + _Bvector_impl_data(_Bvector_impl_data&& __x) noexcept - : _M_start(__x._M_start), _M_finish(__x._M_finish) - , _M_end_of_storage(__x._M_end_of_storage) + : _Bvector_impl_data(__x) { __x._M_reset(); } void _M_move_data(_Bvector_impl_data&& __x) noexcept { - this->_M_start = __x._M_start; - this->_M_finish = __x._M_finish; - this->_M_end_of_storage = __x._M_end_of_storage; + *this = __x; __x._M_reset(); } #endif void _M_reset() _GLIBCXX_NOEXCEPT + { *this = _Bvector_impl_data(); } + + void + _M_swap_data(_Bvector_impl_data& __x) _GLIBCXX_NOEXCEPT { - _M_start = _M_finish = _Bit_iterator(); - _M_end_of_storage = _Bit_pointer(); + // Do not use std::swap(_M_start, __x._M_start), etc as it loses + // information used by TBAA. + std::swap(*this, __x); } }; struct _Bvector_impl : public _Bit_alloc_type, public _Bvector_impl_data - { - public: - _Bvector_impl() _GLIBCXX_NOEXCEPT_IF( - is_nothrow_default_constructible<_Bit_alloc_type>::value) - : _Bit_alloc_type() - { } + { + _Bvector_impl() _GLIBCXX_NOEXCEPT_IF( + is_nothrow_default_constructible<_Bit_alloc_type>::value) + : _Bit_alloc_type() + { } - _Bvector_impl(const _Bit_alloc_type& __a) _GLIBCXX_NOEXCEPT - : _Bit_alloc_type(__a) - { } + _Bvector_impl(const _Bit_alloc_type& __a) _GLIBCXX_NOEXCEPT + : _Bit_alloc_type(__a) + { } #if __cplusplus >= 201103L - _Bvector_impl(_Bvector_impl&&) = default; + // Not defaulted, to enforce noexcept(true) even when + // !is_nothrow_move_constructible<_Bit_alloc_type>. + _Bvector_impl(_Bvector_impl&& __x) noexcept + : _Bit_alloc_type(std::move(__x)), _Bvector_impl_data(std::move(__x)) + { } + + _Bvector_impl(_Bit_alloc_type&& __a, _Bvector_impl&& __x) noexcept + : _Bit_alloc_type(std::move(__a)), _Bvector_impl_data(std::move(__x)) + { } #endif _Bit_type* @@ -511,6 +533,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER #if __cplusplus >= 201103L _Bvector_base(_Bvector_base&&) = default; + + _Bvector_base(_Bvector_base&& __x, const allocator_type& __a) noexcept + : _M_impl(_Bit_alloc_type(__a), std::move(__x._M_impl)) + { } #endif ~_Bvector_base() @@ -647,14 +673,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator())) { _M_initialize(__x.size()); - _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start); + _M_copy_aligned(__x.begin(), __x.end(), begin()); } #if __cplusplus >= 201103L vector(vector&&) = default; - vector(vector&& __x, const allocator_type& __a) - noexcept(_Bit_alloc_traits::_S_always_equal()) + private: + vector(vector&& __x, const allocator_type& __a, true_type) noexcept + : _Base(std::move(__x), __a) + { } + + vector(vector&& __x, const allocator_type& __a, false_type) : _Base(__a) { if (__x.get_allocator() == __a) @@ -667,11 +697,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } } + public: + vector(vector&& __x, const allocator_type& __a) + noexcept(_Bit_alloc_traits::_S_always_equal()) + : vector(std::move(__x), __a, + typename _Bit_alloc_traits::is_always_equal{}) + { } + vector(const vector& __x, const allocator_type& __a) : _Base(__a) { _M_initialize(__x.size()); - _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start); + _M_copy_aligned(__x.begin(), __x.end(), begin()); } vector(initializer_list __l, @@ -689,13 +726,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a = allocator_type()) : _Base(__a) - { _M_initialize_dispatch(__first, __last, __false_type()); } + { + _M_initialize_range(__first, __last, + std::__iterator_category(__first)); + } #else template vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a = allocator_type()) : _Base(__a) { + // Check whether it's an integral type. If so, it's not an iterator. typedef typename std::__is_integer<_InputIterator>::__type _Integral; _M_initialize_dispatch(__first, __last, _Integral()); } @@ -762,7 +803,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER vector& operator=(initializer_list __l) { - this->assign (__l.begin(), __l.end()); + this->assign(__l.begin(), __l.end()); return *this; } #endif @@ -786,6 +827,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void assign(_InputIterator __first, _InputIterator __last) { + // Check whether it's an integral type. If so, it's not an iterator. typedef typename std::__is_integer<_InputIterator>::__type _Integral; _M_assign_dispatch(__first, __last, _Integral()); } @@ -874,17 +916,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER reference operator[](size_type __n) - { - return *iterator(this->_M_impl._M_start._M_p - + __n / int(_S_word_bit), __n % int(_S_word_bit)); - } + { return begin()[__n]; } const_reference operator[](size_type __n) const - { - return *const_iterator(this->_M_impl._M_start._M_p - + __n / int(_S_word_bit), __n % int(_S_word_bit)); - } + { return begin()[__n]; } protected: void @@ -951,10 +987,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void swap(vector& __x) _GLIBCXX_NOEXCEPT { - std::swap(this->_M_impl._M_start, __x._M_impl._M_start); - std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); - std::swap(this->_M_impl._M_end_of_storage, - __x._M_impl._M_end_of_storage); +#if __cplusplus >= 201103L + __glibcxx_assert(_Bit_alloc_traits::propagate_on_container_swap::value + || _M_get_Bit_allocator() == __x._M_get_Bit_allocator()); +#endif + this->_M_impl._M_swap_data(__x._M_impl); _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(), __x._M_get_Bit_allocator()); } @@ -992,8 +1029,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _InputIterator __first, _InputIterator __last) { difference_type __offset = __position - cbegin(); - _M_insert_dispatch(__position._M_const_cast(), - __first, __last, __false_type()); + _M_insert_range(__position._M_const_cast(), + __first, __last, + std::__iterator_category(__first)); return begin() + __offset; } #else @@ -1002,6 +1040,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER insert(iterator __position, _InputIterator __first, _InputIterator __last) { + // Check whether it's an integral type. If so, it's not an iterator. typedef typename std::__is_integer<_InputIterator>::__type _Integral; _M_insert_dispatch(__position, __first, __last, _Integral()); } @@ -1113,15 +1152,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { _Bit_pointer __q = this->_M_allocate(__n); this->_M_impl._M_end_of_storage = __q + _S_nword(__n); - this->_M_impl._M_start = iterator(std::__addressof(*__q), 0); + iterator __start = iterator(std::__addressof(*__q), 0); + this->_M_impl._M_start = __start; + this->_M_impl._M_finish = __start + difference_type(__n); } - else - { - this->_M_impl._M_end_of_storage = _Bit_pointer(); - this->_M_impl._M_start = iterator(0, 0); - } - this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n); - } void @@ -1141,8 +1175,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _M_shrink_to_fit(); #endif - // Check whether it's an integral type. If so, it's not an iterator. - +#if __cplusplus < 201103L // _GLIBCXX_RESOLVE_LIB_DEFECTS // 438. Ambiguity in the "do the right thing" clause template @@ -1159,6 +1192,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER __false_type) { _M_initialize_range(__first, __last, std::__iterator_category(__first)); } +#endif template void @@ -1176,7 +1210,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { const size_type __n = std::distance(__first, __last); _M_initialize(__n); - std::copy(__first, __last, this->_M_impl._M_start); + std::copy(__first, __last, begin()); } #if __cplusplus < 201103L @@ -1240,8 +1274,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } } - // Check whether it's an integral type. If so, it's not an iterator. - +#if __cplusplus < 201103L // _GLIBCXX_RESOLVE_LIB_DEFECTS // 438. Ambiguity in the "do the right thing" clause template @@ -1257,6 +1290,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER __false_type) { _M_insert_range(__pos, __first, __last, std::__iterator_category(__first)); } +#endif void _M_fill_insert(iterator __position, size_type __n, bool __x); diff --git a/libstdc++-v3/python/libstdcxx/v6/printers.py b/libstdc++-v3/python/libstdcxx/v6/printers.py index e4da8dfe5b6..0bf307b8e5f 100644 --- a/libstdc++-v3/python/libstdcxx/v6/printers.py +++ b/libstdc++-v3/python/libstdcxx/v6/printers.py @@ -405,7 +405,7 @@ class StdVectorPrinter: self.bitvec = bitvec if bitvec: self.item = start['_M_p'] - self.so = start['_M_offset'] + self.so = 0 self.finish = finish['_M_p'] self.fo = finish['_M_offset'] itype = self.item.dereference().type @@ -453,12 +453,11 @@ class StdVectorPrinter: end = self.val['_M_impl']['_M_end_of_storage'] if self.is_bool: start = self.val['_M_impl']['_M_start']['_M_p'] - so = self.val['_M_impl']['_M_start']['_M_offset'] finish = self.val['_M_impl']['_M_finish']['_M_p'] fo = self.val['_M_impl']['_M_finish']['_M_offset'] itype = start.dereference().type bl = 8 * itype.sizeof - length = (bl - so) + bl * ((finish - start) - 1) + fo + length = bl * (finish - start) + fo capacity = bl * (end - start) return ('%s of length %d, capacity %d' % (self.typename, int (length), int (capacity))) diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/allocator/swap.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/allocator/swap.cc index a8107145c58..793115b473e 100644 --- a/libstdc++-v3/testsuite/23_containers/vector/bool/allocator/swap.cc +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/allocator/swap.cc @@ -28,19 +28,17 @@ namespace __gnu_test // It is undefined behaviour to swap() containers with unequal allocators // if the allocator doesn't propagate, so ensure the allocators compare // equal, while still being able to test propagation via get_personality(). - bool - operator==(const propagating_allocator&, - const propagating_allocator&) - { - return true; - } + template + bool + operator==(const propagating_allocator&, + const propagating_allocator&) + { return true; } - bool - operator!=(const propagating_allocator&, - const propagating_allocator&) - { - return false; - } + template + bool + operator!=(const propagating_allocator&, + const propagating_allocator&) + { return false; } } using __gnu_test::propagating_allocator; diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/cons/noexcept_move_construct.cc index 03794d8ebd8..296ba33bba8 100644 --- a/libstdc++-v3/testsuite/23_containers/vector/bool/cons/noexcept_move_construct.cc +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/cons/noexcept_move_construct.cc @@ -23,4 +23,34 @@ typedef std::vector vbtype; -static_assert(std::is_nothrow_move_constructible::value, "Error"); +static_assert( std::is_nothrow_move_constructible::value, + "noexcept move constructor" ); +static_assert( std::is_nothrow_constructible::value, + "noexcept move constructor with allocator" ); + +template + class not_noexcept_move_constructor_alloc : public std::allocator + { + public: + not_noexcept_move_constructor_alloc() noexcept { } + + not_noexcept_move_constructor_alloc( + const not_noexcept_move_constructor_alloc& x) noexcept + : std::allocator(x) + { } + + not_noexcept_move_constructor_alloc( + not_noexcept_move_constructor_alloc&& x) noexcept(false) + : std::allocator(std::move(x)) + { } + + template + struct rebind + { typedef not_noexcept_move_constructor_alloc<_Tp1> other; }; + }; + +typedef std::vector> vbtype2; + +static_assert( std::is_nothrow_move_constructible::value, + "noexcept move constructor with not noexcept alloc" ); -- 2.30.2