c - thrust::reduce_by_key 性能，关键重复次数很少

Question

我必须使用许多不同的键对数组进行键控缩减，这些键偶尔会重复一次:

keys =  {1,2,3,3,4,5,6,7,7, 8, 9, 9,10,11,...}
array = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,...}

// after reduction
result = {1,2,7,5,6,7,17,10,23,13,14}

使用 thrust::reduce_by_key(或任何其他分段缩减方法)并不是最快的选择，因为大多数操作实际上只是从一个数组复制到另一个数组。

解决这个问题的更好方法是什么？

Answer 1

实际上，reduce_by_key 是适合此处使用的算法。只是当前在 Thrust 中的实现并没有达到预期的速度。详细来说，没有什么可以阻止 reduce_by_key 以 memcpy 速度执行，我相信 other implementations已经达到那个速度了。我们对 Thrust v1.7 的暂定计划包括使用相关 back40computing 中的代码对 reduce_by_key 和其他基于扫描的算法进行性能改进。项目。

请注意，当段是 (1) 长或 (2) 统一长度时，可能比 reduce_by_key 做得更好。例如，在某些时候使用基于偏移量的段描述符比键或头标志更经济。但是，当段很短(如您的情况)或长度变化很大时，最佳的 reduce_by_key 实现确实是完成这项工作的最佳工具。