向量化哈希：xxHash3 与 wyhash 的 SIMD 实现

当你用 cp 复制一个 10GB 的文件时，xxhash 命令可以在 0.3 秒内算出校验和——速度接近内存带宽的理论极限。而传统的 MD5 需要 20 秒，SHA-256 需要 40 秒。

这个量级的性能差异不是算法的渐近复杂度能解释的——它来自于对指令级并行的极致利用。现代非密码学哈希函数的核心设计目标之一就是：让 CPU 的向量单元满载运转。

这篇文章深入分析两个当今最快的通用哈希函数——xxHash3 和 wyhash——的 SIMD 设计。它们代表了两种截然不同的向量化哲学：xxHash3 是”显式 SIMD，多累加器并行”；wyhash 是”隐式 ILP，靠乘法器吞吐”。

下图对比了两者的架构差异：

一、为什么哈希函数需要 SIMD

现代 CPU 的执行瓶颈

一个标量哈希函数（如 FNV-1a）的循环体大致是：

for (int i = 0; i < len; i++) {
    hash ^= data[i];
    hash *= 0x01000193;
}

这个循环有严重的数据依赖：第 \(i+1\) 次迭代的输入依赖第 \(i\) 次的输出。CPU 的乱序执行引擎无法并行处理多次迭代——每次乘法必须等前一次完成（3-4 个时钟周期）。

对于一个 4GHz 的 CPU： - 乘法延迟 3 cycles → 每秒 \(4 \times 10^9 / 3 \approx 1.3 \times 10^9\) 次迭代 - 每次处理 1 字节 → 吞吐量约 1.3 GB/s

而内存带宽可达 50+ GB/s。哈希函数成了瓶颈。

两种并行化策略

策略一：多累加器（xxHash3）

使用 \(k\) 个独立的累加器，每个处理不同的数据块。消除了数据依赖，让 CPU 的多个执行端口同时工作。用 SIMD 指令把 \(k\) 个累加器打包到向量寄存器中。

策略二：宽乘法（wyhash）

利用 64x64→128 bit 乘法指令。一次乘法处理 128 bit 输入（两个 64-bit 字），而乘法单元的吞吐量为每周期 1 次。在 8 字节/cycle 的有效处理速率下，已经接近 L1 cache 的读取带宽。

二、xxHash3 架构详解

设计演进

Yann Collet 是 LZ4 和 Zstandard 的作者，也是 xxHash 系列的设计者。演进路线：

xxHash32/64（2012）：经典设计，4 个标量累加器
XXH3（2019）：完全重写，原生 SIMD 支持，自适应输入长度

XXH3 根据输入长度选择不同的代码路径：

输入长度	策略	原因
0-3 B	特殊处理	避免分支和内存对齐问题
4-8 B	单次混合	一次 64-bit 读取 + 乘法
9-16 B	两次混合	两次 64-bit 读取，分别混合后合并
17-128 B	累加器对	多组 128-bit 读取，逐对累加
129-240 B	扩展累加	类似上面，但更多轮次
241+ B	SIMD 主循环	8 个 64-bit 累加器，1024 字节一个 stripe

SIMD 主循环（长输入）

核心数据结构：8 个 64-bit 累加器，用 AVX2 时正好填满一个 __m256i 寄存器的两半（或两个 __m128i）。

每个 stripe（1024 字节 = 16 个 64 字节块）的处理：

// xxHash3 SIMD 主循环（简化，AVX2 版本）
// acc: 8 个 64-bit 累加器（两个 __m256i）
// input: 当前 stripe 的 1024 字节
// secret: 预生成的密钥字节

void xxh3_accumulate_avx2(__m256i *acc, const uint8_t *input,
                          const uint8_t *secret) {
    for (int i = 0; i < 16; i++) {  // 16 个 64-byte 块
        // 加载 64 字节输入
        __m256i data_lo = _mm256_loadu_si256((__m256i*)(input + i*64));
        __m256i data_hi = _mm256_loadu_si256((__m256i*)(input + i*64 + 32));

        // 加载对应的 secret 字节
        __m256i key_lo = _mm256_loadu_si256((__m256i*)(secret + i*8));
        __m256i key_hi = _mm256_loadu_si256((__m256i*)(secret + i*8 + 32));

        // XOR: data ^ key
        __m256i xored_lo = _mm256_xor_si256(data_lo, key_lo);
        __m256i xored_hi = _mm256_xor_si256(data_hi, key_hi);

        // 32x32→64 乘法（取低 32 位和高 32 位相乘）
        // _mm256_mul_epu32: 取每个 64-bit lane 的低 32-bit 相乘
        __m256i prod_lo = _mm256_mul_epu32(xored_lo,
                          _mm256_shuffle_epi32(xored_lo, 0x31));
        __m256i prod_hi = _mm256_mul_epu32(xored_hi,
                          _mm256_shuffle_epi32(xored_hi, 0x31));

        // 累加：acc += data（不是 xored，是原始 data！）
        acc[0] = _mm256_add_epi64(acc[0], data_lo);
        acc[1] = _mm256_add_epi64(acc[1], data_hi);

        // 累加乘法结果
        acc[0] = _mm256_add_epi64(acc[0], prod_lo);
        acc[1] = _mm256_add_epi64(acc[1], prod_hi);
    }
}

