NVIDIA / NVIDIA/cccl

Slow thrust::distance called for for_each with C++20 iterators

Open
#846 4 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
2.5k
Forks
487
Avg merge
2d 7h
Merged PRs (30d)
296

Description

Example:

```c++
#include
#include
#include

int main()
{
auto l = std::views::iota(0, 1);
thrust::for_each(thrust::device, l.begin(), l.end(), [](int) {});
return 0;
}
```

ends up:

- calling `thrust::distance` [here](https://github.com/NVIDIA/thrust/blob/24486a169a62a58ef8f824d3dc9613c006b6f5a7/thrust/system/cuda/detail/for_each.h#L98), however
- since the `iota_view::iterator` does not inherit from `std::random_access_iterator_tag`,
- `thrust::iterator_traversal::type()` return` `thrust::single_pass_traversal_tag`, and
- [this](https://github.com/NVIDIA/thrust/blob/24486a169a62a58ef8f824d3dc9613c006b6f5a7/thrust/system/detail/generic/distance.inl#L42) distance overload is called, which advances the iterator using a `while` loop.

This impacts users silently, e.g., when switching from `for_each_n` to `for_each`, introducing silent catastrophic performance cliffs. Therefore, I think it would make sense to explore whether there exists a small change that could bridge the gap between the current library designed for C++<=17 iterators, with the C++23+ world we live in.

My proposal would be to, as an extension supported by P2408, modify `thrust::iterator_traits` to compute the `iterator_category` as follows:
- When compiling in C++ < 20, keep logic as is.
- Otherwise,
- if the iterator inherits from an iterator category tag, pick that,
- else, if the iterator models any of the C++20 concepts, map that concept to the equivalent iterator category type.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.