Engineering In-place (Shared-memory) Sorting Algorithms
Engineering In-place (Shared-memory) Sorting Algorithms
复制标题
DOI：
10.1145/3505286
复制
发表时间：
2022-03-01
影响因子：
1.6
通讯作者：
Sanders, Peter
中科院分区：
文献类型：
--
作者：
Axtmann, Michael;Witt, Sascha;Sanders, Peter
我们提出了新的顺序和并行排序算法，这些算法目前代表了针对广泛的输入规模、输入分布、数据类型和机器的已知最快技术。有些令人惊讶的是，部分速度优势归因于算法的额外特性，即原地工作，也就是说，它们除了输入数组之外不需要大量空间。以前，原地特性往往意味着性能损失。我们的主要算法贡献是一种分块的原地数据分布方法，经证明它具有高效的缓存利用率。我们还考虑到动态负载平衡和内存局部性对这种方法进行了并行化。
我们新的基于比较的算法——原地并行超标量样本排序（IPS(4)o）将这种技术与无分支决策树相结合。通过考虑有许多相等元素的情况，并动态调整分布程度，我们得到了一种高度稳健的算法，它比之前最好的原地并行基于比较的排序算法快了近三倍。无论我们考虑原地还是非原地、并行还是顺序设置，该算法都优于最好的基于比较的竞争对手。
另一个令人惊讶的结果是，IPS(4)o在很多情况下甚至优于最好的（原地或非原地）整数排序算法。在许多其余的情况中（通常涉及接近均匀的输入分布、小键值或顺序设置），我们新的原地并行超标量基数排序（(IPSRa)-Ra-2）被证明是最好的算法。
很多论文都声称拥有在某种意义上“最好”的排序算法，但不可能所有的声称都是真的。因此，我们的结论基于一项广泛的实验研究，该研究涉及21种最先进的排序代码、6种数据类型、10种输入分布、4种机器、4种内存分配策略的大部分交叉组合，以及跨越7个数量级的输入规模。这证实了我们关于算法稳健性能的说法，同时揭示了许多竞争对手在相关出版物所报告的具体测量集之外存在的主要性能问题。对于整数排序算法来说尤其如此，这为在稳健的通用排序中更倾向于基于比较的算法提供了一个理由。
We present new sequential and parallel sorting algorithms that now represent the fastest known techniques for a wide range of input sizes, input distributions, data types, and machines. Somewhat surprisingly, part of the speed advantage is due to the additional feature of the algorithms to work in-place, i.e., they do not need a significant amount of space beyond the input array. Previously, the in-place feature often implied performance penalties. Our main algorithmic contribution is a blockwise approach to in-place data distribution that is provably cache-efficient. We also parallelize this approach taking dynamic load balancing and memory locality into account.Our new comparison-based algorithm In-place Parallel Super Scalar Samplesort (IPS(4)o), combines this technique with branchless decision trees. By taking cases with many equal elements into account and by adapting the distribution degree dynamically, we obtain a highly robust algorithm that outperforms the best previous in-place parallel comparison-based sorting algorithms by almost a factor of three. That algorithm also outperforms the best comparison-based competitors regardless of whether we consider in-place or not in-place, parallel or sequential settings.Another surprising result is that IPS(4)o even outperforms the best (in-place or not in-place) integer sorting algorithms in a wide range of situations. In many of the remaining cases (often involving near-uniform input distributions, small keys, or a sequential setting), our new In-place Parallel Super Scalar Radix Sort ((IPSRa)-Ra-2) turns out to be the best algorithm.Claims to have the - in some sense - "best" sorting algorithm can be found in many papers which cannot all be true. Therefore, we base our conclusions on an extensive experimental study involving a large part of the cross product of 21 state-of-the-art sorting codes, 6 data types, 10 input distributions, 4 machines, 4 memory allocation strategies, and input sizes varying over 7 orders of magnitude. This confirms the claims made about the robust performance of our algorithms while revealing major performance problems in many competitors outside the concrete set of measurements reported in the associated publications. This is particularly true for integer sorting algorithms giving one reason to prefer comparison-based algorithms for robust general-purpose sorting.