“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]”
BlockQuicksort: How Branch Mispredictions don't affect Quicksort
分块比较并缓冲结果,使快速排序的划分几乎不产生分支预测失败
快速排序的划分步骤会因数据相关的条件分支而频繁预测失败。BlockQuicksort 把输入切成固定大小的块(建议 128 个元素),先把块内元素与枢轴的比较结果存入缓冲区,再在第二遍中重排元素,从而避免依赖比较结果的条件分支。作者证明了在静态分支预测器下的平均误预测次数上界,并在随机整数上比 GCC 的 C++ std::sort 快 80%,只在有序或近乎有序的输入等少数情形下 std::sort 更快。
评论者把它当作避免分支预测失败的排序算法代表,常和 pdqsort、super scalar sample sort 并提,也指出其分块划分的思想是后来 pdqsort 等实现的源头。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“for a simpler algorithm that's still much faster than quicksort in most cases, blockquicksort (BlockQuicksort, code: [LINK])”
“two particular advances in the last decade are of practical importance: one for sort and one for hash table.”
“This article is missing the important reference to the prior work by Edelkamp and Weiss, on branchless quicksort [1].”
“The first one is AFAIK originally from the BlockQuicksort paper BlockQuicksort section 3.2.”
- BlockQuicksort: How Branch Mispredictions Don't Affect Quicksort ↗ingve · 2016-04-26 · 3 分