This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Default std::vector<bool> default and move constructor
- From: François Dumont <frs dot dumont at gmail dot com>
- To: Jonathan Wakely <jwakely at redhat dot com>
- Cc: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Thu, 1 Jun 2017 22:49:53 +0200
- Subject: Re: Default std::vector<bool> default and move constructor
- Authentication-results: sourceware.org; auth=none
- References: <cda87f91-d9fd-692b-f60e-dcc92728f02e@gmail.com> <20170525162816.GD12306@redhat.com> <ecc75c47-7a8e-2b91-7ef0-8cf2e1a09815@gmail.com> <20170527111401.GH12306@redhat.com> <b580bfe8-adef-1926-7b2b-2a6a6ca478cf@gmail.com> <4fcb496e-08ed-85ef-0470-e4f5b0d816ca@gmail.com> <20170531103454.GL12306@redhat.com> <164fb25b-dedc-21f4-9305-f68c47fa58df@gmail.com> <20170601133402.GU12306@redhat.com>
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
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>