按年被提到
20162023 · 2 次2026
算法与数据结构›经典算法与数据结构·arXiv:1604.06697 · cs.DS

BlockQuicksort: How Branch Mispredictions don't affect Quicksort

BlockQuicksort:分支预测失败如何不再影响快速排序
Stefan Edelkamp, Armin Weiß · 2016

分块比较并缓冲结果,使快速排序的划分几乎不产生分支预测失败

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 5 人首次 2016-04-26 · 最近 2023-06-10
5不同的人
6活跃月份
6讨论串
7被引(OpenAlex)

快速排序的划分步骤会因数据相关的条件分支而频繁预测失败。BlockQuicksort 把输入切成固定大小的块(建议 128 个元素),先把块内元素与枢轴的比较结果存入缓冲区,再在第二遍中重排元素,从而避免依赖比较结果的条件分支。作者证明了在静态分支预测器下的平均误预测次数上界,并在随机整数上比 GCC 的 C++ std::sort 快 80%,只在有序或近乎有序的输入等少数情形下 std::sort 更快。

HN 为什么提它

评论者把它当作避免分支预测失败的排序算法代表,常和 pdqsort、super scalar sample sort 并提,也指出其分块划分的思想是后来 pdqsort 等实现的源头。

方法难度 3 / 5约 40 分钟经得起时间
读之前最好知道
1快速排序(Quicksort)及其划分
2CPU 分支预测与流水线
3算法平均复杂度分析
4C++ std::sort 与缓存/内存层次基础

HN 书评

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

“You should rather look at sorting algorithms which don't suffer from branch mispredictions (as much), such as pdqsort, super-scalar sample sort [1,2] or block quicksort [3]”

建议改用少受分支预测失败影响的排序,如 block quicksort
Pattern-defeating quicksort原评论 ↗
推荐lorenzhs · 2018-08

“for a simpler algorithm that's still much faster than quicksort in most cases, blockquicksort (BlockQuicksort, code: [LINK])”

推荐 blockquicksort,更简单且多数情况比快排快得多
On the Worst-Case Complexity of TimSort原评论 ↗
推荐sanxiyn · 2023-05

“two particular advances in the last decade are of practical importance: one for sort and one for hash table.”

把 BlockQuicksort 列为近十年对排序有实际价值的进展
Ask HN: What is new in Algorithms / Data Structures these days?原评论 ↗
引用nightcracker · 2021-07

“This article is missing the important reference to the prior work by Edelkamp and Weiss, on branchless quicksort [1].”

指出文章漏引 Edelkamp 和 Weiss 的无分支快排工作
Do Low-Level Optimizations Matter? (2020)原评论 ↗
引用Voultapher · 2023-06

“The first one is AFAIK originally from the BlockQuicksort paper BlockQuicksort section 3.2.”

指出块分区思想最初出自这篇论文 3.2 节
10~17x faster than what? A performance analysis of Intel x86-SIMD-sort (AVX-512)原评论 ↗
被提交为 story · 1 次