Re: Default std::vector default and move constructor
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.
Re: Default std::vector default and move constructor
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 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 @@ -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*>(>_M_impl); } + { return this->_M_impl; } const _Bit_alloc_type& _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT - { return *static_cast(>_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
Re: Default std::vector default and move constructor
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.
Re: Default std::vector default and move constructor
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, 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_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 alloc_type; + typedef std::vectortest_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 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 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,
Re: Default std::vector default and move constructor
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())) ) 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 alloc_type; + typedef std::vectortest_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 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).
Re: Default std::vector default and move constructor
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::operator=(vector&&)): Likewise. (vector::vector()): Default. (vector::assign(_InputIterator, _InputIterator)): Use _M_assign_aux. (vector::assign(initializer_list)): Likewise. (vector::_M_initialize_value(bool)): New. (vector(size_type, const bool&, const allocator_type&)): Use latter. (vector::_M_initialize_dispatch(_Integer, _Integer, __true_type)): Likewise. (vector::_M_fill_assign(size_t, bool)): Likewise. Ok to commit ? François 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 @@ -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(
Re: Default std::vector default and move constructor
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.
Re: Default std::vector default and move constructor
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::_M_initialize but I don't think it will conflict with your changes.
Re: Default std::vector default and move constructor
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. 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 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 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 @@ -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(),
Re: Default std::vector default and move constructor
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. 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 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 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 +struct __alloc_value_initializer; + + template +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 +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
Re: Default std::vector default and move constructor
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. 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 to value-init the allocator. Not default-init. Here's an allocator that behaves differently if value-initialized or default-initialized: template struct Alloc { using value_type = T; Alloc() = default; template Alloc(const Alloc& a) : mem(a.mem) { } T* allocate(std::size_t n) { if (mem) throw 1; return std::allocator().allocate(n); } void deallocate(T* p, std::size_t n) { std::allocator().deallocate(p, n); } int mem; }; template bool operator==(const Alloc& t, const Alloc& u) { return t.mem == u.mem; } template bool operator!=(const Alloc& t, const Alloc& u) { return !(t == u); }
Re: Default std::vector default and move constructor
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. 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
Re: Default std::vector default and move constructor
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. 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.
Re: Default std::vector default and move constructor
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 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
Re: Default std::vector default and move constructor
Hi On 15/05/2017 21:31, Marc Glisse wrote: The __fill_bvector part of the fill overload for vector 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 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 @@ -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
Re: Default std::vector default and move constructor
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
Re: Default std::vector default and move constructor
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 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
Re: Default std::vector default and move constructor
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 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
Default std::vector default and move constructor
Hi Following what I have started on RbTree here is a patch to default implementation of default and move constructors on std::vector. 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::operator=(vector&&)): Likewise. (vector::vector()): Default. (vector::assign(_InputIterator, _InputIterator)): Use _M_assign_aux. (vector::assign(initializer_list)): Likewise. (vector::_M_initialize_value(bool)): New. (vector(size_type, const bool&, const allocator_type&)): Use latter. (vector::_M_initialize_dispatch(_Integer, _Integer, __true_type)): Likewise. (vector::_M_fill_assign(size_t, bool)): Likewise. Tested under Linux x86_64 normal mode, with and without versioned namespace. Ok to commit ? François 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; -