[PATCH] Improve std::fill for vector<bool>

[PATCH] Improve std::fill for vector<bool>

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 866 bytes --]

Hi

I am not clear about current stage so I am proposing this trivial patch 
to find out if we are back in stage 1.

This patch extend the overload so that it is used even when 
_GLIBCXX_DEBUG mode is activated.

             * include/bits/stl_algobase.h (struct _Bit_iterator): New 
declaration.
             (std::__fill_a1(_Bit_iterator, _Bit_iterator, const 
bool&)): Likewise.
             * include/bits/stl_bvector.h (__fill_bvector): Move outside
             _GLIBCXX_STD_C namespace.
             (fill(_Bit_iterator, _Bit_iterator, const bool&)): Likewise 
and rename
             into...
             (__fill_a1): ...this.
             * testsuite/25_algorithms/fill/bvector/1.cc: New.

Tested under Linux x86_64 normal and debug modes.

Ok to commit ?

François


[-- Attachment #2: bvector_fill.patch --]
[-- Type: text/x-patch, Size: 5390 bytes --]

diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index aca70bc1239..133507483a6 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -438,6 +438,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   template<typename _Tp, typename _Ref, typename _Ptr>
     struct _Deque_iterator;
 
+  struct _Bit_iterator;
+
 _GLIBCXX_END_NAMESPACE_CONTAINER
 
   // Helpers for streambuf iterators (either istream or ostream).
@@ -957,6 +959,10 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
 	      const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
 	      const _VTp&);
 
+  void
+  __fill_a1(_GLIBCXX_STD_C::_Bit_iterator, _GLIBCXX_STD_C::_Bit_iterator,
+	    const bool&);
+
   template<typename _FIte, typename _Tp>
     _GLIBCXX20_CONSTEXPR
     inline void
diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h
index f245e52b25d..a365e7182eb 100644
--- a/libstdc++-v3/include/bits/stl_bvector.h
+++ b/libstdc++-v3/include/bits/stl_bvector.h
@@ -416,39 +416,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     { return __x + __n; }
   };
 
-  inline void
-  __fill_bvector(_Bit_type * __v,
-		 unsigned int __first, unsigned int __last, bool __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
-  fill(_Bit_iterator __first, _Bit_iterator __last, const bool& __x)
-  {
-    if (__first._M_p != __last._M_p)
-      {
-	_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 if (__first._M_offset != __last._M_offset)
-      __fill_bvector(__first._M_p, __first._M_offset, __last._M_offset, __x);
-  }
-
   template<typename _Alloc>
     struct _Bvector_base
     {
@@ -1336,15 +1303,46 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   };
 
 _GLIBCXX_END_NAMESPACE_CONTAINER
-_GLIBCXX_END_NAMESPACE_VERSION
-} // namespace std
 
-#if __cplusplus >= 201103L
+  inline void
+  __fill_bvector(_GLIBCXX_STD_C::_Bit_type * __v,
+		 unsigned int __first, unsigned int __last, bool __x)
+  {
+    using _GLIBCXX_STD_C::_Bit_type;
+    using _GLIBCXX_STD_C::_S_word_bit;
+    const _Bit_type __fmask = ~0ul << __first;
+    const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last);
+    const _Bit_type __mask = __fmask & __lmask;
 
-namespace std _GLIBCXX_VISIBILITY(default)
-{
-_GLIBCXX_BEGIN_NAMESPACE_VERSION
+    if (__x)
+      *__v |= __mask;
+    else
+      *__v &= ~__mask;
+  }
 
+  inline void
+  __fill_a1(_GLIBCXX_STD_C::_Bit_iterator __first,
+	    _GLIBCXX_STD_C::_Bit_iterator __last, const bool& __x)
+  {
+    using _GLIBCXX_STD_C::_Bit_type;
+    using _GLIBCXX_STD_C::_S_word_bit;
+    if (__first._M_p != __last._M_p)
+      {
+	_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 if (__first._M_offset != __last._M_offset)
+      __fill_bvector(__first._M_p, __first._M_offset, __last._M_offset, __x);
+  }
+
+#if __cplusplus >= 201103L
   // DR 1182.
   /// std::hash specialization for vector<bool>.
   template<typename _Alloc>
@@ -1354,10 +1352,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       size_t
       operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept;
     };
+#endif // C++11
 
 _GLIBCXX_END_NAMESPACE_VERSION
-}// namespace std
-
-#endif // C++11
+} // namespace std
 
 #endif
