[PATCH] Optimize seed_seq construction

[PATCH] Optimize seed_seq construction

[Antony Polukhin]

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

When std::seed_seq is constructed from random access iterators we can
detect the internal vector size in O(1). Reserving memory for elements
in such cases may avoid multiple memory allocations.

libstdc++-v3/ChangeLog:

        * include/bits/random.tcc: Optimize seed_seq construction.

-- 
Best regards,
Antony Polukhin

[-- Attachment #2: seed_seq_optimize_construction.txt --]
[-- Type: text/plain, Size: 1503 bytes --]

diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc
index bf43970..816bfc1 100644
--- a/libstdc++-v3/include/bits/random.tcc
+++ b/libstdc++-v3/include/bits/random.tcc
@@ -3234,14 +3234,31 @@ namespace __detail
   template<typename _IntType>
     seed_seq::seed_seq(std::initializer_list<_IntType> __il)
     {
+      _M_v.reserve(__il.size());
       for (auto __iter = __il.begin(); __iter != __il.end(); ++__iter)
 	_M_v.push_back(__detail::__mod<result_type,
 		       __detail::_Shift<result_type, 32>::__value>(*__iter));
     }
 
+  template<typename _Vector, typename _InputIterator>
+    void __reserve_if_distance_cheap(_Vector& __vec, _InputIterator __begin,
+      _InputIterator __end, random_access_iterator_tag)
+    {
+      __vec.reserve(__end - __begin);
+    }
+
+  template<typename _Vector, typename _InputIterator, typename _Tag>
+    void __reserve_if_distance_cheap(_Vector&, _InputIterator,
+      _InputIterator, _Tag)
+    {
+      // computing the distance between __begin and __end is not O(1)
+    }
+
   template<typename _InputIterator>
     seed_seq::seed_seq(_InputIterator __begin, _InputIterator __end)
     {
+      std::__reserve_if_distance_cheap(_M_v, __begin, __end,
+          typename iterator_traits<_InputIterator>::iterator_category());
       for (_InputIterator __iter = __begin; __iter != __end; ++__iter)
 	_M_v.push_back(__detail::__mod<result_type,
 		       __detail::_Shift<result_type, 32>::__value>(*__iter));

Re: [PATCH] Optimize seed_seq construction

[Jonathan Wakely]

On Tue, 17 Aug 2021 at 09:42, Antony Polukhin wrote:
>
> When std::seed_seq is constructed from random access iterators we can
> detect the internal vector size in O(1). Reserving memory for elements
> in such cases may avoid multiple memory allocations.
>
> libstdc++-v3/ChangeLog:
>
>         * include/bits/random.tcc: Optimize seed_seq construction.

Thanks, this is a nice improvement. We can avoid tag dispatching to
make it simpler though:

@@ -3248,6 +3249,9 @@ namespace __detail
  template<typename _InputIterator>
    seed_seq::seed_seq(_InputIterator __begin, _InputIterator __end)
    {
+      if _GLIBCXX17_CONSTEXPR
(__is_random_access_iter<_InputIterator>::value)
+       _M_v.reserve(std::distance(__begin, __end));
+
      for (_InputIterator __iter = __begin; __iter != __end; ++__iter)
       _M_v.push_back(__detail::__mod<result_type,
                      __detail::_Shift<result_type, 32>::__value>(*__iter));

The call to std::distance is well-formed for input iterators, but we
won't actually call it unless we have random access iterators.

Unless you see a problem with this that I'm missing, I'll go with that version.

Re: [PATCH] Optimize seed_seq construction

[Antony Polukhin]

вт, 17 авг. 2021 г. в 16:37, Jonathan Wakely <jwakely@redhat.com>:
<...>
> Thanks, this is a nice improvement. We can avoid tag dispatching to
> make it simpler though:
>
> @@ -3248,6 +3249,9 @@ namespace __detail
>   template<typename _InputIterator>
>     seed_seq::seed_seq(_InputIterator __begin, _InputIterator __end)
>     {
> +      if _GLIBCXX17_CONSTEXPR
> (__is_random_access_iter<_InputIterator>::value)
> +       _M_v.reserve(std::distance(__begin, __end));
> +
>       for (_InputIterator __iter = __begin; __iter != __end; ++__iter)
>        _M_v.push_back(__detail::__mod<result_type,
>                       __detail::_Shift<result_type, 32>::__value>(*__iter));
>
> The call to std::distance is well-formed for input iterators, but we
> won't actually call it unless we have random access iterators.
>
> Unless you see a problem with this that I'm missing, I'll go with that version.

Looks much better. Thanks!

-- 
Best regards,
Antony Polukhin

Re: [PATCH] Optimize seed_seq construction

[Jonathan Wakely]

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

On Tue, 17 Aug 2021 at 14:40, Antony Polukhin <antoshkka@gmail.com> wrote:
>
> вт, 17 авг. 2021 г. в 16:37, Jonathan Wakely <jwakely@redhat.com>:
> <...>
> > Thanks, this is a nice improvement. We can avoid tag dispatching to
> > make it simpler though:
> >
> > @@ -3248,6 +3249,9 @@ namespace __detail
> >   template<typename _InputIterator>
> >     seed_seq::seed_seq(_InputIterator __begin, _InputIterator __end)
> >     {
> > +      if _GLIBCXX17_CONSTEXPR
> > (__is_random_access_iter<_InputIterator>::value)
> > +       _M_v.reserve(std::distance(__begin, __end));
> > +
> >       for (_InputIterator __iter = __begin; __iter != __end; ++__iter)
> >        _M_v.push_back(__detail::__mod<result_type,
> >                       __detail::_Shift<result_type, 32>::__value>(*__iter));
> >
> > The call to std::distance is well-formed for input iterators, but we
> > won't actually call it unless we have random access iterators.
> >
> > Unless you see a problem with this that I'm missing, I'll go with that version.
>
> Looks much better. Thanks!

Here's what I've tested and pushed to trunk.

Thanks again!

[-- Attachment #2: patch.txt --]
[-- Type: text/plain, Size: 2521 bytes --]

commit 174f9257a75dec93221eca26c236e0a6346c9dfd
Author: Antony Polukhin <antoshkka@gmail.com>
Date:   Tue Aug 17 13:50:53 2021

    libstdc++: Optimize std::seed_seq construction
    
    When std::seed_seq is constructed from random access iterators we can
    detect the internal vector size in O(1). Reserving memory for elements
    in such cases may avoid multiple memory allocations.
    
    Signed-off-by: Jonathan Wakely <jwakely@redhat.com>
    
    libstdc++-v3/ChangeLog:
    
            * include/bits/random.tcc (seed_seq::seed_seq): Reserve capacity
            if distance is O(1).
            * testsuite/26_numerics/random/pr60037-neg.cc: Adjust dg-error
            line number.
    
    Co-authored-by: Jonathan Wakely <jwakely@redhat.com>

diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc
index 0be50d90e8a..023fded7f5d 100644
--- a/libstdc++-v3/include/bits/random.tcc
+++ b/libstdc++-v3/include/bits/random.tcc
@@ -3240,6 +3240,7 @@ namespace __detail
   template<typename _IntType, typename>
     seed_seq::seed_seq(std::initializer_list<_IntType> __il)
     {
+      _M_v.reserve(__il.size());
       for (auto __iter = __il.begin(); __iter != __il.end(); ++__iter)
 	_M_v.push_back(__detail::__mod<result_type,
 		       __detail::_Shift<result_type, 32>::__value>(*__iter));
@@ -3248,6 +3249,9 @@ namespace __detail
   template<typename _InputIterator>
     seed_seq::seed_seq(_InputIterator __begin, _InputIterator __end)
     {
+      if _GLIBCXX17_CONSTEXPR (__is_random_access_iter<_InputIterator>::value)
+	_M_v.reserve(std::distance(__begin, __end));
+
       for (_InputIterator __iter = __begin; __iter != __end; ++__iter)
 	_M_v.push_back(__detail::__mod<result_type,
 		       __detail::_Shift<result_type, 32>::__value>(*__iter));
diff --git a/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc b/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc
index 8fba7144d8a..3ab9c44232e 100644
--- a/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc
+++ b/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc
@@ -12,4 +12,4 @@ auto x = std::generate_canonical<std::size_t,
 
 // { dg-error "static assertion failed: template argument must be a floating point type" "" { target *-*-* } 169 }
 
-// { dg-error "static assertion failed: template argument must be a floating point type" "" { target *-*-* } 3352 }
+// { dg-error "static assertion failed: template argument must be a floating point type" "" { target *-*-* } 3356 }