<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/63447>63447</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            C++20 random access iterators run sequentially with PSTL
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          gonzalobg
      </td>
    </tr>
</table>

<pre>
    This snippet runs sequentially:

```cpp
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:
 
```cpp
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;
};
```

I'm not very happy with this workaround. I think that the fundamental issue is that there are no execution policy overloads of the algorithms in `std::ranges`, but that will take a while to fix, and given the impact this is having in practice, I'd like to discuss if there are better ways to improve this until then.

@ldionne @philnik777 What do you think?


<details>
<summary>Self-contained Reproducer</summary> 

```cpp=
#include <chrono>
#include <iostream>
#include <vector>
#include <algorithm>
#include <ranges>
#include <execution>
 
#if defined(TBB_STDPAR_THREADS)
#include <oneapi/tbb/global_control.h>
#include <tbb/parallel_for.h>
#endif
 
namespace stdv = std::views;
namespace stde = std::execution;
 
template <typename F>
void bench(const char* name, F&& f, size_t sz) {
  f();
  // Measure bandwidth in [GB/s]
  using clk_t = std::chrono::steady_clock;
  auto start = clk_t::now();
  int nit = 100;
  for (int it = 0; it < nit; ++it) f();
  auto seconds = std::chrono::duration<double>(clk_t::now() - start).count(); // Duration in [s]
 
    // Amount of bytes transferred from/to chip.
  auto gigabytes = static_cast<double>(sz * sizeof(double)) * 1.e-9;
  auto gb_moved = (gigabytes * nit); // GB
  std::cerr << name << ", Total size [GB]: " << gigabytes << ", Bandwidth [GB/s]: " << (gb_moved / seconds) << std::endl;
}
 
