* Default std::vector<bool> default and move constructor @ 2017-05-15 18:38 François Dumont 2017-05-15 19:36 ` Marc Glisse 2017-05-25 16:33 ` Jonathan Wakely 0 siblings, 2 replies; 19+ messages in thread From: François Dumont @ 2017-05-15 18:38 UTC (permalink / raw) To: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 1691 bytes --] Hi Following what I have started on RbTree here is a patch to default implementation of default and move constructors on std::vector<bool>. As in _Rb_tree_impl the default allocator is not value initialized anymore. We could add a small helper type arround the allocator to do this value initialization per default. Should I do so ? I also added some optimizations. Especially replacement of std::fill with calls to __builtin_memset. Has anyone ever proposed to optimize std::fill in such a way ? It would require a test on the value used to fill the range but it might worth this additional runtime check, no ? * include/bits/stl_bvector.h (_Bvector_impl_data): New. (_Bvector_impl): Inherits from latter. (_Bvector_impl(_Bit_alloc_type&&)): Delete. (_Bvector_impl(_Bvector_impl&&)): New, default. (_Bvector_base()): Default. (_Bvector_base(_Bvector_base&&)): Default. (_Bvector_base::_M_move_data(_Bvector_base&&)): New. (vector(vector&&, const allocator_type&)): Use latter. (vector<bool>::operator=(vector&&)): Likewise. (vector<bool>::vector()): Default. (vector<bool>::assign(_InputIterator, _InputIterator)): Use _M_assign_aux. (vector<bool>::assign(initializer_list<bool>)): Likewise. (vector<bool>::_M_initialize_value(bool)): New. (vector<bool>(size_type, const bool&, const allocator_type&)): Use latter. (vector<bool>::_M_initialize_dispatch(_Integer, _Integer, __true_type)): Likewise. (vector<bool>::_M_fill_assign(size_t, bool)): Likewise. Tested under Linux x86_64 normal mode, with and without versioned namespace. Ok to commit ? François [-- Attachment #2: bvector.patch --] [-- Type: text/x-patch, Size: 8584 bytes --] diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h index 37e000a..a6afced 100644 --- a/libstdc++-v3/include/bits/stl_bvector.h +++ b/libstdc++-v3/include/bits/stl_bvector.h @@ -399,8 +399,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { if (__first._M_p != __last._M_p) { - std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0); - __fill_bvector(__first, _Bit_iterator(__first._M_p + 1, 0), __x); + _Bit_type *__first_p = __first._M_p; + if (__first._M_offset != 0) + __fill_bvector(__first, _Bit_iterator(++__first_p, 0), __x); + + __builtin_memset(__first_p, __x ? ~0 : 0, + (__last._M_p - __first_p) * sizeof(_Bit_type)); + + if (__last._M_offset != 0) __fill_bvector(_Bit_iterator(__last._M_p, 0), __last, __x); } else @@ -416,33 +422,66 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Bit_alloc_traits; typedef typename _Bit_alloc_traits::pointer _Bit_pointer; - struct _Bvector_impl - : public _Bit_alloc_type + struct _Bvector_impl_data { _Bit_iterator _M_start; _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(_Bvector_impl_data&& __x) noexcept + : _M_start(__x._M_start), _M_finish(__x._M_finish) + , _M_end_of_storage(__x._M_end_of_storage) + { __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; + __x._M_reset(); + } + + void + _M_reset() noexcept + { + this->_M_start = _Bit_iterator(); + this->_M_finish = _Bit_iterator(); + this->_M_end_of_storage = nullptr; + } +#endif + }; + + struct _Bvector_impl + : public _Bit_alloc_type, public _Bvector_impl_data + { + public: +#if __cplusplus >= 201103L + _Bvector_impl() = default; +#else _Bvector_impl() - : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage() + : _Bit_alloc_type() { } +#endif _Bvector_impl(const _Bit_alloc_type& __a) - : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage() + : _Bit_alloc_type(__a) { } #if __cplusplus >= 201103L - _Bvector_impl(_Bit_alloc_type&& __a) - : _Bit_alloc_type(std::move(__a)), _M_start(), _M_finish(), - _M_end_of_storage() - { } + _Bvector_impl(_Bvector_impl&&) = default; #endif _Bit_type* _M_end_addr() const _GLIBCXX_NOEXCEPT { - if (_M_end_of_storage) - return std::__addressof(_M_end_of_storage[-1]) + 1; + if (this->_M_end_of_storage) + return std::__addressof(this->_M_end_of_storage[-1]) + 1; return 0; } }; @@ -462,23 +501,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER get_allocator() const _GLIBCXX_NOEXCEPT { return allocator_type(_M_get_Bit_allocator()); } +#if __cplusplus >= 201103L + _Bvector_base() = default; +#else _Bvector_base() : _M_impl() { } +#endif _Bvector_base(const allocator_type& __a) : _M_impl(__a) { } #if __cplusplus >= 201103L - _Bvector_base(_Bvector_base&& __x) noexcept - : _M_impl(std::move(__x._M_get_Bit_allocator())) - { - this->_M_impl._M_start = __x._M_impl._M_start; - this->_M_impl._M_finish = __x._M_impl._M_finish; - this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; - __x._M_impl._M_start = _Bit_iterator(); - __x._M_impl._M_finish = _Bit_iterator(); - __x._M_impl._M_end_of_storage = nullptr; - } + _Bvector_base(_Bvector_base&&) = default; #endif ~_Bvector_base() @@ -505,6 +539,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } } +#if __cplusplus >= 201103L + void + _M_move_data(_Bvector_base&& __x) noexcept + { _M_impl._M_move_data(std::move(__x._M_impl)); } +#endif + static size_t _S_nword(size_t __n) { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); } @@ -564,7 +604,8 @@ template<typename _Alloc> typedef std::reverse_iterator<iterator> reverse_iterator; typedef _Alloc allocator_type; - allocator_type get_allocator() const + allocator_type + get_allocator() const { return _Base::get_allocator(); } protected: @@ -574,11 +615,12 @@ template<typename _Alloc> using _Base::_M_get_Bit_allocator; public: - vector() #if __cplusplus >= 201103L - noexcept(is_nothrow_default_constructible<allocator_type>::value) -#endif + vector() = default; +#else + vector() : _Base() { } +#endif explicit vector(const allocator_type& __a) @@ -592,23 +634,16 @@ template<typename _Alloc> vector(size_type __n, const bool& __value, const allocator_type& __a = allocator_type()) - : _Base(__a) - { - _M_initialize(__n); - std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_addr(), - __value ? ~0 : 0); - } #else explicit vector(size_type __n, const bool& __value = bool(), const allocator_type& __a = allocator_type()) +#endif : _Base(__a) { _M_initialize(__n); - std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_addr(), - __value ? ~0 : 0); + _M_initialize_value(__value); } -#endif vector(const vector& __x) : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator())) @@ -618,22 +653,14 @@ template<typename _Alloc> } #if __cplusplus >= 201103L - vector(vector&& __x) noexcept - : _Base(std::move(__x)) { } + vector(vector&&) = default; vector(vector&& __x, const allocator_type& __a) noexcept(_Bit_alloc_traits::_S_always_equal()) : _Base(__a) { if (__x.get_allocator() == __a) - { - this->_M_impl._M_start = __x._M_impl._M_start; - this->_M_impl._M_finish = __x._M_impl._M_finish; - this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; - __x._M_impl._M_start = _Bit_iterator(); - __x._M_impl._M_finish = _Bit_iterator(); - __x._M_impl._M_end_of_storage = nullptr; - } + this->_M_move_data(std::move(__x)); else { _M_initialize(__x.size()); @@ -716,12 +743,7 @@ template<typename _Alloc> || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator()) { this->_M_deallocate(); - this->_M_impl._M_start = __x._M_impl._M_start; - this->_M_impl._M_finish = __x._M_impl._M_finish; - this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; - __x._M_impl._M_start = _Bit_iterator(); - __x._M_impl._M_finish = _Bit_iterator(); - __x._M_impl._M_end_of_storage = nullptr; + this->_M_move_data(std::move(__x)); std::__alloc_on_move(_M_get_Bit_allocator(), __x._M_get_Bit_allocator()); } @@ -760,7 +782,7 @@ template<typename _Alloc> typename = std::_RequireInputIter<_InputIterator>> void assign(_InputIterator __first, _InputIterator __last) - { _M_assign_dispatch(__first, __last, __false_type()); } + { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } #else template<typename _InputIterator> void @@ -774,7 +796,7 @@ template<typename _Alloc> #if __cplusplus >= 201103L void assign(initializer_list<bool> __l) - { this->assign(__l.begin(), __l.end()); } + { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); } #endif iterator @@ -1096,6 +1118,14 @@ template<typename _Alloc> } void + _M_initialize_value(bool __x) + { + __builtin_memset(this->_M_impl._M_start._M_p, __x ? ~0 : 0, + (this->_M_impl._M_end_addr() - this->_M_impl._M_start._M_p) + * sizeof(_Bit_type)); + } + + void _M_reallocate(size_type __n); #if __cplusplus >= 201103L @@ -1112,8 +1142,7 @@ template<typename _Alloc> _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) { _M_initialize(static_cast<size_type>(__n)); - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_addr(), __x ? ~0 : 0); + _M_initialize_value(__x); } template<typename _InputIterator> @@ -1160,15 +1189,13 @@ template<typename _Alloc> { if (__n > size()) { - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_addr(), __x ? ~0 : 0); + _M_initialize_value(__x); insert(end(), __n - size(), __x); } else { _M_erase_at_end(begin() + __n); - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_addr(), __x ? ~0 : 0); + _M_initialize_value(__x); } } ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Default std::vector<bool> default and move constructor 2017-05-15 18:38 Default std::vector<bool> default and move constructor François Dumont @ 2017-05-15 19:36 ` Marc Glisse 2017-05-16 20:38 ` François Dumont 2017-05-19 19:42 ` François Dumont 2017-05-25 16:33 ` Jonathan Wakely 1 sibling, 2 replies; 19+ messages in thread From: Marc Glisse @ 2017-05-15 19:36 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches On Mon, 15 May 2017, François Dumont wrote: > I also added some optimizations. Especially replacement of std::fill with > calls to __builtin_memset. Has anyone ever proposed to optimize std::fill in > such a way ? It would require a test on the value used to fill the range but > it might worth this additional runtime check, no ? Note that with -O3, gcc recognizes the pattern in std::fill and generates a call to memset (there is a bit too much extra code around the memset, but a couple match.pd transformations should fix that). That doesn't mean we can't save it the work. If you want to save the runtime check, there is always __builtin_constant_p... The __fill_bvector part of the fill overload for vector<bool> could do with some improvements as well. Looping is unnecessary, one just needs to produce the right mask and and or or with it, that shouldn't take more than 4 instructions or so. There was a time when I suggested overloading std::count and std::find in order to use __builtin_popcount, etc. But from what I've seen of committee discussions, I expect that there will be specialized algorithms (possibly member functions) eventually, making the overload less useful. -- Marc Glisse ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Default std::vector<bool> default and move constructor 2017-05-15 19:36 ` Marc Glisse @ 2017-05-16 20:38 ` François Dumont 2017-05-16 21:39 ` Marc Glisse 2017-05-19 19:42 ` François Dumont 1 sibling, 1 reply; 19+ messages in thread From: François Dumont @ 2017-05-16 20:38 UTC (permalink / raw) To: libstdc++; +Cc: gcc-patches On 15/05/2017 21:31, Marc Glisse wrote: > On Mon, 15 May 2017, François Dumont wrote: > >> I also added some optimizations. Especially replacement of >> std::fill with calls to __builtin_memset. Has anyone ever proposed to >> optimize std::fill in such a way ? It would require a test on the >> value used to fill the range but it might worth this additional >> runtime check, no ? > > Note that with -O3, gcc recognizes the pattern in std::fill and > generates a call to memset (there is a bit too much extra code around > the memset, but a couple match.pd transformations should fix that). Good to know, at least g++ will be able to spend more time on other optimizations :-) What is match.pd ? > That doesn't mean we can't save it the work. If you want to save the > runtime check, there is always __builtin_constant_p... Good point, I will give it a try. > > The __fill_bvector part of the fill overload for vector<bool> could do > with some improvements as well. Looping is unnecessary, one just needs > to produce the right mask and and or or with it, that shouldn't take > more than 4 instructions or so. Yes, good idear, I'll submit another patch after this one. > > There was a time when I suggested overloading std::count and std::find > in order to use __builtin_popcount, etc. But from what I've seen of > committee discussions, I expect that there will be specialized > algorithms (possibly member functions) eventually, making the overload > less useful. > ok, thanks for those feedbacks. François ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Default std::vector<bool> default and move constructor 2017-05-16 20:38 ` François Dumont @ 2017-05-16 21:39 ` Marc Glisse 0 siblings, 0 replies; 19+ messages in thread From: Marc Glisse @ 2017-05-16 21:39 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches On Tue, 16 May 2017, François Dumont wrote: > What is match.pd ? It is a file in gcc where we describe simple pattern-matching optimizations. In this case, IIRC, the missing transformations were * ptr + n == ptr + 1 --> n == 1 (we already do it if 1 is replaced by a variable or 0) * ((n/8)+1)*8 --> n+8 when the division is known to be exact -- Marc Glisse ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Default std::vector<bool> default and move constructor 2017-05-15 19:36 ` Marc Glisse 2017-05-16 20:38 ` François Dumont @ 2017-05-19 19:42 ` François Dumont 2017-05-23 20:14 ` François Dumont 1 sibling, 1 reply; 19+ messages in thread From: François Dumont @ 2017-05-19 19:42 UTC (permalink / raw) To: libstdc++; +Cc: gcc-patches [-- Attachment #1: Type: text/plain, Size: 482 bytes --] Hi On 15/05/2017 21:31, Marc Glisse wrote: > The __fill_bvector part of the fill overload for vector<bool> could do > with some improvements as well. Looping is unnecessary, one just needs > to produce the right mask and and or or with it, that shouldn't take > more than 4 instructions or so. > > I have implemented this idear so I would like to amend my patch proposal with this additional optimization. Tested under Linux x86_64 normal mode. Ok to commit ? François [-- Attachment #2: bvector.patch --] [-- Type: text/x-patch, Size: 9395 bytes --] diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h index 37e000a..09683f7 100644 --- a/libstdc++-v3/include/bits/stl_bvector.h +++ b/libstdc++-v3/include/bits/stl_bvector.h @@ -388,10 +388,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return __x + __n; } inline void - __fill_bvector(_Bit_iterator __first, _Bit_iterator __last, bool __x) + __fill_bvector(_Bit_type * __v, + unsigned int __first, unsigned int __last, bool __x) { - for (; __first != __last; ++__first) - *__first = __x; + const _Bit_type __fmask = ~0ul << __first; + const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last); + const _Bit_type __mask = __fmask & __lmask; + + if (__x) + *__v |= __mask; + else + *__v &= ~__mask; } inline void @@ -399,12 +406,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { if (__first._M_p != __last._M_p) { - std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0); - __fill_bvector(__first, _Bit_iterator(__first._M_p + 1, 0), __x); - __fill_bvector(_Bit_iterator(__last._M_p, 0), __last, __x); + _Bit_type *__first_p = __first._M_p; + if (__first._M_offset != 0) + __fill_bvector(__first_p++, __first._M_offset, _S_word_bit, __x); + + __builtin_memset(__first_p, __x ? ~0 : 0, + (__last._M_p - __first_p) * sizeof(_Bit_type)); + + if (__last._M_offset != 0) + __fill_bvector(__last._M_p, 0, __last._M_offset, __x); } else - __fill_bvector(__first, __last, __x); + __fill_bvector(__first._M_p, __first._M_offset, __last._M_offset, __x); } template<typename _Alloc> @@ -416,33 +429,66 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Bit_alloc_traits; typedef typename _Bit_alloc_traits::pointer _Bit_pointer; - struct _Bvector_impl - : public _Bit_alloc_type + struct _Bvector_impl_data { _Bit_iterator _M_start; _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(_Bvector_impl_data&& __x) noexcept + : _M_start(__x._M_start), _M_finish(__x._M_finish) + , _M_end_of_storage(__x._M_end_of_storage) + { __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; + __x._M_reset(); + } + + void + _M_reset() noexcept + { + this->_M_start = _Bit_iterator(); + this->_M_finish = _Bit_iterator(); + this->_M_end_of_storage = nullptr; + } +#endif + }; + + struct _Bvector_impl + : public _Bit_alloc_type, public _Bvector_impl_data + { + public: +#if __cplusplus >= 201103L + _Bvector_impl() = default; +#else _Bvector_impl() - : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage() + : _Bit_alloc_type() { } +#endif _Bvector_impl(const _Bit_alloc_type& __a) - : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage() + : _Bit_alloc_type(__a) { } #if __cplusplus >= 201103L - _Bvector_impl(_Bit_alloc_type&& __a) - : _Bit_alloc_type(std::move(__a)), _M_start(), _M_finish(), - _M_end_of_storage() - { } + _Bvector_impl(_Bvector_impl&&) = default; #endif _Bit_type* _M_end_addr() const _GLIBCXX_NOEXCEPT { - if (_M_end_of_storage) - return std::__addressof(_M_end_of_storage[-1]) + 1; + if (this->_M_end_of_storage) + return std::__addressof(this->_M_end_of_storage[-1]) + 1; return 0; } }; @@ -462,23 +508,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER get_allocator() const _GLIBCXX_NOEXCEPT { return allocator_type(_M_get_Bit_allocator()); } +#if __cplusplus >= 201103L + _Bvector_base() = default; +#else _Bvector_base() : _M_impl() { } +#endif _Bvector_base(const allocator_type& __a) : _M_impl(__a) { } #if __cplusplus >= 201103L - _Bvector_base(_Bvector_base&& __x) noexcept - : _M_impl(std::move(__x._M_get_Bit_allocator())) - { - this->_M_impl._M_start = __x._M_impl._M_start; - this->_M_impl._M_finish = __x._M_impl._M_finish; - this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; - __x._M_impl._M_start = _Bit_iterator(); - __x._M_impl._M_finish = _Bit_iterator(); - __x._M_impl._M_end_of_storage = nullptr; - } + _Bvector_base(_Bvector_base&&) = default; #endif ~_Bvector_base() @@ -505,6 +546,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } } +#if __cplusplus >= 201103L + void + _M_move_data(_Bvector_base&& __x) noexcept + { _M_impl._M_move_data(std::move(__x._M_impl)); } +#endif + static size_t _S_nword(size_t __n) { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); } @@ -564,7 +611,8 @@ template<typename _Alloc> typedef std::reverse_iterator<iterator> reverse_iterator; typedef _Alloc allocator_type; - allocator_type get_allocator() const + allocator_type + get_allocator() const { return _Base::get_allocator(); } protected: @@ -574,11 +622,12 @@ template<typename _Alloc> using _Base::_M_get_Bit_allocator; public: - vector() #if __cplusplus >= 201103L - noexcept(is_nothrow_default_constructible<allocator_type>::value) -#endif + vector() = default; +#else + vector() : _Base() { } +#endif explicit vector(const allocator_type& __a) @@ -592,23 +641,16 @@ template<typename _Alloc> vector(size_type __n, const bool& __value, const allocator_type& __a = allocator_type()) - : _Base(__a) - { - _M_initialize(__n); - std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_addr(), - __value ? ~0 : 0); - } #else explicit vector(size_type __n, const bool& __value = bool(), const allocator_type& __a = allocator_type()) +#endif : _Base(__a) { _M_initialize(__n); - std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_addr(), - __value ? ~0 : 0); + _M_initialize_value(__value); } -#endif vector(const vector& __x) : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator())) @@ -618,22 +660,14 @@ template<typename _Alloc> } #if __cplusplus >= 201103L - vector(vector&& __x) noexcept - : _Base(std::move(__x)) { } + vector(vector&&) = default; vector(vector&& __x, const allocator_type& __a) noexcept(_Bit_alloc_traits::_S_always_equal()) : _Base(__a) { if (__x.get_allocator() == __a) - { - this->_M_impl._M_start = __x._M_impl._M_start; - this->_M_impl._M_finish = __x._M_impl._M_finish; - this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; - __x._M_impl._M_start = _Bit_iterator(); - __x._M_impl._M_finish = _Bit_iterator(); - __x._M_impl._M_end_of_storage = nullptr; - } + this->_M_move_data(std::move(__x)); else { _M_initialize(__x.size()); @@ -716,12 +750,7 @@ template<typename _Alloc> || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator()) { this->_M_deallocate(); - this->_M_impl._M_start = __x._M_impl._M_start; - this->_M_impl._M_finish = __x._M_impl._M_finish; - this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; - __x._M_impl._M_start = _Bit_iterator(); - __x._M_impl._M_finish = _Bit_iterator(); - __x._M_impl._M_end_of_storage = nullptr; + this->_M_move_data(std::move(__x)); std::__alloc_on_move(_M_get_Bit_allocator(), __x._M_get_Bit_allocator()); } @@ -760,7 +789,7 @@ template<typename _Alloc> typename = std::_RequireInputIter<_InputIterator>> void assign(_InputIterator __first, _InputIterator __last) - { _M_assign_dispatch(__first, __last, __false_type()); } + { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } #else template<typename _InputIterator> void @@ -774,7 +803,7 @@ template<typename _Alloc> #if __cplusplus >= 201103L void assign(initializer_list<bool> __l) - { this->assign(__l.begin(), __l.end()); } + { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); } #endif iterator @@ -1096,6 +1125,14 @@ template<typename _Alloc> } void + _M_initialize_value(bool __x) + { + __builtin_memset(this->_M_impl._M_start._M_p, __x ? ~0 : 0, + (this->_M_impl._M_end_addr() - this->_M_impl._M_start._M_p) + * sizeof(_Bit_type)); + } + + void _M_reallocate(size_type __n); #if __cplusplus >= 201103L @@ -1112,8 +1149,7 @@ template<typename _Alloc> _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) { _M_initialize(static_cast<size_type>(__n)); - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_addr(), __x ? ~0 : 0); + _M_initialize_value(__x); } template<typename _InputIterator> @@ -1160,15 +1196,13 @@ template<typename _Alloc> { if (__n > size()) { - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_addr(), __x ? ~0 : 0); + _M_initialize_value(__x); insert(end(), __n - size(), __x); } else { _M_erase_at_end(begin() + __n); - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_addr(), __x ? ~0 : 0); + _M_initialize_value(__x); } } ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Default std::vector<bool> default and move constructor 2017-05-19 19:42 ` François Dumont @ 2017-05-23 20:14 ` François Dumont 0 siblings, 0 replies; 19+ messages in thread From: François Dumont @ 2017-05-23 20:14 UTC (permalink / raw) To: libstdc++; +Cc: gcc-patches Gentle reminder, ok to commit ? François On 19/05/2017 21:39, François Dumont wrote: > Hi > > On 15/05/2017 21:31, Marc Glisse wrote: >> The __fill_bvector part of the fill overload for vector<bool> could >> do with some improvements as well. Looping is unnecessary, one just >> needs to produce the right mask and and or or with it, that shouldn't >> take more than 4 instructions or so. >> >> > I have implemented this idear so I would like to amend my patch > proposal with this additional optimization. > > Tested under Linux x86_64 normal mode. > > Ok to commit ? > > François > > ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Default std::vector<bool> default and move constructor 2017-05-15 18:38 Default std::vector<bool> default and move constructor François Dumont 2017-05-15 19:36 ` Marc Glisse @ 2017-05-25 16:33 ` Jonathan Wakely 2017-05-26 21:34 ` François Dumont 1 sibling, 1 reply; 19+ messages in thread From: Jonathan Wakely @ 2017-05-25 16:33 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches On 15/05/17 19:57 +0200, François Dumont wrote: >Hi > > Following what I have started on RbTree here is a patch to default >implementation of default and move constructors on std::vector<bool>. > > As in _Rb_tree_impl the default allocator is not value initialized >anymore. We could add a small helper type arround the allocator to do >this value initialization per default. Should I do so ? It's required to be value-initialized, so if your patch changes that then it's a problem. Did we decide it's OK to do that for RB-trees? Did we actually discuss that part of the r243379 changes? N.B. defining these members as defaulted makes diagnostics worse, see PR 80858, but I think we need to fix that in the compiler anyway. ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Default std::vector<bool> default and move constructor 2017-05-25 16:33 ` Jonathan Wakely @ 2017-05-26 21:34 ` François Dumont 2017-05-27 11:16 ` Jonathan Wakely 0 siblings, 1 reply; 19+ messages in thread From: François Dumont @ 2017-05-26 21:34 UTC (permalink / raw) To: Jonathan Wakely; +Cc: libstdc++, gcc-patches On 25/05/2017 18:28, Jonathan Wakely wrote: > On 15/05/17 19:57 +0200, François Dumont wrote: >> Hi >> >> Following what I have started on RbTree here is a patch to default >> implementation of default and move constructors on std::vector<bool>. >> >> As in _Rb_tree_impl the default allocator is not value initialized >> anymore. We could add a small helper type arround the allocator to do >> this value initialization per default. Should I do so ? > > It's required to be value-initialized, so if your patch changes that > then it's a problem. > > Did we decide it's OK to do that for RB-trees? Did we actually discuss > that part of the r243379 changes? I remember a message pointing this issue but after the commit AFAIR. I thought it was from Tim but I can't find it on the archive. What is the rational of this requirement ? I started working on a type to do the allocator value initialization if there is no default constructor but it seems quite complicated to do so. It is quite sad that we can't fully benefit from this nice C++11 feature just because of this requirement. If there is any initialization needed it doesn't sound complicated to provide a default constructor. > > > N.B. defining these members as defaulted makes diagnostics worse, see > PR 80858, but I think we need to fix that in the compiler anyway. > > Ok, I hope compiler will be able to improve this situtation. François ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Default std::vector<bool> default and move constructor 2017-05-26 21:34 ` François Dumont @ 2017-05-27 11:16 ` Jonathan Wakely 2017-05-28 20:29 ` François Dumont 0 siblings, 1 reply; 19+ messages in thread From: Jonathan Wakely @ 2017-05-27 11:16 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches On 26/05/17 23:13 +0200, François Dumont wrote: >On 25/05/2017 18:28, Jonathan Wakely wrote: >>On 15/05/17 19:57 +0200, François Dumont wrote: >>>Hi >>> >>> Following what I have started on RbTree here is a patch to >>>default implementation of default and move constructors on >>>std::vector<bool>. >>> >>> As in _Rb_tree_impl the default allocator is not value >>>initialized anymore. We could add a small helper type arround the >>>allocator to do this value initialization per default. Should I do >>>so ? >> >>It's required to be value-initialized, so if your patch changes that >>then it's a problem. >> >>Did we decide it's OK to do that for RB-trees? Did we actually discuss >>that part of the r243379 changes? > >I remember a message pointing this issue but after the commit AFAIR. I >thought it was from Tim but I can't find it on the archive. > >What is the rational of this requirement ? I started working on a type >to do the allocator value initialization if there is no default >constructor but it seems quite complicated to do so. It is quite sad >that we can't fully benefit from this nice C++11 feature just because >of this requirement. If there is any initialization needed it doesn't >sound complicated to provide a default constructor. The standard says that the default constructor is: vector() : vector(Allocator()) { } That value-initializes the allocator. If the allocator type behaves differently for value-init and default-init (e.g. it has data members that are left uninitialized by default-init) then the difference matters. If you change the code so it only does default-init of the allocator then you will introduce an observable difference. I don't see any requirement that a DefaultConstructible allocator cannot leave members uninitialized, so that means the standard requires default construction of vector<bool> to value-init the allocator. Not default-init. Here's an allocator that behaves differently if value-initialized or default-initialized: template<typename T> struct Alloc { using value_type = T; Alloc() = default; template<typename U> Alloc(const Alloc<U>& a) : mem(a.mem) { } T* allocate(std::size_t n) { if (mem) throw 1; return std::allocator<T>().allocate(n); } void deallocate(T* p, std::size_t n) { std::allocator<T>().deallocate(p, n); } int mem; }; template<typename T, typename U> bool operator==(const Alloc<T>& t, const Alloc<U>& u) { return t.mem == u.mem; } template<typename T, typename U> bool operator!=(const Alloc<T>& t, const Alloc<U>& u) { return !(t == u); } ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Default std::vector<bool> default and move constructor 2017-05-27 11:16 ` Jonathan Wakely @ 2017-05-28 20:29 ` François Dumont 2017-05-29 20:57 ` François Dumont 2017-05-31 11:13 ` Jonathan Wakely 0 siblings, 2 replies; 19+ messages in thread From: François Dumont @ 2017-05-28 20:29 UTC (permalink / raw) To: Jonathan Wakely; +Cc: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 2601 bytes --] On 27/05/2017 13:14, Jonathan Wakely wrote: > On 26/05/17 23:13 +0200, François Dumont wrote: >> On 25/05/2017 18:28, Jonathan Wakely wrote: >>> On 15/05/17 19:57 +0200, François Dumont wrote: >>>> Hi >>>> >>>> Following what I have started on RbTree here is a patch to >>>> default implementation of default and move constructors on >>>> std::vector<bool>. >>>> >>>> As in _Rb_tree_impl the default allocator is not value >>>> initialized anymore. We could add a small helper type arround the >>>> allocator to do this value initialization per default. Should I do >>>> so ? >>> >>> It's required to be value-initialized, so if your patch changes that >>> then it's a problem. >>> >>> Did we decide it's OK to do that for RB-trees? Did we actually discuss >>> that part of the r243379 changes? >> >> I remember a message pointing this issue but after the commit AFAIR. >> I thought it was from Tim but I can't find it on the archive. >> >> What is the rational of this requirement ? I started working on a >> type to do the allocator value initialization if there is no default >> constructor but it seems quite complicated to do so. It is quite sad >> that we can't fully benefit from this nice C++11 feature just because >> of this requirement. If there is any initialization needed it doesn't >> sound complicated to provide a default constructor. > > The standard says that the default constructor is: > > vector() : vector(Allocator()) { } > > That value-initializes the allocator. If the allocator type behaves > differently for value-init and default-init (e.g. it has data members > that are left uninitialized by default-init) then the difference > matters. If you change the code so it only does default-init of the > allocator then you will introduce an observable difference. > > I don't see any requirement that a DefaultConstructible allocator > cannot leave members uninitialized, so that means the standard > requires default construction of vector<bool> to value-init the > allocator. Not default-init. Sure but like freedom which stop where start others' freedom so does those requirements :-). Because the Standard says that an allocator will be value-init when there is no default-init it makes usage of the C++11 default constructor more complicated. But as it is unavoidable here is a type I tried to work on to keep current implementations as long as we inherit from __alloc_value_initializer. I don't like it myself but I propose just in case you are interested. Otherwise I am also going to rework my patch to keep this initialization. François [-- Attachment #2: allocator.h.patch --] [-- Type: text/x-patch, Size: 1564 bytes --] diff --git a/libstdc++-v3/include/bits/allocator.h b/libstdc++-v3/include/bits/allocator.h index 2081386..9e8afed 100644 --- a/libstdc++-v3/include/bits/allocator.h +++ b/libstdc++-v3/include/bits/allocator.h @@ -241,6 +241,52 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION }; #endif + template<typename _Alloc, bool + = !__is_empty(_Alloc) && __is_trivial(_Alloc)> + struct __alloc_value_initializer; + + template<typename _Alloc> + struct __alloc_value_initializer<_Alloc, true> : public _Alloc + { + // Explicit value initialization. + __alloc_value_initializer() _GLIBCXX_USE_NOEXCEPT + : _Alloc() + { } + + __alloc_value_initializer(const _Alloc& __other) + _GLIBCXX_NOEXCEPT_IF( noexcept(_Alloc(__other)) ) + : _Alloc(__other) + { } + +#if __cplusplus >= 201103L + __alloc_value_initializer(_Alloc&& __other) + noexcept( noexcept(_Alloc(std::move(__other))) ) + : _Alloc(std::move(__other)) + { } +#endif + }; + + template<typename _Alloc> + struct __alloc_value_initializer<_Alloc, false> : public _Alloc + { +#if __cplusplus >= 201103L + __alloc_value_initializer() = default; + + __alloc_value_initializer(_Alloc&& __other) + noexcept( noexcept(_Alloc(std::move(__other))) ) + : _Alloc(std::move(__other)) + { } +#else + __alloc_value_initializer() throw() + { } +#endif + + __alloc_value_initializer(const _Alloc& __other) + _GLIBCXX_NOEXCEPT_IF(noexcept(_Alloc(__other))) + : _Alloc(__other) + { } + }; + _GLIBCXX_END_NAMESPACE_VERSION } // namespace std ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Default std::vector<bool> default and move constructor 2017-05-28 20:29 ` François Dumont @ 2017-05-29 20:57 ` François Dumont 2017-05-31 10:37 ` Jonathan Wakely 2017-05-31 11:13 ` Jonathan Wakely 1 sibling, 1 reply; 19+ messages in thread From: François Dumont @ 2017-05-29 20:57 UTC (permalink / raw) To: Jonathan Wakely; +Cc: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 3201 bytes --] Hi It wasn't such a big deal to restore value-init of the allocator. So here is the updated patch. I used: _Bvector_impl() _GLIBCXX_NOEXCEPT_IF( noexcept(_Bit_alloc_type()) ) rather than using is_nothrow_default_constructible. Any advantage in one approach or the other ? I'll complete testing and add a test on this value-initialization before commit if you agree. Tests still running but I'm pretty sure it will work the same. François On 28/05/2017 22:13, François Dumont wrote: > On 27/05/2017 13:14, Jonathan Wakely wrote: >> On 26/05/17 23:13 +0200, François Dumont wrote: >>> On 25/05/2017 18:28, Jonathan Wakely wrote: >>>> On 15/05/17 19:57 +0200, François Dumont wrote: >>>>> Hi >>>>> >>>>> Following what I have started on RbTree here is a patch to >>>>> default implementation of default and move constructors on >>>>> std::vector<bool>. >>>>> >>>>> As in _Rb_tree_impl the default allocator is not value >>>>> initialized anymore. We could add a small helper type arround the >>>>> allocator to do this value initialization per default. Should I do >>>>> so ? >>>> >>>> It's required to be value-initialized, so if your patch changes that >>>> then it's a problem. >>>> >>>> Did we decide it's OK to do that for RB-trees? Did we actually discuss >>>> that part of the r243379 changes? >>> >>> I remember a message pointing this issue but after the commit AFAIR. >>> I thought it was from Tim but I can't find it on the archive. >>> >>> What is the rational of this requirement ? I started working on a >>> type to do the allocator value initialization if there is no default >>> constructor but it seems quite complicated to do so. It is quite sad >>> that we can't fully benefit from this nice C++11 feature just >>> because of this requirement. If there is any initialization needed >>> it doesn't sound complicated to provide a default constructor. >> >> The standard says that the default constructor is: >> >> vector() : vector(Allocator()) { } >> >> That value-initializes the allocator. If the allocator type behaves >> differently for value-init and default-init (e.g. it has data members >> that are left uninitialized by default-init) then the difference >> matters. If you change the code so it only does default-init of the >> allocator then you will introduce an observable difference. >> >> I don't see any requirement that a DefaultConstructible allocator >> cannot leave members uninitialized, so that means the standard >> requires default construction of vector<bool> to value-init the >> allocator. Not default-init. > > Sure but like freedom which stop where start others' freedom so does > those requirements :-). Because the Standard says that an allocator > will be value-init when there is no default-init it makes usage of the > C++11 default constructor more complicated. > > But as it is unavoidable here is a type I tried to work on to keep > current implementations as long as we inherit from > __alloc_value_initializer. > > I don't like it myself but I propose just in case you are interested. > > Otherwise I am also going to rework my patch to keep this initialization. > > François > [-- Attachment #2: bvector.patch --] [-- Type: text/x-patch, Size: 9631 bytes --] diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h index 37e000a..6509ac5 100644 --- a/libstdc++-v3/include/bits/stl_bvector.h +++ b/libstdc++-v3/include/bits/stl_bvector.h @@ -388,10 +388,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return __x + __n; } inline void - __fill_bvector(_Bit_iterator __first, _Bit_iterator __last, bool __x) + __fill_bvector(_Bit_type * __v, + unsigned int __first, unsigned int __last, bool __x) { - for (; __first != __last; ++__first) - *__first = __x; + const _Bit_type __fmask = ~0ul << __first; + const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last); + const _Bit_type __mask = __fmask & __lmask; + + if (__x) + *__v |= __mask; + else + *__v &= ~__mask; } inline void @@ -399,12 +406,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { if (__first._M_p != __last._M_p) { - std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0); - __fill_bvector(__first, _Bit_iterator(__first._M_p + 1, 0), __x); - __fill_bvector(_Bit_iterator(__last._M_p, 0), __last, __x); + _Bit_type *__first_p = __first._M_p; + if (__first._M_offset != 0) + __fill_bvector(__first_p++, __first._M_offset, _S_word_bit, __x); + + __builtin_memset(__first_p, __x ? ~0 : 0, + (__last._M_p - __first_p) * sizeof(_Bit_type)); + + if (__last._M_offset != 0) + __fill_bvector(__last._M_p, 0, __last._M_offset, __x); } else - __fill_bvector(__first, __last, __x); + __fill_bvector(__first._M_p, __first._M_offset, __last._M_offset, __x); } template<typename _Alloc> @@ -416,33 +429,61 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Bit_alloc_traits; typedef typename _Bit_alloc_traits::pointer _Bit_pointer; - struct _Bvector_impl - : public _Bit_alloc_type + struct _Bvector_impl_data { _Bit_iterator _M_start; _Bit_iterator _M_finish; _Bit_pointer _M_end_of_storage; - _Bvector_impl() - : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage() + _Bvector_impl_data() _GLIBCXX_NOEXCEPT + : _M_start(), _M_finish(), _M_end_of_storage() + { } + +#if __cplusplus >= 201103L + _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) + { __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; + __x._M_reset(); + } +#endif + + void + _M_reset() _GLIBCXX_NOEXCEPT + { + _M_start = _M_finish = _Bit_iterator(); + _M_end_of_storage = _Bit_pointer(); + } + }; + + struct _Bvector_impl + : public _Bit_alloc_type, public _Bvector_impl_data + { + public: + _Bvector_impl() _GLIBCXX_NOEXCEPT_IF( noexcept(_Bit_alloc_type()) ) + : _Bit_alloc_type() { } _Bvector_impl(const _Bit_alloc_type& __a) - : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage() + : _Bit_alloc_type(__a) { } #if __cplusplus >= 201103L - _Bvector_impl(_Bit_alloc_type&& __a) - : _Bit_alloc_type(std::move(__a)), _M_start(), _M_finish(), - _M_end_of_storage() - { } + _Bvector_impl(_Bvector_impl&&) = default; #endif _Bit_type* _M_end_addr() const _GLIBCXX_NOEXCEPT { - if (_M_end_of_storage) - return std::__addressof(_M_end_of_storage[-1]) + 1; + if (this->_M_end_of_storage) + return std::__addressof(this->_M_end_of_storage[-1]) + 1; return 0; } }; @@ -462,23 +503,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER get_allocator() const _GLIBCXX_NOEXCEPT { return allocator_type(_M_get_Bit_allocator()); } - _Bvector_base() - : _M_impl() { } +#if __cplusplus >= 201103L + _Bvector_base() = default; +#else + _Bvector_base() { } +#endif _Bvector_base(const allocator_type& __a) : _M_impl(__a) { } #if __cplusplus >= 201103L - _Bvector_base(_Bvector_base&& __x) noexcept - : _M_impl(std::move(__x._M_get_Bit_allocator())) - { - this->_M_impl._M_start = __x._M_impl._M_start; - this->_M_impl._M_finish = __x._M_impl._M_finish; - this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; - __x._M_impl._M_start = _Bit_iterator(); - __x._M_impl._M_finish = _Bit_iterator(); - __x._M_impl._M_end_of_storage = nullptr; - } + _Bvector_base(_Bvector_base&&) = default; #endif ~_Bvector_base() @@ -500,11 +535,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Bit_alloc_traits::deallocate(_M_impl, _M_impl._M_end_of_storage - __n, __n); - _M_impl._M_start = _M_impl._M_finish = _Bit_iterator(); - _M_impl._M_end_of_storage = _Bit_pointer(); + _M_impl._M_reset(); } } +#if __cplusplus >= 201103L + void + _M_move_data(_Bvector_base&& __x) noexcept + { _M_impl._M_move_data(std::move(__x._M_impl)); } +#endif + static size_t _S_nword(size_t __n) { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); } @@ -564,7 +604,8 @@ template<typename _Alloc> typedef std::reverse_iterator<iterator> reverse_iterator; typedef _Alloc allocator_type; - allocator_type get_allocator() const + allocator_type + get_allocator() const { return _Base::get_allocator(); } protected: @@ -574,11 +615,11 @@ template<typename _Alloc> using _Base::_M_get_Bit_allocator; public: - vector() #if __cplusplus >= 201103L - noexcept(is_nothrow_default_constructible<allocator_type>::value) + vector() = default; +#else + vector() { } #endif - : _Base() { } explicit vector(const allocator_type& __a) @@ -592,23 +633,16 @@ template<typename _Alloc> vector(size_type __n, const bool& __value, const allocator_type& __a = allocator_type()) - : _Base(__a) - { - _M_initialize(__n); - std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_addr(), - __value ? ~0 : 0); - } #else explicit vector(size_type __n, const bool& __value = bool(), const allocator_type& __a = allocator_type()) +#endif : _Base(__a) { _M_initialize(__n); - std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_addr(), - __value ? ~0 : 0); + _M_initialize_value(__value); } -#endif vector(const vector& __x) : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator())) @@ -618,22 +652,14 @@ template<typename _Alloc> } #if __cplusplus >= 201103L - vector(vector&& __x) noexcept - : _Base(std::move(__x)) { } + vector(vector&&) = default; vector(vector&& __x, const allocator_type& __a) noexcept(_Bit_alloc_traits::_S_always_equal()) : _Base(__a) { if (__x.get_allocator() == __a) - { - this->_M_impl._M_start = __x._M_impl._M_start; - this->_M_impl._M_finish = __x._M_impl._M_finish; - this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; - __x._M_impl._M_start = _Bit_iterator(); - __x._M_impl._M_finish = _Bit_iterator(); - __x._M_impl._M_end_of_storage = nullptr; - } + this->_M_move_data(std::move(__x)); else { _M_initialize(__x.size()); @@ -716,12 +742,7 @@ template<typename _Alloc> || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator()) { this->_M_deallocate(); - this->_M_impl._M_start = __x._M_impl._M_start; - this->_M_impl._M_finish = __x._M_impl._M_finish; - this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; - __x._M_impl._M_start = _Bit_iterator(); - __x._M_impl._M_finish = _Bit_iterator(); - __x._M_impl._M_end_of_storage = nullptr; + this->_M_move_data(std::move(__x)); std::__alloc_on_move(_M_get_Bit_allocator(), __x._M_get_Bit_allocator()); } @@ -760,7 +781,7 @@ template<typename _Alloc> typename = std::_RequireInputIter<_InputIterator>> void assign(_InputIterator __first, _InputIterator __last) - { _M_assign_dispatch(__first, __last, __false_type()); } + { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } #else template<typename _InputIterator> void @@ -774,7 +795,7 @@ template<typename _Alloc> #if __cplusplus >= 201103L void assign(initializer_list<bool> __l) - { this->assign(__l.begin(), __l.end()); } + { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); } #endif iterator @@ -1096,6 +1117,14 @@ template<typename _Alloc> } void + _M_initialize_value(bool __x) + { + __builtin_memset(this->_M_impl._M_start._M_p, __x ? ~0 : 0, + (this->_M_impl._M_end_addr() - this->_M_impl._M_start._M_p) + * sizeof(_Bit_type)); + } + + void _M_reallocate(size_type __n); #if __cplusplus >= 201103L @@ -1112,8 +1141,7 @@ template<typename _Alloc> _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) { _M_initialize(static_cast<size_type>(__n)); - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_addr(), __x ? ~0 : 0); + _M_initialize_value(__x); } template<typename _InputIterator> @@ -1160,15 +1188,13 @@ template<typename _Alloc> { if (__n > size()) { - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_addr(), __x ? ~0 : 0); + _M_initialize_value(__x); insert(end(), __n - size(), __x); } else { _M_erase_at_end(begin() + __n); - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_addr(), __x ? ~0 : 0); + _M_initialize_value(__x); } } ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Default std::vector<bool> default and move constructor 2017-05-29 20:57 ` François Dumont @ 2017-05-31 10:37 ` Jonathan Wakely 2017-05-31 20:34 ` François Dumont 0 siblings, 1 reply; 19+ messages in thread From: Jonathan Wakely @ 2017-05-31 10:37 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches On 29/05/17 22:55 +0200, François Dumont wrote: >Hi > > It wasn't such a big deal to restore value-init of the allocator. >So here is the updated patch. > > I used: > _Bvector_impl() _GLIBCXX_NOEXCEPT_IF( noexcept(_Bit_alloc_type()) ) > > rather than using is_nothrow_default_constructible. Any advantage >in one approach or the other ? Well in general the is_nothrow_default_constructible trait also tells you if the type is default-constructible at all, but the form above won't compile if it isn't default-constructible. In this specific case it doesn't matter, because that constructor won't compile anyway if the allocator isn't default-constructible. > I'll complete testing and add a test on this value-initialization >before commit if you agree. Thanks. > Tests still running but I'm pretty sure it will work the same. Yes, it should do. I'm going to commit a fix for PR80893 in vector<bool>::_M_initialize but I don't think it will conflict with your changes. ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Default std::vector<bool> default and move constructor 2017-05-31 10:37 ` Jonathan Wakely @ 2017-05-31 20:34 ` François Dumont 2017-06-01 13:34 ` Jonathan Wakely 0 siblings, 1 reply; 19+ messages in thread From: François Dumont @ 2017-05-31 20:34 UTC (permalink / raw) To: Jonathan Wakely; +Cc: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 2321 bytes --] On 31/05/2017 12:34, Jonathan Wakely wrote: > > Well in general the is_nothrow_default_constructible trait also tells > you if the type is default-constructible at all, but the form above > won't compile if it isn't default-constructible. In this specific case > it doesn't matter, because that constructor won't compile anyway if > the allocator isn't default-constructible. > Thanks for explanation, for the moment I kept the noexcept calls. You'll tell me if it is fine in this new proposal. >> I'll complete testing and add a test on this value-initialization >> before commit if you agree. So here is the new proposal with the additional test. Unless I made a mistake it revealed that restoring explicit call to _Bit_alloc_type() in default constructor was not enough. G++ doesn't transform it into a value-init if needed. I don't know if it is a compiler bug but I had to do just like presented in the Standard to achieve the expected behavior. This value-init is specific to post-C++11 right ? Maybe I could remove the useless explicit call to _Bit_alloc_type() in pre-C++11 mode ? Now I wonder if I really introduced a regression in rb_tree... Tested under Linux x86_64. * include/bits/stl_bvector.h (__fill_bvector(_Bit_type*, unsigned int, unsigned int, bool)): Change signature. (std::fill(_Bit_iterator, _Bit_iterator, bool)): Adapt. (_Bvector_impl_data): New. (_Bvector_impl): Inherits from latter. (_Bvector_impl(_Bit_alloc_type&&)): Delete. (_Bvector_impl(_Bvector_impl&&)): New, default. (_Bvector_base()): Default. (_Bvector_base(_Bvector_base&&)): Default. (_Bvector_base::_M_move_data(_Bvector_base&&)): New. (vector(vector&&, const allocator_type&)): Use latter. (vector<bool>::operator=(vector&&)): Likewise. (vector<bool>::vector()): Default. (vector<bool>::assign(_InputIterator, _InputIterator)): Use _M_assign_aux. (vector<bool>::assign(initializer_list<bool>)): Likewise. (vector<bool>::_M_initialize_value(bool)): New. (vector<bool>(size_type, const bool&, const allocator_type&)): Use latter. (vector<bool>::_M_initialize_dispatch(_Integer, _Integer, __true_type)): Likewise. (vector<bool>::_M_fill_assign(size_t, bool)): Likewise. Ok to commit ? François [-- Attachment #2: bvector.patch --] [-- Type: text/x-patch, Size: 13128 bytes --] diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h index 78195c1..c441957 100644 --- a/libstdc++-v3/include/bits/stl_bvector.h +++ b/libstdc++-v3/include/bits/stl_bvector.h @@ -388,10 +388,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return __x + __n; } inline void - __fill_bvector(_Bit_iterator __first, _Bit_iterator __last, bool __x) + __fill_bvector(_Bit_type * __v, + unsigned int __first, unsigned int __last, bool __x) { - for (; __first != __last; ++__first) - *__first = __x; + const _Bit_type __fmask = ~0ul << __first; + const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last); + const _Bit_type __mask = __fmask & __lmask; + + if (__x) + *__v |= __mask; + else + *__v &= ~__mask; } inline void @@ -399,12 +406,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { if (__first._M_p != __last._M_p) { - std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0); - __fill_bvector(__first, _Bit_iterator(__first._M_p + 1, 0), __x); - __fill_bvector(_Bit_iterator(__last._M_p, 0), __last, __x); + _Bit_type *__first_p = __first._M_p; + if (__first._M_offset != 0) + __fill_bvector(__first_p++, __first._M_offset, _S_word_bit, __x); + + __builtin_memset(__first_p, __x ? ~0 : 0, + (__last._M_p - __first_p) * sizeof(_Bit_type)); + + if (__last._M_offset != 0) + __fill_bvector(__last._M_p, 0, __last._M_offset, __x); } else - __fill_bvector(__first, __last, __x); + __fill_bvector(__first._M_p, __first._M_offset, __last._M_offset, __x); } template<typename _Alloc> @@ -416,33 +429,70 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Bit_alloc_traits; typedef typename _Bit_alloc_traits::pointer _Bit_pointer; - struct _Bvector_impl - : public _Bit_alloc_type + struct _Bvector_impl_data { _Bit_iterator _M_start; _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(_Bvector_impl_data&& __x) noexcept + : _M_start(__x._M_start), _M_finish(__x._M_finish) + , _M_end_of_storage(__x._M_end_of_storage) + { __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; + __x._M_reset(); + } +#endif + + void + _M_reset() _GLIBCXX_NOEXCEPT + { + _M_start = _M_finish = _Bit_iterator(); + _M_end_of_storage = _Bit_pointer(); + } + }; + + struct _Bvector_impl + : public _Bit_alloc_type, public _Bvector_impl_data + { + public: +#if __cplusplus >= 201103L + _Bvector_impl() + noexcept( noexcept(_Bit_alloc_type()) + && noexcept(_Bvector_impl(declval<const _Bit_alloc_type&>())) ) + : _Bvector_impl(_Bit_alloc_type()) + { } +#else _Bvector_impl() - : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage() + : _Bit_alloc_type() { } +#endif _Bvector_impl(const _Bit_alloc_type& __a) - : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage() + _GLIBCXX_NOEXCEPT_IF( noexcept(_Bit_alloc_type(__a)) ) + : _Bit_alloc_type(__a) { } #if __cplusplus >= 201103L - _Bvector_impl(_Bit_alloc_type&& __a) - : _Bit_alloc_type(std::move(__a)), _M_start(), _M_finish(), - _M_end_of_storage() - { } + _Bvector_impl(_Bvector_impl&&) = default; #endif _Bit_type* _M_end_addr() const _GLIBCXX_NOEXCEPT { - if (_M_end_of_storage) - return std::__addressof(_M_end_of_storage[-1]) + 1; + if (this->_M_end_of_storage) + return std::__addressof(this->_M_end_of_storage[-1]) + 1; return 0; } }; @@ -452,33 +502,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Bit_alloc_type& _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT - { return *static_cast<_Bit_alloc_type*>(&this->_M_impl); } + { return this->_M_impl; } const _Bit_alloc_type& _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT - { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); } + { return this->_M_impl; } allocator_type get_allocator() const _GLIBCXX_NOEXCEPT { return allocator_type(_M_get_Bit_allocator()); } - _Bvector_base() - : _M_impl() { } +#if __cplusplus >= 201103L + _Bvector_base() = default; +#else + _Bvector_base() { } +#endif _Bvector_base(const allocator_type& __a) : _M_impl(__a) { } #if __cplusplus >= 201103L - _Bvector_base(_Bvector_base&& __x) noexcept - : _M_impl(std::move(__x._M_get_Bit_allocator())) - { - this->_M_impl._M_start = __x._M_impl._M_start; - this->_M_impl._M_finish = __x._M_impl._M_finish; - this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; - __x._M_impl._M_start = _Bit_iterator(); - __x._M_impl._M_finish = _Bit_iterator(); - __x._M_impl._M_end_of_storage = nullptr; - } + _Bvector_base(_Bvector_base&&) = default; #endif ~_Bvector_base() @@ -500,11 +544,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Bit_alloc_traits::deallocate(_M_impl, _M_impl._M_end_of_storage - __n, __n); - _M_impl._M_start = _M_impl._M_finish = _Bit_iterator(); - _M_impl._M_end_of_storage = _Bit_pointer(); + _M_impl._M_reset(); } } +#if __cplusplus >= 201103L + void + _M_move_data(_Bvector_base&& __x) noexcept + { _M_impl._M_move_data(std::move(__x._M_impl)); } +#endif + static size_t _S_nword(size_t __n) { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); } @@ -564,7 +613,8 @@ template<typename _Alloc> typedef std::reverse_iterator<iterator> reverse_iterator; typedef _Alloc allocator_type; - allocator_type get_allocator() const + allocator_type + get_allocator() const { return _Base::get_allocator(); } protected: @@ -574,11 +624,11 @@ template<typename _Alloc> using _Base::_M_get_Bit_allocator; public: - vector() #if __cplusplus >= 201103L - noexcept(is_nothrow_default_constructible<allocator_type>::value) + vector() = default; +#else + vector() { } #endif - : _Base() { } explicit vector(const allocator_type& __a) @@ -592,23 +642,16 @@ template<typename _Alloc> vector(size_type __n, const bool& __value, const allocator_type& __a = allocator_type()) - : _Base(__a) - { - _M_initialize(__n); - std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_addr(), - __value ? ~0 : 0); - } #else explicit vector(size_type __n, const bool& __value = bool(), const allocator_type& __a = allocator_type()) +#endif : _Base(__a) { _M_initialize(__n); - std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_addr(), - __value ? ~0 : 0); + _M_initialize_value(__value); } -#endif vector(const vector& __x) : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator())) @@ -618,22 +661,14 @@ template<typename _Alloc> } #if __cplusplus >= 201103L - vector(vector&& __x) noexcept - : _Base(std::move(__x)) { } + vector(vector&&) = default; vector(vector&& __x, const allocator_type& __a) noexcept(_Bit_alloc_traits::_S_always_equal()) : _Base(__a) { if (__x.get_allocator() == __a) - { - this->_M_impl._M_start = __x._M_impl._M_start; - this->_M_impl._M_finish = __x._M_impl._M_finish; - this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; - __x._M_impl._M_start = _Bit_iterator(); - __x._M_impl._M_finish = _Bit_iterator(); - __x._M_impl._M_end_of_storage = nullptr; - } + this->_M_move_data(std::move(__x)); else { _M_initialize(__x.size()); @@ -716,12 +751,7 @@ template<typename _Alloc> || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator()) { this->_M_deallocate(); - this->_M_impl._M_start = __x._M_impl._M_start; - this->_M_impl._M_finish = __x._M_impl._M_finish; - this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; - __x._M_impl._M_start = _Bit_iterator(); - __x._M_impl._M_finish = _Bit_iterator(); - __x._M_impl._M_end_of_storage = nullptr; + this->_M_move_data(std::move(__x)); std::__alloc_on_move(_M_get_Bit_allocator(), __x._M_get_Bit_allocator()); } @@ -760,7 +790,7 @@ template<typename _Alloc> typename = std::_RequireInputIter<_InputIterator>> void assign(_InputIterator __first, _InputIterator __last) - { _M_assign_dispatch(__first, __last, __false_type()); } + { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } #else template<typename _InputIterator> void @@ -774,7 +804,7 @@ template<typename _Alloc> #if __cplusplus >= 201103L void assign(initializer_list<bool> __l) - { this->assign(__l.begin(), __l.end()); } + { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); } #endif iterator @@ -1101,6 +1131,15 @@ template<typename _Alloc> this->_M_impl._M_start = iterator(0, 0); } this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n); + + } + + void + _M_initialize_value(bool __x) + { + __builtin_memset(this->_M_impl._M_start._M_p, __x ? ~0 : 0, + (this->_M_impl._M_end_addr() - this->_M_impl._M_start._M_p) + * sizeof(_Bit_type)); } void @@ -1120,8 +1159,7 @@ template<typename _Alloc> _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) { _M_initialize(static_cast<size_type>(__n)); - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_addr(), __x ? ~0 : 0); + _M_initialize_value(__x); } template<typename _InputIterator> @@ -1168,15 +1206,13 @@ template<typename _Alloc> { if (__n > size()) { - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_addr(), __x ? ~0 : 0); + _M_initialize_value(__x); insert(end(), __n - size(), __x); } else { _M_erase_at_end(begin() + __n); - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_addr(), __x ? ~0 : 0); + _M_initialize_value(__x); } } diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/allocator/default_init.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/allocator/default_init.cc new file mode 100644 index 0000000..aee9b508 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/allocator/default_init.cc @@ -0,0 +1,44 @@ +// Copyright (C) 2017 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-do run { target c++11 } } + +#include <vector> +#include <testsuite_hooks.h> +#include <testsuite_allocator.h> + +using T = bool; + +using __gnu_test::default_init_allocator; + +void test01() +{ + typedef default_init_allocator<T> alloc_type; + typedef std::vector<T, alloc_type> test_type; + + test_type v1; + v1.push_back(T()); + + VERIFY( !v1.empty() ); + VERIFY( !v1.get_allocator().state ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/util/testsuite_allocator.h b/libstdc++-v3/testsuite/util/testsuite_allocator.h index 56c2708..233ea0b 100644 --- a/libstdc++-v3/testsuite/util/testsuite_allocator.h +++ b/libstdc++-v3/testsuite/util/testsuite_allocator.h @@ -508,6 +508,38 @@ namespace __gnu_test bool operator!=(const SimpleAllocator<T>&, const SimpleAllocator<U>&) { return false; } + template<typename T> + struct default_init_allocator + { + using value_type = T; + + default_init_allocator() = default; + + template<typename U> + default_init_allocator(const default_init_allocator<U>& a) + : state(a.state) + { } + + T* + allocate(std::size_t n) + { return std::allocator<T>().allocate(n); } + + void + deallocate(T* p, std::size_t n) + { std::allocator<T>().deallocate(p, n); } + + int state; + }; + + template<typename T, typename U> + bool operator==(const default_init_allocator<T>& t, + const default_init_allocator<U>& u) + { return t.state == u.state; } + + template<typename T, typename U> + bool operator!=(const default_init_allocator<T>& t, + const default_init_allocator<U>& u) + { return !(t == u); } #endif template<typename Tp> ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Default std::vector<bool> default and move constructor 2017-05-31 20:34 ` François Dumont @ 2017-06-01 13:34 ` Jonathan Wakely 2017-06-01 20:49 ` François Dumont 2017-06-13 20:36 ` François Dumont 0 siblings, 2 replies; 19+ messages in thread From: Jonathan Wakely @ 2017-06-01 13:34 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches On 31/05/17 22:28 +0200, François Dumont wrote: >Unless I made a mistake it revealed that restoring explicit call to >_Bit_alloc_type() in default constructor was not enough. G++ doesn't >transform it into a value-init if needed. I don't know if it is a >compiler bug but I had to do just like presented in the Standard to >achieve the expected behavior. That really shouldn't be necessary (see blow). >This value-init is specific to post-C++11 right ? Maybe I could remove >the useless explicit call to _Bit_alloc_type() in pre-C++11 mode ? No, because C++03 also requires the allocator to be value-initialized. >Now I wonder if I really introduced a regression in rb_tree... Yes, I think you did. Could you try to verify that using the new default_init_allocator? >+ struct _Bvector_impl >+ : public _Bit_alloc_type, public _Bvector_impl_data >+ { >+ public: >+#if __cplusplus >= 201103L >+ _Bvector_impl() >+ noexcept( noexcept(_Bit_alloc_type()) >+ && noexcept(_Bvector_impl(declval<const _Bit_alloc_type&>())) ) This second condition is not needed, because that constructor should be noexcept (see below). >+ : _Bvector_impl(_Bit_alloc_type()) This should not be necessary... >+ { } >+#else > _Bvector_impl() >- : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage() >+ : _Bit_alloc_type() > { } >+#endif I would expect the constructor to look like this: _Bvector_impl() _GLIBCXX_NOEXCEPT_IF( noexcept(_Bit_alloc_type()) ) : _Bit_alloc_type() { } What happens when you do that? > _Bvector_impl(const _Bit_alloc_type& __a) >- : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage() >+ _GLIBCXX_NOEXCEPT_IF( noexcept(_Bit_alloc_type(__a)) ) Copying the allocator is not allowed to throw. You can use simply _GLIBCXX_NOEXCEPT here. >+void test01() >+{ >+ typedef default_init_allocator<T> alloc_type; >+ typedef std::vector<T, alloc_type> test_type; >+ >+ test_type v1; >+ v1.push_back(T()); >+ >+ VERIFY( !v1.empty() ); >+ VERIFY( !v1.get_allocator().state ); This is unlikely to ever fail, because the stack is probably full of zeros anyway. Did you confirm whether the test fails without your fixes to value-initialize the allocator? One possible way to make it fail would be to construct the vector<bool> using placement new, into a buffer filled with non-zero values. (Valgrind or a sanitizer should also tell us, but we can't rely on them in the testsuite). ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Default std::vector<bool> default and move constructor 2017-06-01 13:34 ` Jonathan Wakely @ 2017-06-01 20:49 ` François Dumont 2017-06-02 10:27 ` Jonathan Wakely 2017-06-13 20:36 ` François Dumont 1 sibling, 1 reply; 19+ messages in thread From: François Dumont @ 2017-06-01 20:49 UTC (permalink / raw) To: Jonathan Wakely; +Cc: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 3631 bytes --] On 01/06/2017 15:34, Jonathan Wakely wrote: > On 31/05/17 22:28 +0200, François Dumont wrote: >> Unless I made a mistake it revealed that restoring explicit call to >> _Bit_alloc_type() in default constructor was not enough. G++ doesn't >> transform it into a value-init if needed. I don't know if it is a >> compiler bug but I had to do just like presented in the Standard to >> achieve the expected behavior. > > That really shouldn't be necessary (see blow). > >> This value-init is specific to post-C++11 right ? Maybe I could >> remove the useless explicit call to _Bit_alloc_type() in pre-C++11 >> mode ? > > No, because C++03 also requires the allocator to be value-initialized. Ok so I'll try to make the test C++03 compatible. > >> Now I wonder if I really introduced a regression in rb_tree... > > Yes, I think you did. Could you try to verify that using the new > default_init_allocator? I did and for the moment I experiment the same result with rb_tree than the one I am having with std::vector<bool>, strange. I plan to add this test to all containers. > > >> + struct _Bvector_impl >> + : public _Bit_alloc_type, public _Bvector_impl_data >> + { >> + public: >> +#if __cplusplus >= 201103L >> + _Bvector_impl() >> + noexcept( noexcept(_Bit_alloc_type()) >> + && noexcept(_Bvector_impl(declval<const >> _Bit_alloc_type&>())) ) > > This second condition is not needed, because that constructor should > be noexcept (see below). > >> + : _Bvector_impl(_Bit_alloc_type()) > > This should not be necessary... > >> + { } >> +#else >> _Bvector_impl() >> - : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage() >> + : _Bit_alloc_type() >> { } >> +#endif > > I would expect the constructor to look like this: > > _Bvector_impl() > _GLIBCXX_NOEXCEPT_IF( noexcept(_Bit_alloc_type()) ) > : _Bit_alloc_type() > { } > > What happens when you do that? This is what I tried first and test was then failing. It surprised me too. > > >> _Bvector_impl(const _Bit_alloc_type& __a) >> - : _Bit_alloc_type(__a), _M_start(), _M_finish(), >> _M_end_of_storage() >> + _GLIBCXX_NOEXCEPT_IF( noexcept(_Bit_alloc_type(__a)) ) > > Copying the allocator is not allowed to throw. You can use simply > _GLIBCXX_NOEXCEPT here. > > >> +void test01() >> +{ >> + typedef default_init_allocator<T> alloc_type; >> + typedef std::vector<T, alloc_type> test_type; >> + >> + test_type v1; >> + v1.push_back(T()); >> + >> + VERIFY( !v1.empty() ); >> + VERIFY( !v1.get_allocator().state ); > > This is unlikely to ever fail, because the stack is probably full of > zeros anyway. Did you confirm whether the test fails without your > fixes to value-initialize the allocator? Yes, the test is failing as soon as I use the default constructor just calling the allocator default constructor in its initialization list or when I default this implementation. > > One possible way to make it fail would be to construct the > vector<bool> using placement new, into a buffer filled with non-zero > values. (Valgrind or a sanitizer should also tell us, but we can't > rely on them in the testsuite). > This is what I have implemented in this new proposal also considering your other remarks. For the moment if the test fail there is a memory leak but I prefer to keep implementation simple. I also start runing the test on the normal std::vector implementation and I never managed to make the test fail. Even when I default all default constructor implementations ! I started rebuilding everything. François [-- Attachment #2: bvector.patch --] [-- Type: text/x-patch, Size: 13256 bytes --] diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h index 78195c1..5fb342f 100644 --- a/libstdc++-v3/include/bits/stl_bvector.h +++ b/libstdc++-v3/include/bits/stl_bvector.h @@ -388,10 +388,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return __x + __n; } inline void - __fill_bvector(_Bit_iterator __first, _Bit_iterator __last, bool __x) + __fill_bvector(_Bit_type * __v, + unsigned int __first, unsigned int __last, bool __x) { - for (; __first != __last; ++__first) - *__first = __x; + const _Bit_type __fmask = ~0ul << __first; + const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last); + const _Bit_type __mask = __fmask & __lmask; + + if (__x) + *__v |= __mask; + else + *__v &= ~__mask; } inline void @@ -399,12 +406,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { if (__first._M_p != __last._M_p) { - std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0); - __fill_bvector(__first, _Bit_iterator(__first._M_p + 1, 0), __x); - __fill_bvector(_Bit_iterator(__last._M_p, 0), __last, __x); + _Bit_type *__first_p = __first._M_p; + if (__first._M_offset != 0) + __fill_bvector(__first_p++, __first._M_offset, _S_word_bit, __x); + + __builtin_memset(__first_p, __x ? ~0 : 0, + (__last._M_p - __first_p) * sizeof(_Bit_type)); + + if (__last._M_offset != 0) + __fill_bvector(__last._M_p, 0, __last._M_offset, __x); } else - __fill_bvector(__first, __last, __x); + __fill_bvector(__first._M_p, __first._M_offset, __last._M_offset, __x); } template<typename _Alloc> @@ -416,33 +429,68 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Bit_alloc_traits; typedef typename _Bit_alloc_traits::pointer _Bit_pointer; - struct _Bvector_impl - : public _Bit_alloc_type + struct _Bvector_impl_data { _Bit_iterator _M_start; _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(_Bvector_impl_data&& __x) noexcept + : _M_start(__x._M_start), _M_finish(__x._M_finish) + , _M_end_of_storage(__x._M_end_of_storage) + { __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; + __x._M_reset(); + } +#endif + + void + _M_reset() _GLIBCXX_NOEXCEPT + { + _M_start = _M_finish = _Bit_iterator(); + _M_end_of_storage = _Bit_pointer(); + } + }; + + struct _Bvector_impl + : public _Bit_alloc_type, public _Bvector_impl_data + { + public: +#if __cplusplus >= 201103L + _Bvector_impl() + noexcept( noexcept(_Bit_alloc_type()) ) + : _Bvector_impl(_Bit_alloc_type()) + { } +#else _Bvector_impl() - : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage() + : _Bit_alloc_type() { } +#endif - _Bvector_impl(const _Bit_alloc_type& __a) - : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage() + _Bvector_impl(const _Bit_alloc_type& __a) _GLIBCXX_NOEXCEPT + : _Bit_alloc_type(__a) { } #if __cplusplus >= 201103L - _Bvector_impl(_Bit_alloc_type&& __a) - : _Bit_alloc_type(std::move(__a)), _M_start(), _M_finish(), - _M_end_of_storage() - { } + _Bvector_impl(_Bvector_impl&&) = default; #endif _Bit_type* _M_end_addr() const _GLIBCXX_NOEXCEPT { - if (_M_end_of_storage) - return std::__addressof(_M_end_of_storage[-1]) + 1; + if (this->_M_end_of_storage) + return std::__addressof(this->_M_end_of_storage[-1]) + 1; return 0; } }; @@ -452,33 +500,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Bit_alloc_type& _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT - { return *static_cast<_Bit_alloc_type*>(&this->_M_impl); } + { return this->_M_impl; } const _Bit_alloc_type& _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT - { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); } + { return this->_M_impl; } allocator_type get_allocator() const _GLIBCXX_NOEXCEPT { return allocator_type(_M_get_Bit_allocator()); } - _Bvector_base() - : _M_impl() { } +#if __cplusplus >= 201103L + _Bvector_base() = default; +#else + _Bvector_base() { } +#endif _Bvector_base(const allocator_type& __a) : _M_impl(__a) { } #if __cplusplus >= 201103L - _Bvector_base(_Bvector_base&& __x) noexcept - : _M_impl(std::move(__x._M_get_Bit_allocator())) - { - this->_M_impl._M_start = __x._M_impl._M_start; - this->_M_impl._M_finish = __x._M_impl._M_finish; - this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; - __x._M_impl._M_start = _Bit_iterator(); - __x._M_impl._M_finish = _Bit_iterator(); - __x._M_impl._M_end_of_storage = nullptr; - } + _Bvector_base(_Bvector_base&&) = default; #endif ~_Bvector_base() @@ -500,11 +542,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Bit_alloc_traits::deallocate(_M_impl, _M_impl._M_end_of_storage - __n, __n); - _M_impl._M_start = _M_impl._M_finish = _Bit_iterator(); - _M_impl._M_end_of_storage = _Bit_pointer(); + _M_impl._M_reset(); } } +#if __cplusplus >= 201103L + void + _M_move_data(_Bvector_base&& __x) noexcept + { _M_impl._M_move_data(std::move(__x._M_impl)); } +#endif + static size_t _S_nword(size_t __n) { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); } @@ -564,7 +611,8 @@ template<typename _Alloc> typedef std::reverse_iterator<iterator> reverse_iterator; typedef _Alloc allocator_type; - allocator_type get_allocator() const + allocator_type + get_allocator() const { return _Base::get_allocator(); } protected: @@ -574,11 +622,11 @@ template<typename _Alloc> using _Base::_M_get_Bit_allocator; public: - vector() #if __cplusplus >= 201103L - noexcept(is_nothrow_default_constructible<allocator_type>::value) + vector() = default; +#else + vector() { } #endif - : _Base() { } explicit vector(const allocator_type& __a) @@ -592,23 +640,16 @@ template<typename _Alloc> vector(size_type __n, const bool& __value, const allocator_type& __a = allocator_type()) - : _Base(__a) - { - _M_initialize(__n); - std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_addr(), - __value ? ~0 : 0); - } #else explicit vector(size_type __n, const bool& __value = bool(), const allocator_type& __a = allocator_type()) +#endif : _Base(__a) { _M_initialize(__n); - std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_addr(), - __value ? ~0 : 0); + _M_initialize_value(__value); } -#endif vector(const vector& __x) : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator())) @@ -618,22 +659,14 @@ template<typename _Alloc> } #if __cplusplus >= 201103L - vector(vector&& __x) noexcept - : _Base(std::move(__x)) { } + vector(vector&&) = default; vector(vector&& __x, const allocator_type& __a) noexcept(_Bit_alloc_traits::_S_always_equal()) : _Base(__a) { if (__x.get_allocator() == __a) - { - this->_M_impl._M_start = __x._M_impl._M_start; - this->_M_impl._M_finish = __x._M_impl._M_finish; - this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; - __x._M_impl._M_start = _Bit_iterator(); - __x._M_impl._M_finish = _Bit_iterator(); - __x._M_impl._M_end_of_storage = nullptr; - } + this->_M_move_data(std::move(__x)); else { _M_initialize(__x.size()); @@ -716,12 +749,7 @@ template<typename _Alloc> || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator()) { this->_M_deallocate(); - this->_M_impl._M_start = __x._M_impl._M_start; - this->_M_impl._M_finish = __x._M_impl._M_finish; - this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; - __x._M_impl._M_start = _Bit_iterator(); - __x._M_impl._M_finish = _Bit_iterator(); - __x._M_impl._M_end_of_storage = nullptr; + this->_M_move_data(std::move(__x)); std::__alloc_on_move(_M_get_Bit_allocator(), __x._M_get_Bit_allocator()); } @@ -760,7 +788,7 @@ template<typename _Alloc> typename = std::_RequireInputIter<_InputIterator>> void assign(_InputIterator __first, _InputIterator __last) - { _M_assign_dispatch(__first, __last, __false_type()); } + { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } #else template<typename _InputIterator> void @@ -774,7 +802,7 @@ template<typename _Alloc> #if __cplusplus >= 201103L void assign(initializer_list<bool> __l) - { this->assign(__l.begin(), __l.end()); } + { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); } #endif iterator @@ -1101,6 +1129,15 @@ template<typename _Alloc> this->_M_impl._M_start = iterator(0, 0); } this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n); + + } + + void + _M_initialize_value(bool __x) + { + __builtin_memset(this->_M_impl._M_start._M_p, __x ? ~0 : 0, + (this->_M_impl._M_end_addr() - this->_M_impl._M_start._M_p) + * sizeof(_Bit_type)); } void @@ -1120,8 +1157,7 @@ template<typename _Alloc> _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) { _M_initialize(static_cast<size_type>(__n)); - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_addr(), __x ? ~0 : 0); + _M_initialize_value(__x); } template<typename _InputIterator> @@ -1168,15 +1204,13 @@ template<typename _Alloc> { if (__n > size()) { - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_addr(), __x ? ~0 : 0); + _M_initialize_value(__x); insert(end(), __n - size(), __x); } else { _M_erase_at_end(begin() + __n); - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_addr(), __x ? ~0 : 0); + _M_initialize_value(__x); } } diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/allocator/default_init.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/allocator/default_init.cc new file mode 100644 index 0000000..c748532 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/allocator/default_init.cc @@ -0,0 +1,51 @@ +// Copyright (C) 2017 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-do run { target c++11 } } + +#include <vector> +#include <testsuite_hooks.h> +#include <testsuite_allocator.h> + +#include <ext/aligned_buffer.h> + +using T = bool; + +using __gnu_test::default_init_allocator; + +void test01() +{ + typedef default_init_allocator<T> alloc_type; + typedef std::vector<T, alloc_type> test_type; + + __gnu_cxx::__aligned_buffer<test_type> buf; + __builtin_memset(buf._M_addr(), ~0, sizeof(test_type)); + + test_type *v = ::new(buf._M_addr()) test_type(); + v->push_back(T()); + + VERIFY( !v->empty() ); + VERIFY( !v->get_allocator().state ); + + v->~test_type(); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/util/testsuite_allocator.h b/libstdc++-v3/testsuite/util/testsuite_allocator.h index 56c2708..233ea0b 100644 --- a/libstdc++-v3/testsuite/util/testsuite_allocator.h +++ b/libstdc++-v3/testsuite/util/testsuite_allocator.h @@ -508,6 +508,38 @@ namespace __gnu_test bool operator!=(const SimpleAllocator<T>&, const SimpleAllocator<U>&) { return false; } + template<typename T> + struct default_init_allocator + { + using value_type = T; + + default_init_allocator() = default; + + template<typename U> + default_init_allocator(const default_init_allocator<U>& a) + : state(a.state) + { } + + T* + allocate(std::size_t n) + { return std::allocator<T>().allocate(n); } + + void + deallocate(T* p, std::size_t n) + { std::allocator<T>().deallocate(p, n); } + + int state; + }; + + template<typename T, typename U> + bool operator==(const default_init_allocator<T>& t, + const default_init_allocator<U>& u) + { return t.state == u.state; } + + template<typename T, typename U> + bool operator!=(const default_init_allocator<T>& t, + const default_init_allocator<U>& u) + { return !(t == u); } #endif template<typename Tp> ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Default std::vector<bool> default and move constructor 2017-06-01 20:49 ` François Dumont @ 2017-06-02 10:27 ` Jonathan Wakely 0 siblings, 0 replies; 19+ messages in thread From: Jonathan Wakely @ 2017-06-02 10:27 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches On 01/06/17 22:49 +0200, François Dumont wrote: >On 01/06/2017 15:34, Jonathan Wakely wrote: >>On 31/05/17 22:28 +0200, François Dumont wrote: >>>Unless I made a mistake it revealed that restoring explicit call >>>to _Bit_alloc_type() in default constructor was not enough. G++ >>>doesn't transform it into a value-init if needed. I don't know if >>>it is a compiler bug but I had to do just like presented in the >>>Standard to achieve the expected behavior. >> >>That really shouldn't be necessary (see blow). >> >>>This value-init is specific to post-C++11 right ? Maybe I could >>>remove the useless explicit call to _Bit_alloc_type() in pre-C++11 >>>mode ? >> >>No, because C++03 also requires the allocator to be value-initialized. > >Ok so I'll try to make the test C++03 compatible. That would require a much more complicated allocator, so I don't think it's too important. If you define the constructor like: _Bvector_impl() _GLIBCXX_NOEXCEPT_IF( noexcept(_Bit_alloc_type()) ) : _Bit_alloc_type() { } then it will do the same thing for C++03 as for later versions, so testing for C++11 only should be good enough. ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Default std::vector<bool> default and move constructor 2017-06-01 13:34 ` Jonathan Wakely 2017-06-01 20:49 ` François Dumont @ 2017-06-13 20:36 ` François Dumont 2017-06-15 11:07 ` Jonathan Wakely 1 sibling, 1 reply; 19+ messages in thread From: François Dumont @ 2017-06-13 20:36 UTC (permalink / raw) To: Jonathan Wakely; +Cc: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 791 bytes --] On 01/06/2017 15:34, Jonathan Wakely wrote: > > I would expect the constructor to look like this: > > _Bvector_impl() > _GLIBCXX_NOEXCEPT_IF( noexcept(_Bit_alloc_type()) ) > : _Bit_alloc_type() > { } > > What happens when you do that? > > >> _Bvector_impl(const _Bit_alloc_type& __a) >> - : _Bit_alloc_type(__a), _M_start(), _M_finish(), >> _M_end_of_storage() >> + _GLIBCXX_NOEXCEPT_IF( noexcept(_Bit_alloc_type(__a)) ) > > Copying the allocator is not allowed to throw. You can use simply > _GLIBCXX_NOEXCEPT here. Now that we find out what was the problem with default/value initialization of allocator I would like to re-submit this patch with the correct constructor. Tested under Linux x86_64 normal mode. Ok to commit ? François [-- Attachment #2: bvector.patch --] [-- Type: text/x-patch, Size: 12293 bytes --] diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h index 78195c1..6e58503 100644 --- a/libstdc++-v3/include/bits/stl_bvector.h +++ b/libstdc++-v3/include/bits/stl_bvector.h @@ -388,10 +388,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return __x + __n; } inline void - __fill_bvector(_Bit_iterator __first, _Bit_iterator __last, bool __x) + __fill_bvector(_Bit_type * __v, + unsigned int __first, unsigned int __last, bool __x) { - for (; __first != __last; ++__first) - *__first = __x; + const _Bit_type __fmask = ~0ul << __first; + const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last); + const _Bit_type __mask = __fmask & __lmask; + + if (__x) + *__v |= __mask; + else + *__v &= ~__mask; } inline void @@ -399,12 +406,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { if (__first._M_p != __last._M_p) { - std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0); - __fill_bvector(__first, _Bit_iterator(__first._M_p + 1, 0), __x); - __fill_bvector(_Bit_iterator(__last._M_p, 0), __last, __x); + _Bit_type *__first_p = __first._M_p; + if (__first._M_offset != 0) + __fill_bvector(__first_p++, __first._M_offset, _S_word_bit, __x); + + __builtin_memset(__first_p, __x ? ~0 : 0, + (__last._M_p - __first_p) * sizeof(_Bit_type)); + + if (__last._M_offset != 0) + __fill_bvector(__last._M_p, 0, __last._M_offset, __x); } else - __fill_bvector(__first, __last, __x); + __fill_bvector(__first._M_p, __first._M_offset, __last._M_offset, __x); } template<typename _Alloc> @@ -416,33 +429,62 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Bit_alloc_traits; typedef typename _Bit_alloc_traits::pointer _Bit_pointer; - struct _Bvector_impl - : public _Bit_alloc_type + struct _Bvector_impl_data { _Bit_iterator _M_start; _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(_Bvector_impl_data&& __x) noexcept + : _M_start(__x._M_start), _M_finish(__x._M_finish) + , _M_end_of_storage(__x._M_end_of_storage) + { __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; + __x._M_reset(); + } +#endif + + void + _M_reset() _GLIBCXX_NOEXCEPT + { + _M_start = _M_finish = _Bit_iterator(); + _M_end_of_storage = _Bit_pointer(); + } + }; + + struct _Bvector_impl + : public _Bit_alloc_type, public _Bvector_impl_data + { + public: _Bvector_impl() - : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage() + _GLIBCXX_NOEXCEPT_IF( noexcept(_Bit_alloc_type()) ) + : _Bit_alloc_type() { } - _Bvector_impl(const _Bit_alloc_type& __a) - : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage() + _Bvector_impl(const _Bit_alloc_type& __a) _GLIBCXX_NOEXCEPT + : _Bit_alloc_type(__a) { } #if __cplusplus >= 201103L - _Bvector_impl(_Bit_alloc_type&& __a) - : _Bit_alloc_type(std::move(__a)), _M_start(), _M_finish(), - _M_end_of_storage() - { } + _Bvector_impl(_Bvector_impl&&) = default; #endif _Bit_type* _M_end_addr() const _GLIBCXX_NOEXCEPT { - if (_M_end_of_storage) - return std::__addressof(_M_end_of_storage[-1]) + 1; + if (this->_M_end_of_storage) + return std::__addressof(this->_M_end_of_storage[-1]) + 1; return 0; } }; @@ -452,33 +494,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Bit_alloc_type& _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT - { return *static_cast<_Bit_alloc_type*>(&this->_M_impl); } + { return this->_M_impl; } const _Bit_alloc_type& _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT - { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); } + { return this->_M_impl; } allocator_type get_allocator() const _GLIBCXX_NOEXCEPT { return allocator_type(_M_get_Bit_allocator()); } - _Bvector_base() - : _M_impl() { } +#if __cplusplus >= 201103L + _Bvector_base() = default; +#else + _Bvector_base() { } +#endif _Bvector_base(const allocator_type& __a) : _M_impl(__a) { } #if __cplusplus >= 201103L - _Bvector_base(_Bvector_base&& __x) noexcept - : _M_impl(std::move(__x._M_get_Bit_allocator())) - { - this->_M_impl._M_start = __x._M_impl._M_start; - this->_M_impl._M_finish = __x._M_impl._M_finish; - this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; - __x._M_impl._M_start = _Bit_iterator(); - __x._M_impl._M_finish = _Bit_iterator(); - __x._M_impl._M_end_of_storage = nullptr; - } + _Bvector_base(_Bvector_base&&) = default; #endif ~_Bvector_base() @@ -500,11 +536,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Bit_alloc_traits::deallocate(_M_impl, _M_impl._M_end_of_storage - __n, __n); - _M_impl._M_start = _M_impl._M_finish = _Bit_iterator(); - _M_impl._M_end_of_storage = _Bit_pointer(); + _M_impl._M_reset(); } } +#if __cplusplus >= 201103L + void + _M_move_data(_Bvector_base&& __x) noexcept + { _M_impl._M_move_data(std::move(__x._M_impl)); } +#endif + static size_t _S_nword(size_t __n) { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); } @@ -564,7 +605,8 @@ template<typename _Alloc> typedef std::reverse_iterator<iterator> reverse_iterator; typedef _Alloc allocator_type; - allocator_type get_allocator() const + allocator_type + get_allocator() const { return _Base::get_allocator(); } protected: @@ -574,11 +616,11 @@ template<typename _Alloc> using _Base::_M_get_Bit_allocator; public: - vector() #if __cplusplus >= 201103L - noexcept(is_nothrow_default_constructible<allocator_type>::value) + vector() = default; +#else + vector() { } #endif - : _Base() { } explicit vector(const allocator_type& __a) @@ -592,23 +634,16 @@ template<typename _Alloc> vector(size_type __n, const bool& __value, const allocator_type& __a = allocator_type()) - : _Base(__a) - { - _M_initialize(__n); - std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_addr(), - __value ? ~0 : 0); - } #else explicit vector(size_type __n, const bool& __value = bool(), const allocator_type& __a = allocator_type()) +#endif : _Base(__a) { _M_initialize(__n); - std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_addr(), - __value ? ~0 : 0); + _M_initialize_value(__value); } -#endif vector(const vector& __x) : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator())) @@ -618,22 +653,14 @@ template<typename _Alloc> } #if __cplusplus >= 201103L - vector(vector&& __x) noexcept - : _Base(std::move(__x)) { } + vector(vector&&) = default; vector(vector&& __x, const allocator_type& __a) noexcept(_Bit_alloc_traits::_S_always_equal()) : _Base(__a) { if (__x.get_allocator() == __a) - { - this->_M_impl._M_start = __x._M_impl._M_start; - this->_M_impl._M_finish = __x._M_impl._M_finish; - this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; - __x._M_impl._M_start = _Bit_iterator(); - __x._M_impl._M_finish = _Bit_iterator(); - __x._M_impl._M_end_of_storage = nullptr; - } + this->_M_move_data(std::move(__x)); else { _M_initialize(__x.size()); @@ -716,12 +743,7 @@ template<typename _Alloc> || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator()) { this->_M_deallocate(); - this->_M_impl._M_start = __x._M_impl._M_start; - this->_M_impl._M_finish = __x._M_impl._M_finish; - this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; - __x._M_impl._M_start = _Bit_iterator(); - __x._M_impl._M_finish = _Bit_iterator(); - __x._M_impl._M_end_of_storage = nullptr; + this->_M_move_data(std::move(__x)); std::__alloc_on_move(_M_get_Bit_allocator(), __x._M_get_Bit_allocator()); } @@ -760,7 +782,7 @@ template<typename _Alloc> typename = std::_RequireInputIter<_InputIterator>> void assign(_InputIterator __first, _InputIterator __last) - { _M_assign_dispatch(__first, __last, __false_type()); } + { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } #else template<typename _InputIterator> void @@ -774,7 +796,7 @@ template<typename _Alloc> #if __cplusplus >= 201103L void assign(initializer_list<bool> __l) - { this->assign(__l.begin(), __l.end()); } + { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); } #endif iterator @@ -1101,6 +1123,15 @@ template<typename _Alloc> this->_M_impl._M_start = iterator(0, 0); } this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n); + + } + + void + _M_initialize_value(bool __x) + { + __builtin_memset(this->_M_impl._M_start._M_p, __x ? ~0 : 0, + (this->_M_impl._M_end_addr() - this->_M_impl._M_start._M_p) + * sizeof(_Bit_type)); } void @@ -1120,8 +1151,7 @@ template<typename _Alloc> _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) { _M_initialize(static_cast<size_type>(__n)); - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_addr(), __x ? ~0 : 0); + _M_initialize_value(__x); } template<typename _InputIterator> @@ -1168,15 +1198,13 @@ template<typename _Alloc> { if (__n > size()) { - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_addr(), __x ? ~0 : 0); + _M_initialize_value(__x); insert(end(), __n - size(), __x); } else { _M_erase_at_end(begin() + __n); - std::fill(this->_M_impl._M_start._M_p, - this->_M_impl._M_end_addr(), __x ? ~0 : 0); + _M_initialize_value(__x); } } diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/allocator/default_init.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/allocator/default_init.cc new file mode 100644 index 0000000..9ee4697 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/allocator/default_init.cc @@ -0,0 +1,67 @@ +// Copyright (C) 2017 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-do run { target c++11 } } +// { dg-options "-O0" } +// { dg-xfail-run-if "PR c++/65816" { *-*-* } } + +#include <vector> +#include <testsuite_hooks.h> +#include <testsuite_allocator.h> + +#include <ext/aligned_buffer.h> + +using T = bool; + +using __gnu_test::default_init_allocator; + +void test01() +{ + typedef default_init_allocator<T> alloc_type; + typedef std::vector<T, alloc_type> test_type; + + __gnu_cxx::__aligned_buffer<test_type> buf; + __builtin_memset(buf._M_addr(), ~0, sizeof(test_type)); + + test_type *tmp = ::new(buf._M_addr()) test_type; + + VERIFY( tmp->get_allocator().state == 0 ); + + tmp->~test_type(); +} + +void test02() +{ + typedef default_init_allocator<T> alloc_type; + typedef std::vector<T, alloc_type> test_type; + + __gnu_cxx::__aligned_buffer<test_type> buf; + __builtin_memset(buf._M_addr(), ~0, sizeof(test_type)); + + test_type *tmp = ::new(buf._M_addr()) test_type(); + + VERIFY( tmp->get_allocator().state == 0 ); + + tmp->~test_type(); +} + +int main() +{ + test01(); + test02(); + return 0; +} ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Default std::vector<bool> default and move constructor 2017-06-13 20:36 ` François Dumont @ 2017-06-15 11:07 ` Jonathan Wakely 0 siblings, 0 replies; 19+ messages in thread From: Jonathan Wakely @ 2017-06-15 11:07 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches On 13/06/17 22:36 +0200, François Dumont wrote: >On 01/06/2017 15:34, Jonathan Wakely wrote: >> >>I would expect the constructor to look like this: >> >> _Bvector_impl() >> _GLIBCXX_NOEXCEPT_IF( noexcept(_Bit_alloc_type()) ) >> : _Bit_alloc_type() >> { } >> >>What happens when you do that? >> >> >>> _Bvector_impl(const _Bit_alloc_type& __a) >>>- : _Bit_alloc_type(__a), _M_start(), _M_finish(), >>>_M_end_of_storage() >>>+ _GLIBCXX_NOEXCEPT_IF( noexcept(_Bit_alloc_type(__a)) ) >> >>Copying the allocator is not allowed to throw. You can use simply >>_GLIBCXX_NOEXCEPT here. > >Now that we find out what was the problem with default/value >initialization of allocator I would like to re-submit this patch with >the correct constructor. > >Tested under Linux x86_64 normal mode. > >Ok to commit ? OK, thanks. ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Default std::vector<bool> default and move constructor 2017-05-28 20:29 ` François Dumont 2017-05-29 20:57 ` François Dumont @ 2017-05-31 11:13 ` Jonathan Wakely 1 sibling, 0 replies; 19+ messages in thread From: Jonathan Wakely @ 2017-05-31 11:13 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches On 28/05/17 22:13 +0200, François Dumont wrote: >Sure but like freedom which stop where start others' freedom so does >those requirements :-). Because the Standard says that an allocator >will be value-init when there is no default-init it makes usage of the >C++11 default constructor more complicated. It makes the std::lib implementors job harder, for the benefit of users. That is the correct trade off. We don't get to ignore the guarantees of the standard just because they're difficult. ^ permalink raw reply [flat|nested] 19+ messages in thread
end of thread, other threads:[~2017-06-15 11:07 UTC | newest] Thread overview: 19+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2017-05-15 18:38 Default std::vector<bool> default and move constructor François Dumont 2017-05-15 19:36 ` Marc Glisse 2017-05-16 20:38 ` François Dumont 2017-05-16 21:39 ` Marc Glisse 2017-05-19 19:42 ` François Dumont 2017-05-23 20:14 ` François Dumont 2017-05-25 16:33 ` Jonathan Wakely 2017-05-26 21:34 ` François Dumont 2017-05-27 11:16 ` Jonathan Wakely 2017-05-28 20:29 ` François Dumont 2017-05-29 20:57 ` François Dumont 2017-05-31 10:37 ` Jonathan Wakely 2017-05-31 20:34 ` François Dumont 2017-06-01 13:34 ` Jonathan Wakely 2017-06-01 20:49 ` François Dumont 2017-06-02 10:27 ` Jonathan Wakely 2017-06-13 20:36 ` François Dumont 2017-06-15 11:07 ` Jonathan Wakely 2017-05-31 11:13 ` Jonathan Wakely
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).