NVIDIA / NVIDIA/cccl

Relax input type requirements for thrust::merge

Open
#808 1 comment 1 reaction 1 assignee Claimed by @gevtushenko View on GitHub
thrust
Dominant language
C++
Stars
2.5k
Forks
486
Avg merge
2d 6h
Merged PRs (30d)
295

Description

`thrust::merge` states this requirement:

> InputIterator2 and InputIterator1 have the same value_type

https://thrust.github.io/doc/group__merging_ga3d2776685a00dca265399f411784acec.html

cppreference for `std::merge` has a slightly more relaxed requirement:

> The signature of the comparison function should be equivalent to the following:
> bool cmp(const Type1 &a, const Type2 &b);
> The types Type1 and Type2 must be such that objects of types InputIt1 and InputIt2 can be dereferenced and then implicitly converted to both Type1 and Type2. ​

https://en.cppreference.com/w/cpp/algorithm/merge

However, I can't find this requirement anywhere in the standard, so I don't know where `cppreference` is getting that from
* Current https://eel.is/c++draft/alg.merge
* C++17 https://timsong-cpp.github.io/cppwp/n4659/alg.merge

Furthermore, none of gcc/clang/msvc seem to actually require this:
https://godbolt.org/z/v1WcW5scv

The Thrust requirement stems from the fact that it loads elements from both input ranges into a single thread local, register array, thus requiring them to be the same type: https://github.com/NVIDIA/thrust/blob/7afdb87ad0e0a213a6f7e50548cbabc7e19f400f/thrust/system/cuda/detail/merge.h#L480-L485

A cursory look through the algorithm makes it seem like it wouldn't be too difficult to instead use two distinct storage arrays for each input range.

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.