企业官网建设流程全解析

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.05982），README 将其作为整个模块的锚点事实。

在源码层面，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.h）：

• VQSort(keys, n, order)：对keys[0, n)全量排序，分派到最佳指令集，不分配内存，栈开销约 1.2 KiB；
• VQPartialSort(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 提供三条路径复现基准结果。核心前提一致：必须使用 Clang（README 声明测试过 13.0.1 与 15.0.6），若它不是默认编译器需通过环境变量指定：

export CC=clang-15 export CXX=clang++-15

CMake 流程（任意平台）

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 要求 C++17，若CMAKE_CXX_STANDARD < 17会给出vqsort requires C++17的警告。

按 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.1）：

go install github.com/bazelbuild/bazelisk@latest git clone https://github.com/google/highway cd highway CC=clang CXX=clang++ ~/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会构建vqsort（24 个按"类型 × 升/降序"拆分的源文件，如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 Graviton3（SVE / NEON）流程

这一节是 README 中最完整的实操记录，目标是 Graviton3（c7g.8xlarge，Amazon Linux 5.10 arm64，最大 32 vCPU）。两个关键坑与解法：

1. 系统 CMake 过旧，无法构建 LLVM，需要先源码构建 CMake 3.23.2：

wget 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_OPENSSL=OFF make -j8 && sudo make install cd ..

2. AWS 自带 Clang 11.1 会生成多余的AND指令，使排序慢 1.15 倍，因此需用 LLVM trunk（README 记录测试时对应 Git hash8f6512fea000c3a0d394864bb94e524bee375069）编译 Clang：

git 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_PROJECTS="clang" -DLLVM_ENABLE_RUNTIMES="libcxx;libcxxabi" -DCMAKE_BUILD_TYPE=Release make -j32 && sudo make install

随后安装 bazelisk 并构建，注意--copt传入目标指令集：

sudo yum install go go install github.com/bazelbuild/bazelisk@latest 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=-march=armv8.2-a+sve hwy/contrib/sort:all bazel-bin/hwy/contrib/sort/sort_test bazel-bin/hwy/contrib/sort/bench_sort

README 特别解释了 SVE 旗标的适用边界：-march=armv8.2-a+sve仅 Graviton3 可用；要测同一颗处理器上的 NEON（或其他 Arm CPU）需把该选项改为--copt=-march=armv8.2-a+crypto。作者同时指出，一旦 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::sort，vq即 VQSort）→键类型（f32即 float）→键分布（uniform32为 0 到 2^32 区间的均匀随机）→键数量→吞吐量（每秒输出的排序键字节数）。源码中分布枚举定义在 algo-inl.h#L109：enum class Dist { kUniform8, kUniform16, kUniform32 };。

README 给出的 Xeon 6154（Skylake-X，3 GHz）摘录：

[ RUN ] BenchSortGroup/BenchSort.BenchAllSort/AVX3 AVX3: std: f32: uniform32: 1.00E+06 54 MB/s ( 1 threads) AVX3: vq: f32: uniform32: 1.00E+06 1143 MB/s ( 1 threads)

1143 MB/s 对 54 MB/s，即该场景下约 21 倍吞吐（注意：这是单线程、100 万浮点键、均匀随机分布的单项数据，与"10 倍"的总体表述口径不同）。从 bench_sort.cc 的AlgoForBench()可见，基准框架内置了多个可插拔对照算法：kVQSort、kVXSort、kIntel（x86-simd-sort）、kIPS4O、kPDQ、kSort512、kSEA等，由编译期宏HAVE_VXSORT、HAVE_INTEL、HAVE_PDQSORT等开关控制，默认构建下主要对比 VQSort 与std::sort。

基准的尺寸采样模式定义在 bench_sort.cc#L363-L421 的BenchmarkModes中，与 README"对比研究"一节一一对应：

• kDefault：100 与 100K（或 100M，开启并行/SORT_100M时）；
• kSmallPow2：2、4、…、128 的 2 的幂，用于隔离"排序网络"性能（README 提到 x86-simd-sort 与 vxsort 都使用排序网络，VQSort 同样在小输入走网络）；
• kPow10：10、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-L111：Linux 上 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 的指令缓存，甚至可能落入微操作缓存（DSB，1500–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 6154（Skylake 微架构，是潜在受降频影响最大的架构之一），Linux 6.1.20，Clang 接近 LLVM trunk。作者新增了一个 'cold' 基准：初始化随机种子 → 数组填常量、仅一个随机索引处填不同值 → 调用 VQSort → 打印一个随机元素防止计算被消除。构建命令：

# 构建时定义宏 cmake .. -DSORT_ONLY_COLD=1 # 等价于编译定义 -DSORT_ONLY_COLD=1 # 运行 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的定义与回退默认值 0；BenchAllColdSort()（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 原文的核心论点）：

1. 若周边代码平均每 500 µs 执行一次 AVX-512 指令，AVX-512 保持活跃，此时无论输入多小，每次 VQSort 调用都直接受益。对按数据导向设计、已广泛使用 SIMD 的现代系统，这是合理预期；
2. 若把 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 给出三条充分可行的缓解措施：

• 把更多代码向量化，摊薄启动成本；
• 换用启动开销小得多的新 CPU（Skylake 是 2015 年产品），如 Intel Icelake（2021）或 AMD Zen4（2022）；
• 确保每次排序（或其他 AVX-512 工作）处理至少 100 KiB 数据，使期望加速覆盖启动成本。

与 x86-simd-sort、vxsort 的对比

2022 年 5 月的论文对比对象是ips4o与std::sort；README 的后续更新纳入了 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 到 128）

• 64 位键下 VQSort 总体最快，例外为：N=2 与 vxsort 打平（537 MB/s）、N=16 略慢于 vxsort（2114 vs 2147 MB/s）、N=32 与 x86-simd-sort 打平（2643 MB/s）；
• N=128 时 VQSort 约快 1.6 倍，README 推测其 2D 结构能支持更大的排序网络。

10 的幂尺寸（10 到 100K）：kPow10模式

该模式覆盖非 2 的幂尺寸与"排序网络 ↔ 快排递归"的交叉点：

• 相对 x86-simd-sort：32 位键加速比 1.33–1.81，64 位键 1.25–1.68，几何均值分别为1.48与1.44；
• 相对 vxsort：32 位键 1.08–2.10，64 位键 1.00–1.47，几何均值1.41与1.20；除 10 个 64 位元素处持平外，VQSort 严格更快。

固定 10K 元素的键类型扫描

x86-simd-sort 处理 int16 需要 AVX512-VBMI2（测试 CPU 不支持），且两个对手均不支持 128 位键，故只测 32/64 位整型与浮点。结果（MB/s）：

VQSort 对每种类型都是最快，部分场景接近 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 时的关键要点：

1. 输入规模：≥100 KiB 时收益最稳定（vqsort.h 的官方建议）；小输入下注意 AVX-512 平台的启动开销与上文三条缓解措施；
2. 两种集成模式：默认动态分派模式包含 vqsort.h 调用VQSort()系列；若希望静态分派、零DLLEXPORT开销，可定义VQSORT_ONLY_STATIC后直接调用 vqsort-inl.h 中的VQSortStatic*，代价是随机种子的安全性下降（回退到栈/代码地址 +clock()混合）；
3. 调试可观测性：VQSORT_PRINT宏（0 静默 / 1 每次排序简报 / ≥2 更多细节，见 vqsort-inl.h#L42-L45）；
4. 正确性测试：sort_test/sort_unit_test对每个类型 × 顺序组合做分派验证，bench_sort内部每次测量后也用SortOrderVerifier校验排序正确性（bench_sort.cc#L351-L354）；
5. 延伸阅读路径：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 版本、C++17 要求与平台旗标；对降频/启动开销的讨论同样以 Skylake 微架构为主要证据，推广到其他微架构时应以本机实测为准。

【免费下载链接】highwayPerformance-portable, length-agnostic SIMD with runtime dispatch项目地址: https://gitcode.com/GitHub_Trending/hi/highway