Parallel C++ algorithms run sequentially

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.

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.

See PR 100070. This is basically the same issue, but for PSTL.

@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?

Oh I forgot we approved that one

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

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.

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>>...>;

(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.

Patch posted for review:
https://gcc.gnu.org/pipermail/gcc-patches/2024-January/642732.html