Default std::vector<bool> default and move constructor

Default std::vector<bool> default and move constructor

[François Dumont]

[-- 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);
 	  }
       }
 

Re: Default std::vector<bool> default and move constructor

[Marc Glisse]

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

Re: Default std::vector<bool> default and move constructor

[François Dumont]

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

Re: Default std::vector<bool> default and move constructor

[Marc Glisse]

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<bool> default and move constructor

[François Dumont]

[-- 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);
 	  }
       }
 

Re: Default std::vector<bool> default and move constructor

[François Dumont]

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
>
>

Re: Default std::vector<bool> default and move constructor

[Jonathan Wakely]

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.

Re: Default std::vector<bool> default and move constructor

[François Dumont]

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

Re: Default std::vector<bool> default and move constructor

[Jonathan Wakely]

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); }

Re: Default std::vector<bool> default and move constructor

[François Dumont]

[-- 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
 

Re: Default std::vector<bool> default and move constructor

[François Dumont]

[-- 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);
 	  }
       }
 

Re: Default std::vector<bool> default and move constructor

[Jonathan Wakely]

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.

Re: Default std::vector<bool> default and move constructor

[Jonathan Wakely]

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<bool> default and move constructor

[François Dumont]

[-- 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>

Re: Default std::vector<bool> default and move constructor

[Jonathan Wakely]

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).

Re: Default std::vector<bool> default and move constructor

[François Dumont]

[-- 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>

Re: Default std::vector<bool> default and move constructor

[Jonathan Wakely]

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<bool> default and move constructor

[François Dumont]

[-- 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;
+}

Re: Default std::vector<bool> default and move constructor

[Jonathan Wakely]

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.