diff --git a/libstdc++-v3/testsuite/25_algorithms/fill/bvector/1.cc b/libstdc++-v3/testsuite/25_algorithms/fill/bvector/1.cc
new file mode 100644
index 00000000000..22e4fca73b8
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/fill/bvector/1.cc
@@ -0,0 +1,39 @@
+// Copyright (C) 2020 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/>.
+
+#include <algorithm>
+#include <vector>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  using namespace std;
+
+  vector<bool> v1(100, false);
+  vector<bool> v2(100, true);
+
+  fill(v1.begin(), v1.end(), true);
+
+  VERIFY( equal(v1.begin(), v1.end(), v2.begin()) );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}

Re: [PATCH] Improve std::fill for vector<bool>

[Jonathan Wakely]

On 06/05/20 20:46 +0200, François Dumont via Libstdc++ wrote:
>Hi
>
>I am not clear about current stage so I am proposing this trivial 
>patch to find out if we are back in stage 1.

The current status is always shown on the front page of gcc.gnu.org
(although currently the link to the GCC 11 status is broken, because
the list archives got renumbered for some reason, it should be
https://gcc.gnu.org/pipermail/gcc/2020-April/000505.html for GCC 11).

>This patch extend the overload so that it is used even when 
>_GLIBCXX_DEBUG mode is activated.
>
>            * include/bits/stl_algobase.h (struct _Bit_iterator): New 
>declaration.
>            (std::__fill_a1(_Bit_iterator, _Bit_iterator, const 
>bool&)): Likewise.
>            * include/bits/stl_bvector.h (__fill_bvector): Move outside
>            _GLIBCXX_STD_C namespace.
>            (fill(_Bit_iterator, _Bit_iterator, const bool&)): 
>Likewise and rename
>            into...
>            (__fill_a1): ...this.
>            * testsuite/25_algorithms/fill/bvector/1.cc: New.
>
>Tested under Linux x86_64 normal and debug modes.
>
>Ok to commit ?

OK, thanks.

Re: [PATCH] Improve std::fill for vector<bool>

[Jonathan Wakely]

On 06/05/20 20:35 +0100, Jonathan Wakely wrote:
>On 06/05/20 20:46 +0200, François Dumont via Libstdc++ wrote:
>>Hi
>>
>>I am not clear about current stage so I am proposing this trivial 
>>patch to find out if we are back in stage 1.
>
>The current status is always shown on the front page of gcc.gnu.org
>(although currently the link to the GCC 11 status is broken, because
>the list archives got renumbered for some reason, it should be
>https://gcc.gnu.org/pipermail/gcc/2020-April/000505.html for GCC 11).
>
>>This patch extend the overload so that it is used even when 
>>_GLIBCXX_DEBUG mode is activated.
>>
>>            * include/bits/stl_algobase.h (struct _Bit_iterator): 
>>New declaration.
>>            (std::__fill_a1(_Bit_iterator, _Bit_iterator, const 
>>bool&)): Likewise.
>>            * include/bits/stl_bvector.h (__fill_bvector): Move outside
>>            _GLIBCXX_STD_C namespace.
>>            (fill(_Bit_iterator, _Bit_iterator, const bool&)): 
>>Likewise and rename
>>            into...
>>            (__fill_a1): ...this.
>>            * testsuite/25_algorithms/fill/bvector/1.cc: New.
>>
>>Tested under Linux x86_64 normal and debug modes.
>>
>>Ok to commit ?
>
>OK, thanks.

I've just fixed the indentation in libstdc++-v3/ChangeLog to use
leading tabs not spaces (at 91d505491c7deda61de04dd64da008e0205abf74).