“That linked quicksort paper is pretty cool: Vectorized and performance-portable Quicksort - for sorting floats/integers the speedup against std::qsort is around 10x.”
Vectorized and performance-portable Quicksort
跨七种指令集的 SIMD 快排 vqsort,比标准库快达 20 倍
提出 vqsort:把向量化快速排序整合进并行排序器 ips4o,几何平均加速 1.59 倍,同一实现可跑在七种指令集(含 SVE、RISC-V V)和四个平台上,支持浮点及 16–128 位整型键。论文还给出紧凑、免转置的寄存器内排序网络和对对抗输入稳健的向量友好枢轴采样策略,并称在非元组键上是 CPU 上最快的排序。
HN 上的人把它当作 SIMD 排序大幅快于 std::qsort 的实证,也用来讨论 Highway 库的实现和多路分区的取舍。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“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.”
“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”
“We instead fuse those two steps, see Vectorized and performance-portable Quicksort.”
“which has an associated paper at Vectorized and performance-portable Quicksort.”
- Vectorized and performance-portable Quicksort (2022) ↗tosh · 2024-02-12 · 2 分