Unfortunately, unlike median, the kthvalue documentation does not mention its possible nondeterminism. I think the nondeterminism occurs if there are multiple valid kth values, in which case any index can be returned. This PR should probably update the documentation to reflect this, too.

Is it really only kth value on CUDA that has this issue? If so, we should be explicit about which indices the CPU version will return in the documentation.

Thanks for the extra details! Do you know if there is an issue somewhere describing the nondeterminism of kthvalue? I only put the alert in the CUDA version because in a comment above, you said "kth value on CUDA."

I don't know if there's an issue for kthvalue, sorry. We could always file an extra one and resolve it as a duplicate later if it is redundant.

That's true, and it probably is just CUDA, but it might be worth checking and documenting the CPU behavior.

Ok I understand kthvalue's nondeterminism more clearly now after writing a test: https://github.com/kurtamohler/pytorch-perf-test-scripts/blob/master/determinism_test/kthvalue_determinism.py

In the cases I tried, CPU looks like it could be deterministic, but CUDA is not, depending on the inputs. Results are below.

Aside from determinism, there's another interesting aspect--the uniqueness of the k-to-index mapping. If the input has N duplicate elements, do we get a unique index output from kthvalue for each corresponding k argument?

For example, with an input tensor a = torch.tensor([0.12, 3.4, 0.12, 5.2]), we have duplicate 0.12 elements at index 0 and 2. The k arguments for these are 1 and 2, since 0.12 would be at indices 0 and 1 after sorting the tensor. The question is, when we call a.kthvalue(1) and a.kthvalue(2), do the outputs of those calls always give two different index values, 0 and 2? If so, then we can say that the k-to-index mapping is unique, because each k value will give a different index. CPU gave me unique mappings for each case I tried. CUDA never gave me unique mappings for duplicates, but for some inputs the mapping was at least consistent (and thus deterministic). For an example of a consistent but not unique mapping, in the above simple example, imagine that a.kthvalue(1) and a.kthvalue(2) both always return an index of 0.

device size number-of-copies k-to-index-unique-mapping maybe-deterministic
cpu 20 1 True True
cpu 20 2 True True
cpu 20 5 True True
cpu 20 10 True True
cpu 20 11 True True
cpu 100 1 True True
cpu 100 2 True True
cpu 100 5 True True
cpu 100 10 True True
cpu 100 11 True True
cpu 1000 1 True True
cpu 1000 2 True True
cpu 1000 5 True True
cpu 1000 10 True True
cpu 1000 11 True True
cpu 10000 1 True True
cpu 10000 2 True True
cpu 10000 5 True True
cpu 10000 10 True True
cpu 10000 11 True True
cuda 20 1 True True
cuda 20 2 False True
cuda 20 5 False True
cuda 20 10 False True
cuda 20 11 False True
cuda 100 1 True True
cuda 100 2 False True
cuda 100 5 False True
cuda 100 10 False True
cuda 100 11 False True
cuda 1000 1 True True
cuda 1000 2 N/A False
cuda 1000 5 N/A False
cuda 1000 10 N/A False
cuda 1000 11 N/A False
cuda 10000 1 True True
cuda 10000 2 N/A False
cuda 10000 5 N/A False
cuda 10000 10 N/A False
cuda 10000 11 N/A False

I have some questions about what to do next:

• My tests do not show that CPU is nondeterministic, but that doesn't mean that we can be sure that it isn't. Should we just assume that CPU is nondeterministic and add the alert, or should we leave it alone until someone finds a nondeterministic case?
• I can document what I know about CUDA's nondeterminism. What about the question of unique k-to-index mappings? Is that important or useful for users to know?

Please check cpu implementation for the sources of nondeterminism, it's a question to which we can know the exact answer.
As for cuda, there are no guarantees of consistent mapping, any of the indices corresponding to a particular value can be returned. It may appear deterministic on some hardware/small examples, but don't be deceived by it.

I read through the kthvalue CPU code, and I don't see anything that would be an obvious source of nondeterminism, as far as I can tell. There is a parallel aspect of kthvalue CPU, but it's just for splitting up the separate arrays that need to be sorted (which happens if the input tensor has more than one dimension), so it is not a source of nondeterminism. On each array, a serial quicksort algorithm is used and then the kth value is pulled from the sorted array. The quicksort looks deterministic to me: https://github.com/pytorch/pytorch/blob/master/aten/src/ATen/native/Sorting.cpp#L36

Again I don't think we want to model a decorator as using dunder init and dunder del. There are some examples of different kinds of Pythonic decorators in https://github.com/pytorch/pytorch/blob/master/torch/testing/_internal/common_device_type.py that may be interesting to look at.

I've changed CuBLASConfigGuard to act like a context manager

This doesn't appear to be called anywhere?

Only if the input is CUDA, though.

"When :attr:`input` is on CUDA and there are multiple valid :attr:`k`th values, this function may nondeterministically return :attr:`indices` for any of them."

Index_copy_ needs a note, too:

https://pytorch.org/docs/master/tensors.html?highlight=index_copy#torch.Tensor.index_copy_

but median already has one:

https://pytorch.org/docs/master/generated/torch.median.html?highlight=median#torch.median

Please elaborate in this comment that tests using this wrapper need to start a subprocess (how and why) so that their cuBLAS is initialized with the new workspace config