按年被提到
20172017 · 2 次2026
算法与数据结构›经典算法与数据结构·arXiv:1705.02257 · cs.DC

In-place Parallel Super Scalar Samplesort (IPS$^4$o)

Michael Axtmann, Sascha Witt, Daniel Ferizovic, Peter Sanders · 2017
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2017-06-30 · 最近 2020-05-17
2不同的人
3活跃月份
3讨论串
6被引(OpenAlex)
arXiv 摘要(候选层不写导读)

We present a sorting algorithm that works in-place, executes in parallel, is cache-efficient, avoids branch-mispredictions, and performs work O(n log n) for arbitrary inputs with high probability. The main algorithmic contributions are new ways to make distribution-based algorithms in-place: On the practical side, by using coarse-grained block-based permutations, and on the theoretical side, we show how to eliminate the recursion stack. Extensive experiments show that our algorithm IPS$^4$o scales well on a variety of multi-core machines. We outperform our closest in-place competitor by a factor of up to 3. Even as a sequential algorithm, we are up to 1.5 times faster than the closest sequential competitor, BlockQuicksort.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论lorenzhs · 2017-06

“To illustrate the point about branch misprediction, I implemented quicksort with intentionally skewed pivot selection. You can see the results here: https://github.com/lorenzhs/quicksort-pivot-imbalance For this demo I'm sorting a permutation of the range 1 to n, so obtaining perfect or arbitrarily skewed pivots is free, which isn't realistic, but that's…”

Pattern-defeating quicksort原评论 ↗
评论lorenzhs · 2017-06

“Don't count out sample-sort just yet, it lends itself to parallelisation very well and is blazingly fast. See https://arxiv.org/abs/1705.02257 (to be presented at ESA in September) for an in-place parallel implementation that overcomes the most important downsides of previous sample-sort implementations (linear additional space).”

Pattern-defeating quicksort原评论 ↗
评论lorenzhs · 2018-08

“Especially when targeting realistic machine models, there are a lot of things that are suboptimal about the classical sorting algorithms like quicksort or mergesort. For example, a quicksort with perfect choice of pivot will incur a branch miss with probability 50% for every element. That's not something classical complexity analysis measures, but on actu…”

On the Worst-Case Complexity of TimSort原评论 ↗
评论ipsofacto · 2020-05

“There's an even better branch-free (super scalar) sorting algorithm: "In-place Parallel Super Scalar Samplesort (IPS4o)" which we started using: https://github.com/SaschaWitt/ips4o https://arxiv.org/abs/1705.02257 As an example, to sort 10 million random longs on my computer it takes std::sort 766 ms (roughly in line with Andrei's numbers) and ips4o::s…”

Lomuto's Comeback原评论 ↗