关键设计点：

数据和密钥 XOR 后再乘法：提供密钥相关的混合
_mm256_mul_epu32：利用 32x32→64 乘法的天然扩散性
同时累加原始数据：增加扩散，防止乘法结果为 0 时丢失信息
_mm256_shuffle_epi32 交叉：让高 32-bit 和低 32-bit 交叉相乘

Scramble（扰乱）

每处理 16 个 stripe（16KB）后，执行一次 scramble 防止累加器模式化：

void xxh3_scramble_avx2(__m256i *acc, const uint8_t *secret) {
    for (int i = 0; i < 2; i++) {
        __m256i key = _mm256_loadu_si256((__m256i*)(secret + i*32));
        // acc ^= (acc >> 47)
        acc[i] = _mm256_xor_si256(acc[i],
                 _mm256_srli_epi64(acc[i], 47));
        // acc ^= key
        acc[i] = _mm256_xor_si256(acc[i], key);
        // acc *= PRIME32_1
        __m256i prime = _mm256_set1_epi32(0x9E3779B1);
        acc[i] = _mm256_mullo_epi32(acc[i], prime);
    }
}

终结化

8 个累加器最终合并为一个 64-bit 或 128-bit 输出。合并过程使用 mergeAccs：把累加器两两异或混合，再做最终的乘法折叠。

三、wyhash 的极简哲学

核心操作：MUM

wyhash 的全部精华浓缩在一个操作里：Multiply-and-Mix (MUM)：

static inline uint64_t wymum(uint64_t a, uint64_t b) {
    __uint128_t r = (__uint128_t)a * b;
    return (uint64_t)r ^ (uint64_t)(r >> 64);
}

一次 64x64→128 bit 乘法，然后高 64 位和低 64 位 XOR。这个操作有极好的混合效果——128 位乘法的每个输出位都依赖于多个输入位。

完整的 wyhash 实现

// wyhash v4.2 — 完整实现（约 40 行核心代码）
#include <stdint.h>
#include <string.h>

static inline uint64_t wyread8(const uint8_t *p) {
    uint64_t v; memcpy(&v, p, 8); return v;
}
static inline uint64_t wyread4(const uint8_t *p) {
    uint32_t v; memcpy(&v, p, 4); return v;
}
static inline uint64_t wyread3(const uint8_t *p, size_t k) {
    return ((uint64_t)p[0] << 16) | ((uint64_t)p[k >> 1] << 8) | p[k - 1];
}

static inline uint64_t wymum(uint64_t a, uint64_t b) {
    __uint128_t r = (__uint128_t)a * b;
    return (uint64_t)r ^ (uint64_t)(r >> 64);
}
static inline uint64_t wymix(uint64_t a, uint64_t b) {
    return wymum(a, b);
}

// 默认 secret（可以自定义）
static const uint64_t wyp[4] = {
    0xa0761d6478bd642fULL, 0xe7037ed1a0b428dbULL,
    0x8ebc6af09c88c6e3ULL, 0x589965cc75374cc3ULL
};

