按年被提到
20222022 · 3 次2026
算法与数据结构›经典算法与数据结构·arXiv:2205.05982 · cs.IR

Vectorized and performance-portable Quicksort

向量化且性能可移植的快速排序
Mark Blacher, Joachim Giesen, Peter Sanders, Jan Wassenberg · 2022

跨七种指令集的 SIMD 快排 vqsort,比标准库快达 20 倍

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 5 人首次 2022-06-08 · 最近 2024-03-01发表于 Software Practice and Experience
5不同的人
5活跃月份
6讨论串
13被引(OpenAlex)

提出 vqsort:把向量化快速排序整合进并行排序器 ips4o,几何平均加速 1.59 倍,同一实现可跑在七种指令集(含 SVE、RISC-V V)和四个平台上,支持浮点及 16–128 位整型键。论文还给出紧凑、免转置的寄存器内排序网络和对对抗输入稳健的向量友好枢轴采样策略,并称在非元组键上是 CPU 上最快的排序。

HN 为什么提它

HN 上的人把它当作 SIMD 排序大幅快于 std::qsort 的实证,也用来讨论 Highway 库的实现和多路分区的取舍。

方法难度 4 / 5约 50 分钟经得起时间
读之前最好知道
1快速排序与分区算法
2SIMD 向量指令(AVX、SVE 等)
3排序网络(sorting networks)
4CPU 缓存与并行排序
5C++ 高性能编程

HN 书评

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

“That linked quicksort paper is pretty cool: Vectorized and performance-portable Quicksort - for sorting floats/integers the speedup against std::qsort is around 10x.”

推荐这篇快速排序论文:对浮点数和整数排序比 std::qsort 快约 10 倍
Efficient and performance-portable vector software原评论 ↗
引用janwas · 2022-06

“In short, it turns out not to help for single core with vectors, but a few initial passes of ips4o (with 64..256-way partitioning) is faster for parallel sorts.”

指出多枢轴划分对单核向量化没帮助,但先做几轮 ips4o 对并行排序更快
Vectorized and performance-portable Quicksort原评论 ↗
引用inkyoto · 2022-06

“A recent paper from Google engineering has compared performance of a vectorised (SIMD) vs non-vectorised implementation of the quick sort in the Highway library”

引用 Google 这篇论文:Highway 库中 SIMD 快排比非向量化实现快 9 到 19 倍
Apple M2 Die Shot and Architecture Analysis – Big Cost Increase and A15 Based IP原评论 ↗
引用janwas · 2022-12

“We instead fuse those two steps, see Vectorized and performance-portable Quicksort.”

指出这篇论文把转置和列排序两步融合起来
Sorting with SIMD原评论 ↗
引用jhalstead · 2024-03

“which has an associated paper at Vectorized and performance-portable Quicksort.”

指出 Highway 库里的向量化快速排序有这篇相应论文
JPEG XL and the Pareto Front原评论 ↗
被提交为 story · 1 次