[Bug libstdc++/110512] New: C++20 random access iterators run sequentially with PSTL

[Bug libstdc++/110512] New: C++20 random access iterators run sequentially with PSTL

[gonzalo.gadeschi at gmail dot com]

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

            Bug ID: 110512
           Summary: C++20 random access iterators run sequentially with
                    PSTL
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gonzalo.gadeschi at gmail dot com
  Target Milestone: ---

See https://github.com/llvm/llvm-project/issues/63447

The problem is the following:

std::vector<int> x(n), y(n);
auto ids = std::views::iota((int)0, (int)x.size());
std::for_each(std::execution::par_unseq, ids.begin(), ids.end(), [x = x.data(),
y = y.data()](int i) {
    x[i] = y[i];
});

Iterators from C++20 ranges model the C++20 random_access_iterator concept, but
do not necessarily have a random access iterator tag. They are not recognized
by the PSTL as random access iterators (but forward iterators), causing the
parallel algorithms to fall back to sequential execution.

This is significantly impacting the performance a couple of large HPC
applications.

A quick and dirty workaround is to modify pstl/executors_impls.hpp by changing
the random_access_iterator<IteratorType> to:

template <typename _IteratorType>
struct __is_random_access_iterator<_IteratorType> {
    static constexpr bool value = (
        (bool)std::is_same_v<typename
std::iterator_traits<_IteratorType>::iterator_category,
std::random_access_iterator_tag>
        || (bool)::std::random_access_iterator<_IteratorType>
    );
    typedef std::integral_constant<bool, value> type;
};

Since llvm-project/pstl has been forked by libc++, it does no longer make sense
to try to patch pstl upstream to fix this issue.

[Bug libstdc++/110512] C++20 random access iterators run sequentially with PSTL

[redi at gcc dot gnu.org]

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

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I think this is the correct behaviour according to the standard. We have other
bug reports about C++20 iterators used with STL algos and containers, which
again, are working as required by the standard.

[Bug libstdc++/110512] C++20 random access iterators run sequentially with PSTL

[redi at gcc dot gnu.org]

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

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

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

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
See PR 100070. This is basically the same issue, but for PSTL.

[Bug libstdc++/110512] C++20 random access iterators run sequentially with PSTL

[gonzalo.gadeschi at gmail dot com]

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

--- Comment #3 from gnzlbg <gonzalo.gadeschi at gmail dot com> ---
@Jonathan What is missing in https://wg21.link/p2408 to enable the PSTL to use
the iterator concept for the iota_view::iterator such that the PSTL may run the
above in parallel?

[Bug libstdc++/110512] C++20 random access iterators run sequentially with PSTL

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2023-07-02
     Ever confirmed|0                           |1
             Blocks|                            |106749

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Oh I forgot we approved that one


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106749
[Bug 106749] Implement C++23 library features

[Bug libstdc++/110512] C++20 random access iterators run sequentially with PSTL

[gonzalo.gadeschi at gmail dot com]

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

--- Comment #5 from gnzlbg <gonzalo.gadeschi at gmail dot com> ---
The patch for this bug in libc++ has been reviewed:
https://reviews.llvm.org/D154305 

I've submitted a patch for the same issue to libstdc++: 
https://gcc.gnu.org/pipermail/libstdc++/2023-July/056266.html

[Bug libstdc++/110512] C++20 random access iterators run sequentially with PSTL

[redi at gcc dot gnu.org]

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

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
The proposed change will compile very slowly, something like this would be
better:

--- a/libstdc++-v3/include/pstl/execution_impl.h
+++ b/libstdc++-v3/include/pstl/execution_impl.h
@@ -19,13 +19,24 @@ namespace __pstl
 {
 namespace __internal
 {
+#if __glibcxx_concepts
+template<typename _Iter>
+  concept __is_random_access_iter
+    = std::is_base_of_v<std::random_access_iterator_tag,
+                       std::__iter_category_t<_Iter>>
+      || std::random_access_iterator<_Iter>;

+template <typename... _IteratorTypes>
+  using __are_random_access_iterators
+    = std::bool_constant<(__is_random_access_iter<_IteratorTypes> && ...)>;
+#else
 template <typename _IteratorTag, typename... _IteratorTypes>
 using __are_iterators_of = std::conjunction<
     std::is_base_of<_IteratorTag, typename
std::iterator_traits<std::decay_t<_IteratorTypes>>::iterator_category>...>;

 template <typename... _IteratorTypes>
 using __are_random_access_iterators =
__are_iterators_of<std::random_access_iterator_tag, _IteratorTypes...>;
+#endif

 struct __serial_backend_tag
 {



This uses the libstdc++ helper __iter_category_t but since we no longer need to
sync with upstream, that seems fine.

[Bug libstdc++/110512] C++20 random access iterators run sequentially with PSTL

[redi at gcc dot gnu.org]

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

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Actually, if we don't care about upstream any more, we can improve the
pre-C++20 version too:

template <typename... _IteratorTypes>
using __are_random_access_iterators
    = std::__or_<std::is_base_of<std::random_access_iterator_tag,
                                 std::__iter_category_t<_IteratorTypes>>...>;

[Bug libstdc++/110512] C++20 random access iterators run sequentially with PSTL

[redi at gcc dot gnu.org]

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

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #7)
>     = std::__or_<std::is_base_of<std::random_access_iterator_tag,

Oops, that should be __and_ of course.

[Bug libstdc++/110512] C++20 random access iterators run sequentially with PSTL

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
   Target Milestone|---                         |14.0
           Assignee|unassigned at gcc dot gnu.org      |redi at gcc dot gnu.org

[Bug libstdc++/110512] C++20 random access iterators run sequentially with PSTL

[redi at gcc dot gnu.org]

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

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Patch posted for review:
https://gcc.gnu.org/pipermail/gcc-patches/2024-January/642732.html

[Bug libstdc++/110512] C++20 random access iterators run sequentially with PSTL

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|14.0                        |14.2

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 14.1 is being released, retargeting bugs to GCC 14.2.