NVIDIA / NVIDIA/cccl

Semantics of thrust::minmax_element do not match those of std::minmax_element

Open
#762 1 comment 0 reactions 1 assignee Claimed by @griwes View on GitHub
nvbug thrust
Dominant language
C++
Stars
2.5k
Forks
487
Avg merge
2d 7h
Merged PRs (30d)
296

Description

The Thrust documentation for thrust::minmax_element ( https://thrust.github.io/doc/group__extrema_ga08dbf5a0046858f3a182895919eb620c.html ) states:
It returns a pair of iterators (imin, imax) where imin is the same iterator returned by min_element and imax is the same iterator returned by max_element.

The iterator for the maximum element that is returned does not match the behavior of std::minmax_element when there are multiple elements with the same maximum value.

The description of std::max_element ( https://en.cppreference.com/w/cpp/algorithm/max_element ) states:
If several elements in the range are equivalent to the greatest element, returns the iterator to the first such element.
(and the description of thrust::max_element matches that).

The description of std::minmax_element ( https://en.cppreference.com/w/cpp/algorithm/minmax_element ) specifies a different behavior for the maximum element when there are duplicate values:
If several elements are equivalent to the largest element, the iterator to the last such element is returned.
(There is a footnote in the standard ( http://eel.is/c++draft/alg.min.max#footnote-235 ) explaining that this behavior of minmax_element is intentionally different from the behavior of max_element.)

This bug in thrust::minmax_element is causing problems with PGI's implementation of parallel algorithms on the GPU, where thrust::minmax_element is used to implement std::minmax_element, resulting in "std::minmax_element(std::execution::par, ...);" having the wrong behavior. This bug was caught by the Intel pSTL test suite. The best workaround in the PGI pSTL code that I can think of is to implement the GPU std::minmax_element as a call to thrust::min_element and a separate call to thrust::max_element with reverse iterators.

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.