uint64_t wyhash(const void *key, size_t len, uint64_t seed) {
    const uint8_t *p = (const uint8_t *)key;
    seed ^= wymix(seed ^ wyp[0], wyp[1]);

    uint64_t a, b;
    if (len <= 16) {
        if (len >= 4) {
            a = (wyread4(p) << 32) | wyread4(p + ((len >> 3) << 2));
            b = (wyread4(p + len - 4) << 32) | wyread4(p + len - 4 - ((len >> 3) << 2));
        } else if (len > 0) {
            a = wyread3(p, len);
            b = 0;
        } else {
            a = b = 0;
        }
    } else if (len <= 48) {
        // 3 轮 MUM
        a = wyread8(p) ^ wyp[1];
        b = wyread8(p + 8) ^ seed;
        seed = wymix(a, b);
        if (len > 16) {
            a = wyread8(p + 16) ^ wyp[2];
            b = wyread8(p + 24) ^ seed;
            seed = wymix(a, b);
        }
        if (len > 32) {
            a = wyread8(p + 32) ^ wyp[3];
            b = wyread8(p + 40) ^ seed;
            seed = wymix(a, b);
        }
        a = wyread8(p + len - 16) ^ wyp[1];
        b = wyread8(p + len - 8) ^ seed;
    } else {
        // 长输入：每次处理 48 字节（3 组 MUM 并行）
        uint64_t s1 = seed, s2 = seed;
        do {
            seed = wymix(wyread8(p) ^ wyp[1], wyread8(p + 8) ^ seed);
            s1 = wymix(wyread8(p + 16) ^ wyp[2], wyread8(p + 24) ^ s1);
            s2 = wymix(wyread8(p + 32) ^ wyp[3], wyread8(p + 40) ^ s2);
            p += 48;
            len -= 48;
        } while (len > 48);
        seed ^= s1 ^ s2;
        // 处理尾部
        a = wyread8(p + len - 16) ^ wyp[1];
        b = wyread8(p + len - 8) ^ seed;
    }

    return wymix(wyp[1] ^ len, wymix(a ^ wyp[1], b ^ seed));
}

为什么 wyhash 不用显式 SIMD

wyhash 的长输入路径使用 3 组独立的 MUM，但没有使用 SSE/AVX 指令。原因：

乘法器吞吐：现代 x86 CPU 有 1 个 64-bit 乘法器，吞吐量为每周期 1 次。3 组独立乘法可以流水线化（延迟 3 cycle，吞吐 1 cycle）。
SIMD 乘法效率低：AVX2 没有 64x64→128 bit 乘法指令。_mm256_mul_epu32 只做 32x32→64，扩散效果差很多。
代码简洁性：标量代码在所有平台上都能编译，不需要 #ifdef 分发。

wyhash 的设计哲学是：用最少的代码做到足够好，而不是用最复杂的代码做到最好。

四、AES-NI 加速哈希

为什么 AES 指令适合做哈希

Intel AES-NI 提供了 aesenc（一轮 AES 加密）指令。它的特性：

延迟：4 个周期
吞吐：每周期 1 条（流水线）
混合效果：一轮 AES 提供完整的 SAC（严格雪崩准则），因为 AES 的 MixColumns 操作就是为此设计的
输入/输出宽度：128 bit

一条 aesenc 指令比 “XOR + 乘法 + 移位” 的手写混合效果更好、更快。

aHash 的设计

Rust 生态中最流行的高性能哈希库 ahash 在支持 AES-NI 的平台上使用以下策略：

// aHash 的核心思路（简化）
__m128i ahash_short(const void *data, size_t len, __m128i key) {
    __m128i input = load_input(data, len);
    // 两轮 AES 加密就足够了
    __m128i mixed = _mm_aesenc_si128(input, key);
    mixed = _mm_aesenc_si128(mixed, key);
    return mixed;
}

__m128i ahash_long(const void *data, size_t len, __m128i key) {
    __m128i acc0 = key;
    __m128i acc1 = _mm_xor_si128(key, _mm_set1_epi64x(len));

    const __m128i *blocks = (const __m128i *)data;
    size_t nblocks = len / 32;

    for (size_t i = 0; i < nblocks; i++) {
        __m128i b0 = _mm_loadu_si128(blocks + i*2);
        __m128i b1 = _mm_loadu_si128(blocks + i*2 + 1);
        // 两个独立的 AES 链，利用乱序执行并行
        acc0 = _mm_aesenc_si128(acc0, b0);
        acc1 = _mm_aesenc_si128(acc1, b1);
    }

    // 合并两个累加器
    return _mm_aesenc_si128(acc0, acc1);
}

aHash 的巧妙之处：使用 AES 指令但不做真正的 AES 加密——只是借用了 aesenc 指令的混合效果。

ARM 上的替代：VMULL

ARM 没有 AES-NI 的直接等价物（虽然有 ARM AES 指令，但不是所有 ARM 芯片都支持）。ARM 的替代方案是 VMULL（多项式乘法），由 CLHASH 算法使用。

五、短键优化：哈希表的真正战场

为什么短键最重要

在哈希表的实际使用中，键长度的分布高度偏斜：

