[Bug c++/100070] New: Standard library container iterator-pair constructors should check C++20 iterator concepts

[Bug c++/100070] New: Standard library container iterator-pair constructors should check C++20 iterator concepts

[barry.revzin at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070

            Bug ID: 100070
           Summary: Standard library container iterator-pair constructors
                    should check C++20 iterator concepts
           Product: gcc
           Version: 10.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: barry.revzin at gmail dot com
  Target Milestone: ---

>From StackOverflow (https://stackoverflow.com/q/67081354/2069064), a user was
benchmarking code that did this:

   int convert(int);

   std::vector<int> foo(100,42);
   auto transform_range = foo | std::ranges::views::transform(convert);
   std::vector<int> fooTimesTwo(transform_range.begin(),
transform_range.end());

And found it to be much slower than their initial implementation that did not
use ranges. This is because while transform_range is a C++20 random access
range, it is only a C++17 input range. 

libstdc++'s decision is based entirely on iterator_category
(https://github.com/gcc-mirror/gcc/blob/8084ab15a3e300e3b2c537e56e0f3a1b00778aec/libstdc%2B%2B-v3/include/bits/stl_vector.h#L652-L659)
which does the best you can with an input range: just loop and emplace.

But if it instead checked for forward_iterator and random_access_iterator (the
concept), this construction case could be handled efficiently (i.e. as a single
allocation). I think that should safe? Checking for random_access_iterator
checks the tag before checking for the validity of operator-?

[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
          Component|c++                         |libstdc++
   Last reconfirmed|                            |2021-04-13

[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
We want to do the same thing in insert and assign too. And in std::deque.

[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
This is a partial solution:

--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -654,6 +654,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
               const allocator_type& __a = allocator_type())
        : _Base(__a)
        {
+#if __cpp_lib_concepts
+         if constexpr (forward_iterator<_InputIterator>)
+           {
+             size_type __n;
+             if constexpr (random_access_iterator<_InputIterator>)
+               __n = __last - __first;
+             else
+               __n = std::distance(__first, __last);
+             _M_range_initialize_n(__first, __last, __n);
+             return;
+           }
+         else
+#endif
          _M_range_initialize(__first, __last,
                              std::__iterator_category(__first));
        }
@@ -1577,7 +1590,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
                            std::forward_iterator_tag)
        {
-         const size_type __n = std::distance(__first, __last);
+         _M_range_initialize_n(__first, __last,
+                               std::distance(__first, __last));
+       }
+
+      template<typename _InputIterator>
+       void
+       _M_range_initialize_n(_InputIterator __first, _InputIterator __last,
+                             size_type __n)
+       {
          this->_M_impl._M_start
            = this->_M_allocate(_S_check_init_len(__n, _M_get_Tp_allocator()));
          this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;


This doubles the speed of the vector construction, but it's still slow because
it uses std::copy to copy the range elements into the vector, and std::copy
also dispatches on the iterator_category.

[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
So I think there is a *lot* work needed throughout the library to solve the
general problem that the existing container code uses C++17 iterator categories
and C++17 std::algos (not ranges::algos).

We might be better off just waiting for a vector(range&&) constructor.

[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Barry suggested out-of-band that we could change std::__iterator_category to
determine the result based on the C++20 iterator concepts. That looks
promising.

std::distance dispatches on the result of std::__iterator_category, and doesn't
care whether some meets all the Cpp17RandomAccessIterator requirements, it only
cares whether (last - first) is valid and efficient.

We need to audit all the uses of std::__iterator_category to see whether any
code in libstdc++ that gets used for std::forward_iterator_tag actually depends
on the reference type being a reference. So far it looks like the answer is no.

[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
If there is code that cares, we could always add std::__cpp17_iterator_category
for the cases where we really care about the traditional category (or where
we're forwarding the result of *i to user code which might care but we can't
tell).

[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I'm not sure we should make std::__iterator_category just return
std::__detail::__iter_concept, because that has a fallback of
random_access_iterator_tag and I keep forgetting why that is. And I don't think
it's what we want here.

So just:

--- a/libstdc++-v3/include/bits/stl_iterator_base_types.h
+++ b/libstdc++-v3/include/bits/stl_iterator_base_types.h
@@ -236,7 +236,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     inline _GLIBCXX_CONSTEXPR
     typename iterator_traits<_Iter>::iterator_category
     __iterator_category(const _Iter&)
-    { return typename iterator_traits<_Iter>::iterator_category(); }
+    {
+#if __cpp_lib_concepts
+      if constexpr (random_access_iterator<_Iter>)
+       return random_access_iterator_tag{};
+      else if constexpr (bidirectional_iterator<_Iter>)
+       return bidirectional_iterator_tag{};
+      else if constexpr (forward_iterator<_Iter>)
+       return forward_iterator_tag{};
+      else
+#endif
+      return typename iterator_traits<_Iter>::iterator_category();
+    }

   ///@}

[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Note to self/Patrick:

Measure whether it helps to specialize transform_view's iterator so that when
_Base_iter is __normal_iterator we unwrap it and store a raw pointer.

Also, I suspect the indirections in

  return std::__invoke(*_M_parent->_M_fun, *_M_current);

are making the optimizer give up.

We have an indirection to the parent to access the semi-regular box, which has
its own indirections. Maybe we could just get rid of the semi-regular box for a
function pointer and store a function pointer (i.e. decay_t<Fp>) directly. That
would have the same syntax (i.e. operator*) to access it as the semi-regular
box, but would be less abstraction to un-abstract.

And maybe store a function pointer directly in the transform_view iterator, so
we don't need to go to the parent to get it on every dereference.

Barry pointed out that range-v3 elides the use of semi-regular box for some
cases, and he confirmed that storing a function pointer in the iterator helps.

[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts

[ppalka at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070

Patrick Palka <ppalka at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ppalka at gcc dot gnu.org

--- Comment #8 from Patrick Palka <ppalka at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #7)
> Note to self/Patrick:
> 
> Measure whether it helps to specialize transform_view's iterator so that
> when _Base_iter is __normal_iterator we unwrap it and store a raw pointer.
> 
> Also, I suspect the indirections in
> 
>   return std::__invoke(*_M_parent->_M_fun, *_M_current);
> 
> are making the optimizer give up.
> 
> We have an indirection to the parent to access the semi-regular box, which
> has its own indirections. Maybe we could just get rid of the semi-regular
> box for a function pointer and store a function pointer (i.e. decay_t<Fp>)
> directly.
> 
> And maybe store a function pointer directly in the transform_view iterator,
> so we don't need to go to the parent to get it on every dereference.

Makes sense to me.  I think we could then get rid of the iterator's _M_parent
data member since it's used only to access the transformation function.  And
doing so would also reduce the size of the iterator in the case where the
transformation function is an empty functor (and so [[no_unique_address]] could
optimize away its storage).

> 
> Barry pointed out that range-v3 elides the use of semi-regular box for some
> cases, and he confirmed that storing a function pointer in the iterator
> helps.

FWIW we already elide the semiregular box for types which are semiregular, via
a partial specialization of __box that is just a [[no_unique_wrapper]] for the
underlying semiregular type.

[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts

[ppalka at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070

Patrick Palka <ppalka at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=100795

--- Comment #9 from Patrick Palka <ppalka at gcc dot gnu.org> ---
This seems to be related to the correctness bug PR100795: some of our
ranges::algos (e.g. ranges::inplace_merge) are implemented as simple wrappers
over the corresponding std::algo, but that breaks in cases where the std::algo
has a minimum requirement on the range's iterator_category..

[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=102181

--- Comment #10 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #4)
> Barry suggested out-of-band that we could change std::__iterator_category to
> determine the result based on the C++20 iterator concepts. That looks
> promising.
> 
> std::distance dispatches on the result of std::__iterator_category, and
> doesn't care whether some meets all the Cpp17RandomAccessIterator
> requirements, it only cares whether (last - first) is valid and efficient.

I have a patch to do this for PR 102181 however the suggested direction for lwg
3197 is to require Cpp17InputIterator for std distance, and not Do The Right
Thing for C++20 iterators. We could of course so it anyway as a valid
interpretation of a precondition violation.

[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070

--- Comment #11 from Jonathan Wakely <redi at gcc dot gnu.org> ---
https://wg21.link/p2408 is in this area, but doesn't touch the containers. 

https://wg21.link/p1206 solves the problem, although it's not as convenient as
Barry asked for. You can construct a subrange from the new-style iterators and
then pass that to the new container members that accept ranges.