请问一下topk算子的sorted参数

[houj04]

请提出你的问题 Please ask your question

文档中是这样写的：

https://www.paddlepaddle.org.cn/documentation/docs/zh/develop/api/paddle/topk_cn.html

sorted (bool，可选) - 控制返回的结果是否按照有序返回，默认为 True。在 GPU 上总是返回有序的结果。

https://www.paddlepaddle.org.cn/documentation/docs/en/develop/api/paddle/topk_en.html

sorted (bool, optional) – controls whether to return the elements in sorted order, default value is True. In gpu device, it always return the sorted value.

按照上面的说明，我理解是这样：不管这个参数传进来的是true还是false，内部一律当做true处理，即，返回的结果始终是有序的。

但是看代码实现，内部似乎根据sorted这个参数，进行了判断，并不是直接忽略这个参数。
https://github.com/PaddlePaddle/Paddle/blob/develop/paddle/phi/kernels/gpu/top_k_kernel.cu

想问一下这个是符合预期的吗？

我之所以要问这个问题，背景是：我在实现某个硬件设备上的topk算子。当sorted参数为true的时候，语义很明确，排序之后输出即可。但是当sorted参数为false的时候，我应该如何输出呢？是可以仍然按照排序之后的输出，还是必须打乱顺序输出？直观上感觉是，不管是否sorted，都按照排序之后的输出即可。所以想确认一下。

[Hongqing-work]

如果之前本身就是用排序算法实现这里就不需要再乱序了，可以注意一下后续新硬件的文档描述，这里设置sorted参数是在做加强保证，相当于一种"make sure"。

这里存在差别的核心原因就是不同硬件对topk的实现方式不同。cpu上是调用的std::nth_element，该算法不保证排序，加上sorted参数能在该算法之后再进行一个保证；而gpu上是调用的phi::funcs::SortTopk，底层直接使用了cub::DeviceSegmentedRadixSort，所以不管有没有sorted参数，结果都是一定保证排序的。这里贴的代码段是对大规模情况下的优化，实验后其实大规模下GPU也不保证排序，后续文档需要修正。你面对的背景和未优化过的GPU场景类似，不需要考虑false的场景了，可以加以注释说明。

[Hongqing-work]

另外，这段代码产生自对大规模topk的优化，见PR40941，这种优化可能不保证排序，所以又引入了这个参数，这也是为什么只会在这一小段有额外sort操作。新硬件实现的话也需要考虑下之后扩展的情况，建议适当注释一下以供后面扩展。
文档的问题后续会考虑再修正优化下，感谢指出。

[Hongqing-work]

GPU未能保证排序的场景如下，条件为input_width >= 1024 && in_dims.size() == 1

>>> import paddle
>>> data_1 = paddle.rand([32000])
>>> value_1, indices_1 = paddle.topk(data_1, k=30, sorted=False)
>>> value_1
Tensor(shape=[30], dtype=float32, place=Place(gpu:0), stop_gradient=True,
       [0.99975669, 0.99968195, 0.99975473, 0.99968398, 0.99939889, 0.99974710,
        0.99998403, 0.99943805, 0.99978644, 0.99965405, 0.99929762, 0.99961352,
        0.99991608, 0.99972552, 0.99980104, 0.99943984, 0.99975103, 0.99928349,
        0.99954355, 0.99991471, 0.99991655, 0.99998146, 0.99950898, 0.99945062,
        0.99976182, 0.99974698, 0.99962926, 0.99949092, 0.99945098, 0.99925196])
>>> value_2, indices_2 = paddle.topk(data_1, k=30)
>>> value_2
Tensor(shape=[30], dtype=float32, place=Place(gpu:0), stop_gradient=True,
       [0.99998403, 0.99998146, 0.99991655, 0.99991608, 0.99991471, 0.99980104,
        0.99978644, 0.99976182, 0.99975669, 0.99975473, 0.99975103, 0.99974710,
        0.99974698, 0.99972552, 0.99968398, 0.99968195, 0.99965405, 0.99962926,
        0.99961352, 0.99954355, 0.99950898, 0.99949092, 0.99945098, 0.99945062,
        0.99943984, 0.99943805, 0.99939889, 0.99929762, 0.99928349, 0.99925196])

value_1未保证排序输出，value_2已强制排序。