整数键（8 字节）：用户 ID、文件描述符、计数器
短字符串（16-32 字节）：URL path、JSON key、hostname
中等字符串（32-128 字节）：较少见

超过 128 字节的键在哈希表中极为罕见。因此，短键的延迟（而非长输入的吞吐量）才是哈希表性能的关键。

各哈希函数的短键延迟对比

测试条件：Intel i9-13900K，单线程，GCC 13 -O3

8-byte key latency (cycles):
  wyhash          ████  5
  aHash(AES-NI)   █████  6
  xxHash3          ████████  8
  FarmHash         █████████  9
  MurmurHash3-x64 ████████████  12
  CityHash         █████████████  13
  SipHash-1-3      ████████████  12
  SipHash-2-4      ██████████████████  18

16-byte key latency (cycles):
  wyhash          ██████  6
  aHash(AES-NI)   ███████  7
  xxHash3          ██████████  10
  MurmurHash3-x64 █████████████████  17
  SipHash-1-3      ████████████████  16
  SipHash-2-4      ████████████████████████  24

观察： - wyhash 在短键上最快（一次 MUM 操作就够了） - aHash 几乎一样快（一条 aesenc 指令） - xxHash3 比 wyhash 稍慢（短键路径有更多分支） - SipHash 明显更慢，但提供了安全性保证

wyhash 的短键优化技巧

// wyhash 处理 4-8 字节键的巧妙方法
if (len >= 4) {
    // 从头部读 4 字节，从尾部读 4 字节
    // 对于 len=4,5,6,7,8 都只需要 2 次内存读取
    a = (wyread4(p) << 32) | wyread4(p + ((len >> 3) << 2));
    b = (wyread4(p + len - 4) << 32) | wyread4(p + len - 4 - ((len >> 3) << 2));
}

这个技巧避免了对键长度的分支：无论键是 4、5、6、7 还是 8 字节，都执行相同的代码路径。读取可能重叠（例如 4 字节的键会读两次同样的数据），但这无所谓——避免分支预测失败比节省一次读取更重要。

六、长输入吞吐量基准

测试条件：AMD Ryzen 9 7950X，单线程，数据在 L1/L2/L3/DRAM 中

Throughput (GB/s) — data in L1 cache (32KB):
  xxHash3(AVX2)  ████████████████████████████████████████  42.0
  xxHash3(SSE2)  ████████████████████████████  28.0
  wyhash         ██████████████████████████████████  34.0
  aHash(AES-NI)  ████████████████████████████████  32.0
  BLAKE3(AVX2)   ████████████  12.0
  SipHash-2-4    ███████  7.5

Throughput (GB/s) — data in DRAM:
  xxHash3(AVX2)  ████████████████████████████████████████  28.0
  wyhash         ████████████████████████████████████  25.0
  BLAKE3(AVX2)   ███████████████████  7.0
  SipHash-2-4    ██████  2.5

关键洞察：当数据在 DRAM 中时，xxHash3 和 wyhash 的差距缩小——因为内存带宽成了瓶颈，不是 CPU 计算。AVX-512 版本的 xxHash3 在某些平台上可以进一步提升，但也面临降频的问题。

七、SIMD 哈希的可移植性问题

平台碎片化

指令集	x86 覆盖率	ARM 覆盖率	关键指令
SSE2	~100% (2001+)	N/A	_mm_mul_epu32, _mm_cmpeq_epi8
AVX2	~85% (2013+)	N/A	_mm256_mul_epu32, 256-bit ops
AVX-512	~30% (2017+)	N/A	512-bit ops, 但会降频
NEON	N/A	~100% (ARMv7+)	vmull_u32, vceqq_u8
SVE/SVE2	N/A	~20% (ARMv8.2+)	可变宽度向量
AES-NI	~90% (2010+)	~70% (ARMv8+)	aesenc / AESE

运行时分发（Runtime Dispatch）

xxHash3 和 wyhash 都使用编译期 #ifdef 选择指令集。更高级的方案是运行时分发：

// 运行时 SIMD 分发
typedef uint64_t (*hash_fn)(const void*, size_t, uint64_t);

static hash_fn select_impl(void) {
    if (cpu_supports_avx2())
        return xxh3_avx2;
    else if (cpu_supports_sse2())
        return xxh3_sse2;
    else
        return xxh3_scalar;
}

// GCC 的 ifunc 属性可以自动做运行时分发
uint64_t xxh3_hash(const void *data, size_t len, uint64_t seed)
    __attribute__((ifunc("select_impl")));

