Message ID | CAKqmYPa137-NdG8a0Jds5GSv230ufazYscmepFBNUHZWoSoc0w@mail.gmail.com |
---|---|
State | New |
Headers | show |
Series | Optimize seed_seq construction | expand |
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.
вт, 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!
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! 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 }
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));