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

["François Dumont" <frs.dumont@gmail.com>]

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