int main(int argc, char *argv[]) {
  // Read CLI arguments, the first argument is the name of the binary:
  if (argc != 2) {
    std::cerr << "ERROR: Missing length argument!" << std::endl;
 return 1;
  }
 
  // Read length of vector elements
  long long n = std::stoll(argv[1]);
 
  #if defined(TBB_STDPAR_THREADS)
 std::cerr << "TBB STDPAR THREADS = " << TBB_STDPAR_THREADS << std::endl;
    oneapi::tbb::global_control g(oneapi::tbb::global_control::parameter::max_allowed_parallelism,
 TBB_STDPAR_THREADS);
    (void)g;
  #endif
 
  // Allocate the vector
  std::vector<double> x(n, 0.), y(n, 0.);
 auto sz = x.size() + y.size();
 
  constexpr auto e = stde::par_unseq;
  std::for_each_n(e, x.data(), x.size(), [x = x.data(), y = y.data()](auto& e) {
    ptrdiff_t i = &e - x;
    x[i] = 1.0;
 y[i] = 2.0;
  });
 
 
  auto for_each = [&] {
      auto ids = stdv::iota((int)0, (int)x.size());
      std::for_each(stde::par_unseq, ids.begin(), ids.end(), [x = x.data(), y = y.data()](int i) {
 x[i] = y[i];
      });
  };
  bench("for_each", for_each, sz);
 
  auto copy = [&] {
      std::copy(e, x.data(), x.data() + x.size(), y.data());
  };
  bench("copy", copy, sz);
  return 0;
}
```

</details>
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJy8ON1u4zrOT6PeEA0SuUmai140SXPOAebgG3QKfJeGYtOOtrLkkeS07tMvKDmOnaZzBrvADgapJf6IpPgnCudkqREf2HzN5tsb0fiDsQ-l0R9CmX15szd5-_BykA6clnWNHmyjHTj82aD2UijVsuSRTbdsevpdTOP_rK7jjvM54SSPR8y8sSzZSO1Z8gTvjN9rxleMb6A9fSfrSCUab0DmDliyhTMLiW8ufkrjBeP3jN8TO76aEpt-9T5x8gMDfDVk23MqjE1RZAfG7_s9fMes8dLouKyFTRvt8Cdxlrmb7LGU-sQzbqHOzxtsvn4P8r5PctFJF7ULu-1wd76NsoJkfAVs2ckHAPDO5mvJ5ttI1C16DdhyO1Sot_fwEv7yaIU31kFhTQUbxteMr_kUrNAlOqhMjgr8AQcgtphaoXNTpSLL0LlUdkzYYgqZ0RnWnnTZNx5yA9p40EiIwkrVwkEcEQREFhBZwIkFeFFO4OWALQiLgdZiZkotPzCHfRtE-f7j5RsI9wULR3dLZxfGvgmbnwGdjTPROKnLwKoWViiFCoQqjZX-UDnwBgqhFOxF9kqLsw9Df--ToRGD25Pny1LLQmZCe9WCrGqR-f4gtIWxldAZKZ-ZplYIpgAlbInw5_cNiLpWMhPE3Y3YP8LPRmavIHQOubS-hTdjX4U1jc7pWG_ommTR0s3UzivGd1FQY10qq1q5yaGu6XbIgtlB6PIk1td3mWxOvvHS1siSJ6L3pg9i-CqKPVa1Eh6BJRvf1qhFhZBeMutizDaZhzSVLv1SjEvScQg4L7zMyO2cx_fawt4YBUehGgxRQUHUycvvCcb4qg9j6VInKkyPQ1HP0O7c1FshvbsiygVeJjyWxrbkZD2X63qlXpS9GaD7x5YbttwMBI0c_oHVNbl6tsMEQGvSMsdioKT2WFqh0mBBQfl2E0_fRCuSxX1gO0grv84pjC-rELpHtBTvdd3Cm_QH8BQoZ-edwF-0pV_BH4QP_lg0OhcVai8USOcaDA7eQS12SeEch1AbJbMWzBGtMiJ3FFPEaBDPUpObD61YoiOZuxwV2L9JpcCLV4rOt4NUGNKAfCckCrxSHlEHzjGuoy7SUTqjYJIaakvxniGRkA1yUPI18MmlyxpKUcVAjT16jxbeRBtCWFa1NUeMfBvtZUi740TD7qYql0ZrBHY3rQ9Safm6XC7h_0mF3EBrmmhRluxGhPE32eTohVSu9xGWbFxTVcK2LHn6gaq4zYz2QmrM4Rlra_ImQ3IxxndnRPiyjifbbpMnUmeqyUMayA7WaHM-dASUxnmLovoCfOoFrgL7W_4C3t31deCgiD-NcxpPZAE5FmQGxu9f1uv0x8v2--Nz-vLn89Pj9geF1RWORqOoJeM7v98zviuV2cfI8taoyeELOSLyqRKlhbFjVNS5LEYCUp5ytchCsjpebXzWVzBxjDnQfz1ifzWD73qRjkbmsEcdWqKQNqimWMYfgTDJ_XeMLxhfQBFSofzA1IP7uOhfiq7BOecnxneM7-BvFK6hCBE6f5O5P4QQnq__WJMXUovT4cc6nqnX1I9VOzlcTJ8o8jbNlMleB2eFttF5YSNpYBIJtHn7JBn1X1pG1Nl0OoAUxsKpQYtwgsbvDdHQKvZOkvrNK2pHUTAz-rKLHeqRN1bE29rkptmrkOj5_TXB4TZqxvhqkpmG-tzuyJOJtx2zzrIDow5rR0B9rIgD5dV969GBt0K7Aq3FPDSN5O4GsoOsJyOFSlmKSBFVojqdZsL5CwXcB5DrkJcYsk0HC914gMwmePvJXOU-rcwR81ORH5xGfhhMPdD3j576bFu0lu4oXBN5ePfNOCevfTFUg0iqzvWos6Yugp8QhwoOKde92458dkxMIvcq8N3p-oPOEeMcpzpXo-o7vCjyu0qExwZ9Cltmocc9CHLLR2HLY3yyXQRfZ5dnFDlsvv1FhA3VXUfUoRJL63y_HcswRkN1JXYvdSgHj32QFKQWiQCMz-hi-Kcny1XzM86fnp__75ls9Ld0IaoV6tIfegGI4dl6120DFn1jNcyGKWV56dhDzbtDTAGxzAAqjFbokJUhUehHjyPTeaNU1JYMPIsWvsykdNpv15IvbfOyXkOkgY6m8_reHp-5_oOlAKArVgFIJSh8jEsWlIzf_wZe_woWFXpqF2hZifdUKGXeME9PxU26ivFNJ8N1UwxFZPyeig3jq3JUJa6UxHO6UspQIx5ctGseLkO_ny_0eeg0YtjAdDIeNJx2-vNjtv7onu_n4QEleWiH04RPznB-pQQmfT3GyzFC8jldncYQKYV6KLKXs4PxJOM_GDKQUFS18VPU1t7msihSD7JzvQXCLbyPbms0jZhNBkWyHUL4EAIXQwq4sFiw00n1ePR8Tc0FMRtK2KEO5kDH_2b6E1l-MQP6dF3_w6nPr0c-p3fk9qKvWg5RTq0b4_ysV6hc5-UmtmufXThYOTN1--vLOKcyU7dfO-x5HaLn0oNHFvk9jeJ5QZv4-UmTU5WYfq6pV5-z8fFzfjjd5A9JvkpW4gYfZov75R1fLWbLm8PD3fI-m-0XyWKxwPlqOsvni4Iv51gs7uazAmc38oFPeTJdcD6b8sV8OSkWySpfzhYrkWeru7lgd1OshFQTpY7VxNjyJryBHxbJ3d3yRok9KhcmsJxrfIsPZFJ2vr2xD0Rzu29KR69E6bw7c_HSK3wYDfeuDs5so0cT2_hq__7j5dtNY9XDwfs6zFRDpi2lPzT7SRY6QDqq-3NbW_MvzDzjuyCgY3wXFPh3AAAA___UNIj5">