[DOC]: Document work complexity of Thrust/CUB algorithms

[jrhemstad]

Is this a duplicate?

• I confirmed there appear to be no duplicate issues for this bug and that I agree to the Code of Conduct

Is this for new documentation, or an update to existing docs?

New

Describe the incorrect/future/missing documentation

As a user of Thrust and CUB algorithms, I often want to know things like:

• Am I guaranteed that each element of the input range is accessed only once?
• Am I guaranteed that each element of the output is only written to once?
• Can my operator have side-effects?
• Can dereferencing my input/output iterator have side-effects?

All of these questions are inter-related and the answer is unique to each algorithm.

To address these questions, I would like for each Thrust and CUB algorithm to have a "Complexity" section similar to what cppreference has:

If this is a correction, please provide a link to the incorrect documentation. If this is a new documentation request, please link to where you have looked.

No response

[bernhardmgruber]

While I can understand the wish for more knowledge on the user side, there is a trade-off here, since promising too much about the implementation's behavior can also lock us out of future algorithmic evolution. Unless the complexity we advertise is pure documentation that we are allowed to break at any time :)

I vaguely remember Andrei Alexandrescu mentioning in a talk that there could be a faster implementation than the common ones for std::binary_search, but they would not fulfill the complexity guarantees of the STL. I couldn't find the talk right now, so it may just be a myth as well.

[jrhemstad]

promising too much about the implementation's behavior can also lock us out of future algorithmic evolution.

Oh I completely agree. I neglected to mention it, but I fully intended that the "Complexity" section for most algorithms may not make any guarantees at all. for_each is the one algorithm where we definitely need to make strong guarantees, but all the others may not.

The goal is just to give people that information on a per-algorithm basis.