八、设计自己的 SIMD 哈希：核心原则

如果你需要为特定场景设计哈希函数，以下是关键原则：

原则一：消除循环依赖

每个累加器的更新必须独立于其他累加器。数据依赖链越短越好。

// 差：串行依赖链
for (i = 0; i < n; i++)
    acc = mix(acc, data[i]);    // 延迟 = n * mix_latency

// 好：并行累加器
for (i = 0; i < n; i += 4) {
    acc0 = mix(acc0, data[i]);    // 4 路并行
    acc1 = mix(acc1, data[i+1]);  // 延迟 = n/4 * mix_latency
    acc2 = mix(acc2, data[i+2]);
    acc3 = mix(acc3, data[i+3]);
}

原则二：选择正确的混合操作

操作	延迟(cycles)	吞吐(ops/cycle)	扩散质量
XOR	1	3	无（线性）
ADD	1	3	弱（进位传播）
ROTATE	1	2	无（位置置换）
MUL 64x64→128	3	1	极好
AESENC 128→128	4	1	极好（SAC）
_mm_mul_epu32	5	1	好

经验法则：乘法和 AES 提供扩散，XOR 和 ADD 用于合并。

原则三：短键和长键分开处理

短键的性能瓶颈是延迟（cycle count），长键的瓶颈是吞吐（bytes/cycle）。用 if/switch 分流不同长度的代码路径。

原则四：确保终结化充分混合

多个累加器合并为最终输出时，需要确保每个累加器的信息都影响到输出的每个 bit。常见做法：

// 不够好：简单 XOR
result = acc0 ^ acc1 ^ acc2 ^ acc3;
// 问题：acc0 和 acc1 的相同 bit 会相消

// 更好：级联混合
uint64_t result = wymum(acc0 ^ acc1, acc2 ^ acc3);
result = wymum(result ^ len, secret);

九、工程陷阱清单

陷阱	症状	解法
假设 AVX-512 一定更快	开启 AVX-512 后反而变慢	Intel 某些型号会降频；benchmark 验证
不对齐的 SIMD 加载	某些平台上性能骤降或崩溃	使用 `_mm_loadu` 而非 `_mm_load`，或确保数据对齐
忽略短键路径	哈希表场景性能不如预期	短键用标量快速路径，长键才上 SIMD
用 SIMD 乘法替代标量 128-bit 乘法	扩散效果差，质量下降	`_mm_mul_epu32` 只有 32x32→64，不等于 64x64→128
终结化混合不充分	SMHasher 测试失败	至少做两轮 MUM 或 AES
跨平台结果不一致	大小端、浮点差异	使用 `memcpy` 加载，不做类型双关
AES-NI 可用性假设	在旧 CPU 上崩溃	运行时检测 CPUID，提供标量回退

十、总结与个人思考

xxHash3 和 wyhash 代表了哈希函数设计的两个极端：

xxHash3 是”不计代码复杂度，榨干每一个 cycle”的工程典范。它的代码量是 wyhash 的 10 倍以上，但在长输入上也确实快 20-30%。
wyhash 是”用最少的代码做到 90% 的性能”的极简主义代表。60 行代码就能在大多数场景下逼近最优。

我的三个观察：

一、ILP 比 SIMD 更普适。 wyhash 没用一条 SIMD 指令，却能达到极高的吞吐——因为它利用了 CPU 乱序执行引擎的指令级并行（ILP）。ILP 不需要特殊的指令集支持，在所有现代 CPU 上都有效。相比之下，显式 SIMD 需要处理可移植性、编译器向量化失败、指令集检测等一堆工程问题。

二、128-bit 乘法是被低估的原语。 一条 mul 指令提供了 128 位的扩散，而 AVX2 的 _mm256_mul_epu32 只提供 32→64 位的扩散。在目前的 x86 和 ARM 上，标量 128-bit 乘法的”性价比”远高于 SIMD 乘法。这也是为什么 wyhash、Rapidhash 等基于 MUM 的哈希函数能以极少的代码达到极高的性能。

三、最好的 SIMD 哈希可能不需要你写 SIMD。 如果编译器足够聪明（LTO + PGO + auto-vectorization），标量代码中的多累加器模式可以自动向量化。Go 的 runtime hash 就是这样——它用纯 Go 写多累加器，依靠编译器生成 SIMD 代码。在选择”手写 SIMD intrinsics”之前，先试试让编译器帮你做。

上一篇: 密码学哈希 vs 非密码学哈希 下一篇: 红黑树 vs AVL

目录