Highway VQSort 向量化排序实践指南构建、基准复现与 AVX-512 降频/启动开销研究【免费下载链接】highwayPerformance-portable, length-agnostic SIMD with runtime dispatch项目地址: https://gitcode.com/GitHub_Trending/hi/highway本文围绕 hwy/contrib/sort/README.md 展开系统讲解 Highway 贡献库中的向量化快排 VQSort 如何构建、复现基准测试CMake / Linux Bazel / AWS Graviton3 三套流程、如何解读bench_sort输出并结合 bench_sort.cc、vqsort.h、vqsort.cc 等源码深入小数组优化、AVX-512 降频与启动开销测量方法、以及与其他 SIMD 排序算法的对比结论帮助读者既会复现数据也理解数据背后的微观架构原理。性能定位VQSort 是 Highway 的向量化快速排序README 开篇给出的性能基准是自 2022-06-07 起VQSort 对内置类型大数组的排序速度约为 LLVMstd::sort的 10 倍作为参照2023-06 时 pdqsort 这类较新的标量算法约为std::sort的 2 倍。该结论出自 Highway 官方向量化快排的博文与论文arXiv: 2205.05982README 将其作为整个模块的锚点事实。在源码层面vqsort.h 头部注释给出了明确的使用建议// To ensure the overhead of using wide vectors (e.g. AVX2 or AVX-512) is // worthwhile, we recommend using this code for sorting arrays whose size is at // least 100 KiB. See the README for details.即宽向量AVX2 / AVX-512存在启动开销官方推荐输入至少 100 KiB 再使用 VQSort 才能获得正收益——这一建议正是后文AVX-512 启动开销研究的结论在 API 文档中的落地。公开 API 由三族函数组成均带SortAscending/SortDescending模板标签定义见 order.hVQSort(keys, n, order)对keys[0, n)全量排序分派到最佳指令集不分配内存栈开销约 1.2 KiBVQPartialSort(keys, n, k, order)部分排序使[0, k)成为[0, n)中最小的 k 个元素的有序排列VQSelect(keys, n, k, order)向量版快速选择使第 k 个位置落在全排序后的位置。重载覆盖uint16_t/32/64、int16_t/32/64、float16_t/float/double以及 128 位键类型uint128_t、K32V32、K64V64。其中浮点半精度与双精度需在VQSortHaveFloat16()/VQSortHaveFloat64()返回 true 时才能调用这两个函数查询的是 VQSort 库实际编译所覆盖的目标而非通用分派表。VQSort 不保持等价键的相对顺序非稳定排序。旧版Sorter类在 vqsort.h#L232-L300 中已标注为仅为二进制兼容保留官方推荐直接使用更简单的VQSort()接口。构建与复现三种平台的完整操作步骤README 提供三条路径复现基准结果。核心前提一致必须使用 ClangREADME 声明测试过 13.0.1 与 15.0.6若它不是默认编译器需通过环境变量指定export CCclang-15 export CXXclang-15CMake 流程任意平台Highway 顶层 CMake 构建即可。CMake 侧对 VQSort 有两处特殊处理可以从 CMakeLists.txt 确认VQSort 源码通过file(GLOB HWY_CONTRIB_SOURCES hwy/contrib/sort/vqsort_*.cc)收集CMakeLists.txt 第 226 行附近并显式列入hwy/contrib/sort/vqsort.cc、vqsort.h等目标VQSort 要求 C17若CMAKE_CXX_STANDARD 17会给出vqsort requires C17的警告。按 README 的标准工作流执行mkdir -p build cd build cmake .. make -j taskset -c 2 tests/bench_sort其中可选的taskset -c 2将基准进程钉在单个核上防止操作系统在核间迁移基准进程从而降低测量方差。Linux Bazel 流程README 还给出 Bazel 路径先经包管理器安装 golang 与 Clang测试版本 13.0.1go install github.com/bazelbuild/bazelisklatest git clone https://github.com/google/highway cd highway CCclang CXXclang ~/go/bin/bazelisk build -c opt hwy/contrib/sort:all bazel-bin/hwy/contrib/sort/sort_test bazel-bin/hwy/contrib/sort/bench_sort从 BUILD 文件可以核对这些目标的构成hwy/contrib/sort:all会构建vqsort24 个按类型 × 升/降序拆分的源文件如vqsort_f32a.cc、vqsort_i64d.cc注释说明拆分是为了降低 MSVC 构建时间、vqsort_for_test额外定义HWY_COMPILE_ALL_ATTAINABLE使sort_test能动态分派到所有目标以及bench_sort、sort_test、sort_unit_test等测试目标。intel与vxsort两个对比算法库目前在 BUILD 中源文件全部被注释是空壳占位说明当前默认构建不会链接第三方对比实现。AWS Graviton3SVE / NEON流程这一节是 README 中最完整的实操记录目标是 Graviton3c7g.8xlargeAmazon Linux 5.10 arm64最大 32 vCPU。两个关键坑与解法系统 CMake 过旧无法构建 LLVM需要先源码构建 CMake 3.23.2wget https://cmake.org/files/v3.23/cmake-3.23.2.tar.gz tar -xvzf cmake-3.23.2.tar.gz cd cmake-3.23.2/ ./bootstrap -- -DCMAKE_USE_OPENSSLOFF make -j8 sudo make install cd ..AWS 自带 Clang 11.1 会生成多余的AND指令使排序慢 1.15 倍因此需用 LLVM trunkREADME 记录测试时对应 Git hash8f6512fea000c3a0d394864bb94e524bee375069编译 Clanggit clone --depth 1 https://github.com/llvm/llvm-project.git cd llvm-project mkdir -p build cd build /usr/local/bin/cmake ../llvm -DLLVM_ENABLE_PROJECTSclang -DLLVM_ENABLE_RUNTIMESlibcxx;libcxxabi -DCMAKE_BUILD_TYPERelease make -j32 sudo make install随后安装 bazelisk 并构建注意--copt传入目标指令集sudo yum install go go install github.com/bazelbuild/bazelisklatest git clone https://github.com/google/highway cd highway CC/usr/local/bin/clang CXX/usr/local/bin/clang ~/go/bin/bazelisk build -c opt --copt-marcharmv8.2-asve hwy/contrib/sort:all bazel-bin/hwy/contrib/sort/sort_test bazel-bin/hwy/contrib/sort/bench_sortREADME 特别解释了 SVE 旗标的适用边界-marcharmv8.2-asve仅 Graviton3 可用要测同一颗处理器上的 NEON或其他 Arm CPU需把该选项改为--copt-marcharmv8.2-acrypto。作者同时指出一旦 Clang 对 NEON/SVE 内在函数像 x86 那样支持#pragma target这类手工旗标就不再必要。这段记录实际上揭示了 VQSort 的架构可移植性机制同一份 C 源码通过 Highway 的运行时分派per-target 编译与编译期目标旗标结合即可覆盖 x86 AVX2/AVX-512 与 Arm NEON/SVE。解读 bench_sort 输出bench_sort每行输出的字段依次为指令集AVX3 指代 AVX-512→排序算法std即std::sortvq即 VQSort→键类型f32即 float→键分布uniform32为 0 到 2^32 区间的均匀随机→键数量→吞吐量每秒输出的排序键字节数。源码中分布枚举定义在 algo-inl.h#L109enum class Dist { kUniform8, kUniform16, kUniform32 };。README 给出的 Xeon 6154Skylake-X3 GHz摘录[ RUN ] BenchSortGroup/BenchSort.BenchAllSort/AVX3 AVX3: std: f32: uniform32: 1.00E06 54 MB/s ( 1 threads) AVX3: vq: f32: uniform32: 1.00E06 1143 MB/s ( 1 threads)1143 MB/s 对 54 MB/s即该场景下约 21 倍吞吐注意这是单线程、100 万浮点键、均匀随机分布的单项数据与10 倍的总体表述口径不同。从 bench_sort.cc 的AlgoForBench()可见基准框架内置了多个可插拔对照算法kVQSort、kVXSort、kIntelx86-simd-sort、kIPS4O、kPDQ、kSort512、kSEA等由编译期宏HAVE_VXSORT、HAVE_INTEL、HAVE_PDQSORT等开关控制默认构建下主要对比 VQSort 与std::sort。基准的尺寸采样模式定义在 bench_sort.cc#L363-L421 的BenchmarkModes中与 README对比研究一节一一对应kDefault100 与 100K或 100M开启并行/SORT_100M时kSmallPow22、4、…、128 的 2 的幂用于隔离排序网络性能README 提到 x86-simd-sort 与 vxsort 都使用排序网络VQSort 同样在小输入走网络kPow1010、100、…、100K 的 10 的幂见 bench_sort.cc#L414-L418覆盖非 2 的幂尺寸以及排序网络 → 快排递归的交叉点kAllSmall、kPow4、k10K、k1M等供细分研究。小数组优化熵缓存、2D 矩阵排序网络与最小向量宽度README 明确说明 VQSort 最初聚焦大数组论文发表后针对小数组做了三类改进。每一条都能在源码中找到落点。每线程一次的熵种子TLS 缓存最初每次调用 VQSort 都从操作系统获取熵。不可预测的种子能避免快排最坏情况输入超过 100K 元素时其开销可忽略但对 100 或 1000 个元素的数组系统调用开销占比过高。修复方式是每线程只取一次熵、把种子缓存在 TLS 中显著改善后续调用性能用户也可显式初始化随机数生成器。源码印证vqsort-inl.h#L72-L80 的GetGeneratorStateStatic()使用thread_local uint64_t state[3]以state[2]作为是否已初始化的计数器0 表示未初始化仅首次调用时填充种子。安全熵来源的选择逻辑在 vqsort.cc#L56-L111Linux 上 glibc ≥ 2.25 / uclibc / musl 使用getrandom(bytes, 16, 0)注意 urandom 未初始化时可能阻塞Windows 使用CryptGenRandom其余平台回退到 vqsort-inl.h#L54-L70 的Fill16BytesStatic()——混合栈地址、代码地址与clock()时间戳。vqsort.h#L46-L51 的注释也写明约 1.2 KiB 栈 内部 3 字 TLS 随机状态缓存。顺带一提README 还记录了一处历史性能 bug外部贡献者 Lukas Bergdoll 的详尽性能分析发现每次调用都向 OS 取熵是瓶颈之一该问题在 Highway 的 PR #1334 修复——与上述 TLS 缓存的动机相互印证。短于半容量的输入避免转置的 2D 矩阵网络README 指出对短于排序网络半容量的输入旧实现把输入当作恒为 16 行的矩阵处理意味着至多 16 个元素时只有一个向量 lane 是活跃的。改进方案新增 8x2 与 8x4 网络在 lane 可用时激活更多 lane并针对极小输入新增 4x1 与 8x1 网络整体思路是把输入解释为 2D 矩阵从而避开代价高昂的转置。最小向量宽度加载旧实现按列数加载重叠的完整向量新实现改用恰好容纳列数的最小向量宽度在 Skylake 上提高了 IPC 并降低了非对齐加载的代价。代价是代码复用下降README 记录 VQSort 现在约 1500 条指令排序网络代码总量接近翻倍至 10.8 KiB、占总量的 70%。作者论证这一体积仍可舒适地放入 32 KiB 的指令缓存甚至可能落入微操作缓存DSB1500–2300 µop且并非所有指令都保证执行。这个体积换速度的权衡在微架构敏感场景如小数组高频调用值得参考。AVX-512 降频downclocking研究方法论与结论README 用一个完整的小节研究AVX-512 降频是否影响性能。其背景判断值得先交代此前社区对 AVX-512 降频的关注远超其实际影响——Daniel Lemire 2018 年测量的最坏情形也只见 3% 降幅Icelake 之后的 Intel CPU 与 AMD Zen4 受节流影响已小得多。真正的风险集中在早期 Silver/Bronze 级 Xeon而这些处理器面向入门计算/存储市场本就不是 VQSort 目标的高性能负载。测试环境与cold基准测试机为 Xeon Gold 6154Skylake 微架构是潜在受降频影响最大的架构之一Linux 6.1.20Clang 接近 LLVM trunk。作者新增了一个 cold 基准初始化随机种子 → 数组填常量、仅一个随机索引处填不同值 → 调用 VQSort → 打印一个随机元素防止计算被消除。构建命令# 构建时定义宏 cmake .. -DSORT_ONLY_COLD1 # 等价于编译定义 -DSORT_ONLY_COLD1 # 运行 taskset -c 6 setarch -R x86_64 perf stat -r 15 -d bench_sort命令各部分的意图在 README 中逐一说明taskset防线程迁移setarch -R关闭地址空间随机化-r 15让 perf 报告 15 次运行的离散度cycles、instructions、L1 dcache loads 的方差 1%LLC miss 方差 10%归因于机器上的残余后台活动。在 bench_sort.cc#L50-L52 可看到SORT_ONLY_COLD的定义与回退默认值 0BenchAllColdSort()bench_sort.cc#L73-L140实现与 README 描述逐条对应constexpr size_t kSize 10 * 1000的uint64_t栈上数组、items[Random32(rng) % kSize] ...只改一个随机位置、打印随机元素防消除以及在SORT_ONLY_COLD下以NanoSleep(100 * 1000 * 1000)睡眠 100 ms确保下一次运行时 CPU 已退出 AVX-512 模式。用 perf 报告的 GHz 建立上界测量口径是perf报告的 GHz不含内核时间短运行时有噪声README 也记录了sudo perf会报 Cannot allocate memory 的坑。该机器通过 MSR 关闭 Turbo Boost 并执行sudo cpupower frequency-set --governor performance抑制不必要的降频后AVX-512 代码实测 2.6–2.9 GHz相对 3.0 GHz 标称值。作者认为剩余差距可解释为内核时间尤其缺页处理与降频的叠加因此降频的上界为 (3−2.9)/3 到 (3−2.6)/3即 1.03–1.13 倍——相对于 512 位 SIMD 相比 256/128 位每周期工作量 2–4 倍的收益且后者通常不受降频影响完全可以忽略。控制变量确保对照二进制真的没有 AVX-512为收紧上界作者把 VQSort 与不含 AVX-512 的std::sort对照并系统排除了二进制其他部分混入 AVX-512的干扰库函数如memset会偷偷使用 AVX-512 且不会出现在自身二进制的反汇编中为此刻意避免调用这类函数数组零初始化在 clang-16 下通常编译成memset所以改为手动用Unpredictable1()的返回值初始化该函数实现不可见确认可编译为标量循环验证手段把初始化循环临时换成 AVX-512 store吞吐量从稳定的 9 GB/s 升至 9–15 GB/s——说明加入 AVX-512 后性能确实变化反证此前二进制没有使用 AVX-512换回标量初始化后三次运行中 VQSort 与std::sort的 GHz 区间分别为 2.8–2.9 与 2.8–2.8。结论在该 Skylake-X 单核上若有降频也低于测量噪声底且远低于 512 位 SIMD 可预期带来的任何加速。作者预期该结论可推广到 AMD Zen4 与 Gold/Platinum 级 Xeon。AVX-512 启动开销startup overhead研究上一节排除了降频但作者注意到排序前预热 AVX-512有明显收益于是单独立节研究启动成本。参照 Travis Downs 的公开测量Skylake 遇到 AVX-512 指令后会有 8–20 µs 的指令吞吐下降、可能的额外 10 µs 停顿然后才进入本研究中已证明可忽略的降频。冷/热对比数据作者选 10K 个无符号 64 位键使 VQSort 运行 7–10 µs——恰好排序结束时 AVX-512 还没完全预热。输入采用两值近似全相等分布BenchAllColdSort中的实现即数组全为同一值、仅一个随机索引不同这是刻意选择快排对全等分区可提前终止最好情况输入能放大启动开销的可见性否则它会被排序时间掩盖。冷启动标量初始化不预热五组各 15 次运行平均吞吐 9.3 GB/s即含启动成本共 8.6 µs热启动用慢速 scatter 指令初始化耗时约 100 µs充分覆盖预热期15.2 GB/s即无启动成本时 5.3 µs。冷/热比值仅 1.6且未出现 10 µs 硬停顿作者推测因为 VQSort 不用 SIMD 浮点与乘法指令。若按 Downs 的推测——Skylake 节流实际是把延迟向上取整到 4 的倍数——则 1.6 倍很合理VQSort 基本情形中大量跨 lane 或 64 位 min/max 指令在 Skylake 上延迟 3 周期其减速可能仅 1.3 倍而 1.6 倍可由7/8 的指令按 1.3 倍、1/8 的单周期指令按 4 倍粗略推得。滞后时间与对用户的实际含义CPU 无法预知未来指令为避免无谓的状态切换而设有滞后期最后一条 AVX-512 指令到关机的延迟Downs 测得 680 µs。因此基准每轮之间睡眠 100 ms。五组数据的最小二乘斜率中一负二正二平说明越早/越晚运行更占便宜不存在一致模式。对 VQSort 用户的工程含义README 原文的核心论点若周边代码平均每 500 µs 执行一次 AVX-512 指令AVX-512 保持活跃此时无论输入多小每次 VQSort 调用都直接受益。对按数据导向设计、已广泛使用 SIMD 的现代系统这是合理预期若把 VQSort 塞进尚不使用 SIMD 的遗留系统10K 输入下 VQSort 相对std::sort仍有 2.3 倍加速但随后的代码要吃 20 µs 启动期的节流按 README 的账——VQSort 8.6 µs 最多 11.4 µs 的四分之一速节流代码 其余 3/4 部分共约 28.6 µs而std::sort为 19.5 µs 20 µs 正常后续代码共 39.5 µs整体加速缩水到 1.4 倍对更小的输入计入后续代码节流后甚至可能出现实际变慢。这种劫贫济富beggar thy neighbor效应无法在排序这类单点组件层面解决只能在系统层面应对。README 给出三条充分可行的缓解措施把更多代码向量化摊薄启动成本换用启动开销小得多的新 CPUSkylake 是 2015 年产品如 Intel Icelake2021或 AMD Zen42022确保每次排序或其他 AVX-512 工作处理至少 100 KiB 数据使期望加速覆盖启动成本。与 x86-simd-sort、vxsort 的对比2022 年 5 月的论文对比对象是ips4o与std::sortREADME 的后续更新纳入了 Intel x86-simd-sort约 2022 年 10 月开源与 vxsort约 2020 年 5 月以博文系列形式公开作者当时不知情。两者于 2023-06-06 上午约 10:15 UTC 导入bench_sort在同一 Linux Xeon 6154 环境同场对比。总览结论VQSort 通常比两者都快约 1.4 倍个别情况持平或最多慢 2%。一个重要的公平性设计对比使用均匀随机输入。因为 vxsort 与 x86-simd-sort 的枢纽选择较弱分别为三键中位数与64 字节中位数而 VQSort 抽取 384 字节样本并分析其分布——这改善了负载均衡、避免了递归进入全等分区从而对偏斜分布与最坏情况更稳健。用均匀随机可以避免让对手算法处于不利位置。2 的幂小尺寸排序网络正面交锋2 到 12864 位键下 VQSort 总体最快例外为N2 与 vxsort 打平537 MB/s、N16 略慢于 vxsort2114 vs 2147 MB/s、N32 与 x86-simd-sort 打平2643 MB/sN128 时 VQSort 约快 1.6 倍README 推测其 2D 结构能支持更大的排序网络。10 的幂尺寸10 到 100KkPow10模式该模式覆盖非 2 的幂尺寸与排序网络 ↔ 快排递归的交叉点相对 x86-simd-sort32 位键加速比 1.33–1.8164 位键 1.25–1.68几何均值分别为1.48与1.44相对 vxsort32 位键 1.08–2.1064 位键 1.00–1.47几何均值1.41与1.20除 10 个 64 位元素处持平外VQSort 严格更快。固定 10K 元素的键类型扫描x86-simd-sort 处理 int16 需要 AVX512-VBMI2测试 CPU 不支持且两个对手均不支持 128 位键故只测 32/64 位整型与浮点。结果MB/s类型VQSortx86-simd-sortvxsortf321551798823f6417731147745i3215091042968i64136510431145VQSort 对每种类型都是最快部分场景接近 2 倍。一个耐人寻味的现象vxsort 在 i64 上表现最好而其他两个算法在 f64 上最好——潜在解释是该 CPU 每周期可执行两个 f64 min/max 但只能执行一个 i64提示微架构执行端口特征会直接影响排序热点指令比较/选择的效率。综合三组实验README 的最终结论是跨越输入尺寸与键类型VQSort 总体比 vxsort 与 x86-simd-sort 更高效偶发至多 2% 的落后而 32 位键、10 的幂尺寸下的几何均值加速为相对 vxsort1.41、相对 x86-simd-sort1.48。集成建议与源码导航结合 README 与源码使用 VQSort 时的关键要点输入规模≥100 KiB 时收益最稳定vqsort.h 的官方建议小输入下注意 AVX-512 平台的启动开销与上文三条缓解措施两种集成模式默认动态分派模式包含 vqsort.h 调用VQSort()系列若希望静态分派、零DLLEXPORT开销可定义VQSORT_ONLY_STATIC后直接调用 vqsort-inl.h 中的VQSortStatic*代价是随机种子的安全性下降回退到栈/代码地址 clock()混合调试可观测性VQSORT_PRINT宏0 静默 / 1 每次排序简报 / ≥2 更多细节见 vqsort-inl.h#L42-L45正确性测试sort_test/sort_unit_test对每个类型 × 顺序组合做分派验证bench_sort内部每次测量后也用SortOrderVerifier校验排序正确性bench_sort.cc#L351-L354延伸阅读路径README 主体 → 公开接口 vqsort.h → 分派与种子机制 vqsort.cc、vqsort-inl.h → 基准实现 bench_sort.cc → 排序网络与 2D 矩阵结构 sorting_networks-inl.h、traits-inl.h → 构建目标 BUILD 与 CMakeLists.txt。需要重申的适用边界本文所有性能数字均为 README 与仓库源码记录的特定硬件Xeon 6154 Skylake-X、Graviton3与特定编译器版本下的结果复现前请按 README 各节核对 Clang 版本、C17 要求与平台旗标对降频/启动开销的讨论同样以 Skylake 微架构为主要证据推广到其他微架构时应以本机实测为准。【免费下载链接】highwayPerformance-portable, length-agnostic SIMD with runtime dispatch项目地址: https://gitcode.com/GitHub_Trending/hi/highway创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考