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

当你用 xxhsum 校验一个 10 GB 的文件时，xxHash3 可以在 0.3 秒内算出结果——速度接近 DDR5 内存带宽的理论极限。同样的文件交给 MD5 需要 20 秒，SHA-256 需要 40 秒。

这个量级的性能差异不是算法的渐近复杂度能解释的。O(n) 的哈希函数之间，性能差距完全取决于每字节消耗多少个时钟周期。现代非密码学哈希函数的核心设计目标只有一个：让 CPU 流水线的每一个执行端口都满载运转。

这篇文章深入分析两个当今最快的通用哈希函数——xxHash3 和 wyhash——的向量化设计。它们代表了两种截然不同的并行化哲学：

• xxHash3 是”显式 SIMD，多累加器并行”的工程典范——代码超过 2000 行，为 AVX2、SSE2、NEON 各写了一套实现。
• wyhash 是”隐式 ILP，靠宽乘法吞吐”的极简主义代表——核心代码不到 60 行，没有一条 SIMD intrinsic，但吞吐量仅比 xxHash3 低 15%。

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

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

内存带宽 vs 计算瓶颈

先建立一个定量模型。以一台典型的 2024 年桌面机为例：

• CPU 频率：5 GHz
• L1 读取带宽：两个 256-bit load port，理论峰值 = 2 * 32 B * 5 GHz = 320 GB/s
• L2 带宽：约 100 GB/s
• DRAM 带宽：DDR5-5600 双通道，约 45 GB/s

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

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

这个循环有严重的数据依赖链：第 i+1 次迭代的 hash 输入依赖第 i 次的 hash 输出。CPU 的乱序执行引擎无法并行处理多次迭代——每次乘法必须等前一次完成。

IPC 分析

用 perf stat 测量 FNV-1a 处理 1 MB 数据：

Performance counter stats:
    5,240,000   cycles
    3,140,000   instructions    # IPC = 0.60
    1,048,576   branches
            0   branch-misses

Throughput: ~0.95 GB/s @ 5 GHz

IPC 只有 0.6——现代 CPU 可以每周期退休 4-6 条指令，0.6 意味着 85% 的执行能力被浪费了。根本原因是循环携带依赖（loop-carried dependency）：乘法延迟 3 个周期，而循环体只有约 3 条指令，流水线完全被延迟堵死。

换成 xxHash3 的 AVX2 路径：

Performance counter stats:
      310,000   cycles
    1,820,000   instructions    # IPC = 5.87
       19,500   branches
            0   branch-misses

Throughput: ~33 GB/s @ 5 GHz

IPC 从 0.6 飙升到 5.87。同样是 O(n) 的算法，吞吐量差了 35 倍。秘密在于 xxHash3 把依赖链打碎成了 8 条独立的短链路，让 CPU 的多个执行端口同时工作。

两种并行化策略

策略一：多累加器 + 显式 SIMD（xxHash3 的做法）

使用 k 个独立的累加器，每个处理不同的数据块。用 SIMD 指令（AVX2、SSE2、NEON）把 k 个累加器打包到向量寄存器中，一条指令同时更新所有累加器。对于 AVX2，k=8（8 个 64-bit 累加器打包到两个 256-bit 寄存器中）。

策略二：宽乘法 + 隐式 ILP（wyhash 的做法）

利用 64x64 位到 128 位的乘法指令（x86 的 mul、ARM 的 umulh）。一次乘法消耗 16 字节输入（两个 64-bit 字），产生 128 位结果。使用 3 组独立的乘法链，靠 CPU 乱序引擎自动流水线化。不写一条 SIMD intrinsic，但在标量执行单元上仍然达到很高的吞吐。

两种策略的权衡：

二、xxHash 系列演进

xxHash32（2012 年）

Yann Collet（LZ4 和 Zstandard 的作者）在 2012 年发布了 xxHash32。核心思路源自 Bob Jenkins 的哈希设计：使用 4 个 32-bit 累加器消除依赖链。

// xxHash32 核心循环（简化）
uint32_t acc1 = seed + PRIME1 + PRIME2;
uint32_t acc2 = seed + PRIME2;
uint32_t acc3 = seed;
uint32_t acc4 = seed - PRIME1;

while (p <= limit) {
    acc1 += read32(p)    * PRIME2; acc1 = rotl32(acc1, 13) * PRIME1;
    acc2 += read32(p+4)  * PRIME2; acc2 = rotl32(acc2, 13) * PRIME1;
    acc3 += read32(p+8)  * PRIME2; acc3 = rotl32(acc3, 13) * PRIME1;
    acc4 += read32(p+12) * PRIME2; acc4 = rotl32(acc4, 13) * PRIME1;
    p += 16;
}
// 合并 4 个累加器
uint32_t h = rotl32(acc1, 1) + rotl32(acc2, 7)
           + rotl32(acc3, 12) + rotl32(acc4, 18);

4 路并行让 IPC 从约 0.6 提升到约 2.4。每次迭代处理 16 字节，吞吐量约 6-8 GB/s。对于 2012 年的 CPU，这已经是非常出色的数字。

xxHash64（2014 年）

将累加器宽度从 32 位扩展到 64 位，每次处理 32 字节（4 个 64-bit 字）。混合操作从 “乘 + 旋转 + 乘” 变成了类似的三步结构但使用 64 位操作。吞吐量在同代 CPU 上提升到约 12-15 GB/s。但问题依旧：4 个标量累加器仍然受限于乘法单元的吞吐——x86 只有一个 64-bit 乘法端口。

xxHash3（2019 年）：为什么每一代都更快

xxHash3 做了三个关键改变使其远超前辈：

改变一：从 4 个累加器扩展到 8 个。 8 个 64-bit 累加器意味着每次迭代处理 64 字节。用 AVX2 只需两个 256-bit 寄存器就能容纳全部累加器。

改变二：用 32x32 位到 64 位乘法替代 64x64 位乘法。 AVX2 提供了 _mm256_mul_epu32（4 个并行的 32x32 到 64 位乘法），但没有 64x64 到 128 位的 SIMD 乘法。xxHash3 将混合操作改造为适配 SIMD 乘法指令的形式，同时通过累加原始数据来补偿扩散的损失。

改变三：引入 secret 密钥。 用一段 192 字节的密钥（而不是素数常量）与数据 XOR 后再混合。密钥可以自定义，也可以从 seed 派生。这解决了 xxHash64 的一个安全弱点：攻击者知道常量后可以构造碰撞。

吞吐量提升汇总（以 Haswell 为参考基准）：

三、xxHash3 架构深入

Secret 机制

xxHash3 使用一段至少 136 字节的 secret 数据。默认 secret 是编译时常量，但可以通过 seed 生成自定义 secret：

// 从 seed 生成 secret（简化）
void xxh3_generate_secret(uint8_t *secret, uint64_t seed) {
    for (int i = 0; i < 192; i += 16) {
        write64(secret + i,     read64(default_secret + i)     + seed);
        write64(secret + i + 8, read64(default_secret + i + 8) - seed);
    }
}

Secret 的设计目的有三个：

1. 抗碰撞攻击：不同的 seed 产生不同的 secret，攻击者无法预测混合常量。
2. 替代素数常量：传统哈希用固定的素数做乘法常量，现在用可变的 secret 字节。
3. 为每个 stripe 提供不同的混合参数：处理第 i 个数据块时使用 secret 的第 i*8 字节偏移处的值。

Accumulator 结构

8 个 64-bit 累加器构成核心状态。初始值为精心选择的素数常量：

uint64_t acc[8] = {
    PRIME32_3, PRIME64_1, PRIME64_2, PRIME64_3,
    PRIME64_4, PRIME32_2, PRIME64_5, PRIME32_1
};

在 AVX2 实现中，这 8 个值被装入两个 __m256i 寄存器，后续的所有操作都在 256-bit 向量上进行。

Stripe 处理流程

xxHash3 将输入按 1024 字节（= 16 个 64 字节块）分成 stripe。每个 stripe 内的处理不做累加器间的交叉混合——这是保证 SIMD 并行的关键。

AVX2 路径

void xxh3_accumulate_avx2(__m256i *acc, const uint8_t *input,
                          const uint8_t *secret) {
    for (int i = 0; i < 16; i++) {
        // 步骤 1：加载 64 字节输入（分为两个 256-bit 向量）
        __m256i data_lo = _mm256_loadu_si256(
            (const __m256i *)(input + i * 64));
        __m256i data_hi = _mm256_loadu_si256(
            (const __m256i *)(input + i * 64 + 32));

        // 步骤 2：加载对应 secret 偏移处的 64 字节
        __m256i key_lo = _mm256_loadu_si256(
            (const __m256i *)(secret + i * 8));
        __m256i key_hi = _mm256_loadu_si256(
            (const __m256i *)(secret + i * 8 + 32));

        // 步骤 3：data XOR secret
        __m256i xored_lo = _mm256_xor_si256(data_lo, key_lo);
        __m256i xored_hi = _mm256_xor_si256(data_hi, key_hi);

        // 步骤 4：32x32->64 交叉乘法
        // shuffle 把 [A B C D] 变成 [B A D C]（以 32-bit 为单位）
        // 然后 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));

        // 步骤 5：累加原始数据（不是 XOR 后的结果）
        acc[0] = _mm256_add_epi64(acc[0], data_lo);
        acc[1] = _mm256_add_epi64(acc[1], data_hi);

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

关键设计点解析：

1. 为什么 XOR data 和 secret？ 把可变数据与密钥混合，使攻击者无法控制乘法的两个输入。不做 XOR 的话，攻击者可以构造输入使乘法结果为 0。
2. _mm256_shuffle_epi32(x, 0x31) 的作用：0x31 = 00_11_00_01，把每个 128-bit lane 内的 32-bit 元素从 [0,1,2,3] 重排为 [1,0,3,2]。让 mul_epu32 计算”低 32 位乘以高 32 位”。
3. 为什么累加原始 data 而不是 xored？ 乘法可能产生 0（当 XOR 结果的高 32 位或低 32 位为 0 时）。累加原始数据确保信息不会丢失。
4. 为什么用 mul_epu32 而不是 mullo_epi32？ mul_epu32 产生 64-bit 结果，提供 32 位到 64 位的扩散。mullo 只保留低 32 位，丢弃了高位信息。

SSE2 路径

SSE2 路径的逻辑与 AVX2 完全相同，只是向量宽度减半——使用 4 个 __m128i 寄存器容纳 8 个累加器：

void xxh3_accumulate_sse2(__m128i acc[4], const uint8_t *input,
                          const uint8_t *secret) {
    for (int i = 0; i < 16; i++) {
        __m128i d0 = _mm_loadu_si128((const __m128i*)(input + i*64));
        __m128i d1 = _mm_loadu_si128((const __m128i*)(input + i*64 + 16));
        __m128i d2 = _mm_loadu_si128((const __m128i*)(input + i*64 + 32));
        __m128i d3 = _mm_loadu_si128((const __m128i*)(input + i*64 + 48));

        __m128i k0 = _mm_loadu_si128((const __m128i*)(secret + i*8));
        __m128i k1 = _mm_loadu_si128((const __m128i*)(secret + i*8 + 16));
        __m128i k2 = _mm_loadu_si128((const __m128i*)(secret + i*8 + 32));
        __m128i k3 = _mm_loadu_si128((const __m128i*)(secret + i*8 + 48));

        // 对每个 128-bit chunk 执行 XOR + 交叉乘法 + 累加
        // 与 AVX2 逻辑相同，只是寄存器数量翻倍
        __m128i x0 = _mm_xor_si128(d0, k0);
        acc[0] = _mm_add_epi64(acc[0], d0);
        acc[0] = _mm_add_epi64(acc[0],
                 _mm_mul_epu32(x0, _mm_shuffle_epi32(x0, 0x31)));
        // ...d1/k1 -> acc[1], d2/k2 -> acc[2], d3/k3 -> acc[3]
    }
}

SSE2 的吞吐量约为 AVX2 的 65-70%（不是严格的 50%，因为乱序执行可以隐藏部分额外开销）。

NEON 路径

ARM NEON 有自己的等价操作。核心区别在于 NEON 的乘法指令不同：

void xxh3_accumulate_neon(uint64x2_t acc[4], const uint8_t *input,
                          const uint8_t *secret) {
    for (int i = 0; i < 16; i++) {
        uint64x2_t data = vld1q_u64((const uint64_t*)(input + i*16));
        uint64x2_t key  = vld1q_u64((const uint64_t*)(secret + i*8));
        uint64x2_t xored = veorq_u64(data, key);

        // NEON 使用 vmovn + vshrn + vmull 组合实现交叉乘法
        uint32x2_t xored_lo = vmovn_u64(xored);
        uint32x2_t xored_hi = vshrn_n_u64(xored, 32);
        uint64x2_t prod = vmull_u32(xored_lo, xored_hi);

        acc[i % 4] = vaddq_u64(acc[i % 4], data);
        acc[i % 4] = vaddq_u64(acc[i % 4], prod);
    }
}

NEON 的 vmull_u32 提供两个并行的 32x32 到 64 位乘法，与 SSE2 的 _mm_mul_epu32 等价。Apple M 系列芯片上的 NEON 路径吞吐量可达约 30 GB/s。

Scramble 操作

每处理完 16 个 stripe（即 16 KB 数据）后，执行一次 scramble。目的是防止累加器陷入低混合度的稳态模式：

void xxh3_scramble_avx2(__m256i *acc, const uint8_t *secret) {
    for (int i = 0; i < 2; i++) {
        __m256i key = _mm256_loadu_si256(
            (const __m256i *)(secret + 128 + i * 32));

        // acc ^= (acc >> 47)
        acc[i] = _mm256_xor_si256(
            acc[i], _mm256_srli_epi64(acc[i], 47));

        // acc ^= secret
        acc[i] = _mm256_xor_si256(acc[i], key);

        // acc *= PRIME32_1（0x9E3779B1）
        __m256i prime = _mm256_set1_epi32(0x9E3779B1);
        acc[i] = _mm256_mullo_epi32(acc[i], prime);
    }
}

Scramble 的频率选择经过仔细权衡：太频繁会降低吞吐量（scramble 引入了累加器间的依赖），太稀少则质量下降。16 KB 是在 SMHasher 测试和性能之间的最优平衡点。

终结化

处理完所有 stripe 后，8 个累加器需要合并为 64-bit 或 128-bit 输出：

uint64_t xxh3_merge_accs(const uint64_t *acc, const uint8_t *secret,
                          uint64_t len) {
    uint64_t result = len * PRIME64_1;
    for (int i = 0; i < 4; i++) {
        uint64_t a = acc[2*i]     ^ read64(secret + 16*i);
        uint64_t b = acc[2*i + 1] ^ read64(secret + 16*i + 8);
        result += wymum(a, b);
    }
    return xxh3_avalanche(result);
}

uint64_t xxh3_avalanche(uint64_t h) {
    h ^= h >> 37;
    h *= 0x165667919E3779F9ULL;
    h ^= h >> 32;
    return h;
}

四、xxHash3 短键优化

哈希表中 90% 以上的键短于 128 字节。xxHash3 为每个长度段设计了专门的快速路径。

1-3 字节

uint64_t xxh3_len_1to3(const uint8_t *input, size_t len,
                        const uint8_t *secret, uint64_t seed) {
    uint8_t c1 = input[0];
    uint8_t c2 = input[len >> 1];
    uint8_t c3 = input[len - 1];
    uint32_t combined = ((uint32_t)c1 << 16)
                      | ((uint32_t)c2 << 24)
                      | ((uint32_t)c3)
                      | ((uint32_t)len << 8);

    uint64_t lo = (read32(secret) ^ read32(secret + 4)) + seed;
    uint64_t hi = (read32(secret + 4) ^ read32(secret + 8)) - seed;
    uint64_t value = lo ^ ((uint64_t)combined * hi);
    value ^= value >> 51;
    value *= PRIME64_1;
    value ^= value >> 47;
    value *= PRIME64_4;
    value ^= value >> 35;
    return value;
}

巧妙之处：对于 len=1，c1、c2、c3 都读 input[0]（因为 len>>1 == 0，len-1 == 0）。对于 len=2，c1=input[0]、c2=input[1]、c3=input[1]。没有任何分支。

4-8 字节

uint64_t xxh3_len_4to8(const uint8_t *input, size_t len,
                        const uint8_t *secret, uint64_t seed) {
    seed ^= (uint64_t)bswap32((uint32_t)seed) << 32;
    uint32_t lo = read32(input);
    uint32_t hi = read32(input + len - 4);
    uint64_t input64 = lo | ((uint64_t)hi << 32);

    uint64_t bitflip = (read64(secret + 8) ^ read64(secret + 16)) + seed;
    __uint128_t m = (__uint128_t)(input64 ^ bitflip) * PRIME64_1;
    uint64_t result = (uint64_t)m ^ (uint64_t)(m >> 64);
    result ^= result >> 47;
    result *= PRIME64_2;
    result ^= result >> 43;
    return result;
}

无论 len 是 4、5、6、7 还是 8，都执行两次 32-bit 读取。对于 len=4，头和尾读取完全重叠。避免分支远比避免一次多余读取重要。

9-16 字节

uint64_t xxh3_len_9to16(const uint8_t *input, size_t len,
                         const uint8_t *secret, uint64_t seed) {
    uint64_t bitflip_lo = (read64(secret + 24) ^ read64(secret + 32)) + seed;
    uint64_t bitflip_hi = (read64(secret + 40) ^ read64(secret + 48)) - seed;
    uint64_t input_lo = read64(input) ^ bitflip_lo;
    uint64_t input_hi = read64(input + len - 8) ^ bitflip_hi;

    // 两路独立乘法——CPU 可以同周期发射
    __uint128_t m128 = (__uint128_t)input_lo * PRIME64_1;
    uint64_t result = len
                    + bswap64((uint64_t)m128)
                    + input_hi * PRIME64_2;
    result = xxh3_avalanche(result);
    return result;
}

两次 64-bit 读取，两次独立乘法——CPU 可以并行发射这两条乘法指令。

17-128 字节

这个范围使用”首尾对称读取”的方法：

uint64_t xxh3_len_17to128(const uint8_t *input, size_t len,
                           const uint8_t *secret, uint64_t seed) {
    uint64_t acc = len * PRIME64_1;

    if (len > 32) {
        if (len > 64) {
            if (len > 96) {
                acc += xxh3_mix16b(input + 48, secret + 96, seed);
                acc += xxh3_mix16b(input + len - 64, secret + 112, seed);
            }
            acc += xxh3_mix16b(input + 32, secret + 64, seed);
            acc += xxh3_mix16b(input + len - 48, secret + 80, seed);
        }
        acc += xxh3_mix16b(input + 16, secret + 32, seed);
        acc += xxh3_mix16b(input + len - 32, secret + 48, seed);
    }
    acc += xxh3_mix16b(input + 0, secret + 0, seed);
    acc += xxh3_mix16b(input + len - 16, secret + 16, seed);

    return xxh3_avalanche(acc);
}

xxh3_mix16b 读取 16 字节，XOR secret，做一次 MUM 乘法。嵌套 if 的结构确保编译器不生成间接跳转——每个长度子区间的控制流都是确定性的。

129-240 字节

基本思路同上，但增加更多轮次。先用一个固定的 for 循环处理前 128 字节（每 16 字节一轮 mix），然后对剩余部分做类似 17-128 的处理。这是 SIMD 主循环启动前的最后一个标量快速路径。241 字节以上才会进入前面详述的 stripe 处理流程。

五、wyhash 设计哲学

128-bit 乘法 + MUM 混合

wyhash 的核心洞察来自数论：两个 64-bit 整数的 128-bit 乘积具有极好的比特混合特性。

考虑 a * b 的 128 位结果。结果的第 k 位（0 <= k <= 127）依赖于所有满足 i + j = k 的输入位对 (a[i], b[j]) 以及来自低位的进位。单个输出位同时受多个输入位影响——这正是好的哈希混合器需要的扩散性质。

取高 64 位和低 64 位 XOR 进一步增加混合度，因为高位和低位分别依赖不同的输入位组合，XOR 让每个输出位同时包含两组不同的输入信息。wyhash 的作者王奕（Yi Wang）在实验中证明了：单次 MUM 操作在统计测试上接近理想的随机预言机。

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);
}

在 x86-64 上，编译器会把它翻译成：

; rdi = a, rsi = b
mov    rax, rdi
mul    rsi          ; rdx:rax = a * b
xor    rax, rdx     ; result = lo ^ hi
ret

只有 3 条指令。mul 的延迟是 3 个周期，但吞吐量是每周期 1 条。如果有多组独立的 MUM 操作，CPU 的乱序引擎可以让它们流水线化执行。

在 ARM64 上：

; x0 = a, x1 = b
mul    x2, x0, x1    ; x2 = (a * b) 低 64 位
umulh  x3, x0, x1    ; x3 = (a * b) 高 64 位
eor    x0, x2, x3    ; result = lo ^ hi
ret

ARM64 将 128 位乘法拆成 mul（低 64 位）和 umulh（高 64 位）。M1/M2 芯片上这两条指令可以同周期发射，总延迟 3-4 个周期。

为什么代码只有 30 行但质量极高

一、MUM 操作本身就是近乎完美的混合函数。 传统哈希需要”乘法 + 旋转 + XOR + 加法”四步才能达到可接受的混合度。MUM 一步就够了——128 位乘法天然提供了充分的比特扩散。

二、短键路径利用了重叠读取消除分支。 对于 1-16 字节的键，wyhash 用 2-3 次定长读取（可能重叠）覆盖整个输入。没有 switch-case，没有变长循环。

三、长键路径靠 3 组独立 seed 实现隐式并行。 3 个独立的 MUM 链（seed、s1、s2）让 CPU 乱序引擎自动流水线化，不需要显式 SIMD。

六、wyhash 实现细节

读取函数

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;
}

// 1-3 字节读取——无分支
static inline uint64_t wyread3(const uint8_t *p, size_t k) {
    //   k=1: p[0], p[0], p[0]（三次读同一字节）
    //   k=2: p[0], p[1], p[1]
    //   k=3: p[0], p[1], p[2]
    return ((uint64_t)p[0] << 16)
         | ((uint64_t)p[k >> 1] << 8)
         | p[k - 1];
}

memcpy 是关键：编译器会把小长度的 memcpy 优化为单条 load 指令，但语义上它保证了不会触发未定义行为（与 *(uint64_t*)p 不同，后者在非对齐地址上是 UB）。

wymix 函数

static inline uint64_t wymix(uint64_t a, uint64_t b) {
    return wymum(a, b);
}

wymix 和 wymum 在当前版本中是同一个函数。保留这个间接层是为了将来可能的变更——早期版本的 wyhash 中 wymix 包含额外的 XOR 步骤。

主循环与 Finalization

完整实现（约 60 行核心代码）：

#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);
}

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) {
        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 {
        // 长输入：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));
}

主循环 ILP 分析

长输入路径的主循环每迭代处理 48 字节，三条链的数据依赖完全独立：

seed = wymix(read(p)    ^ wyp[1], read(p+8)  ^ seed)   -- 链 A
s1   = wymix(read(p+16) ^ wyp[2], read(p+24) ^ s1)     -- 链 B
s2   = wymix(read(p+32) ^ wyp[3], read(p+40) ^ s2)     -- 链 C

在支持乱序执行的 CPU 上：

• mul 延迟：3 个周期
• mul 吞吐：每周期 1 条
• 3 条独立链可以充分流水线化，有效延迟 = 3/3 = 1 周期/次 MUM
• 每次 MUM 消耗 16 字节，有效吞吐 = 16 B/cycle

在 5 GHz CPU 上：16 * 5 = 80 GB/s 的理论峰值。实际受限于 load 端口数量（每周期 2 个 64-bit load = 16 B/cycle），实测约 30-35 GB/s。

Finalization

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

两层嵌套的 wymix 确保：长度信息（len）参与最终混合；最后两个数据字经过两轮 128 位乘法，即使只有一个字节不同也会产生大量位翻转。

七、其他现代哈希函数

Komihash

由 Aleksey Vaneev 设计，核心思路与 wyhash 类似（基于 128-bit 乘法）但保留了乘法的高低两部分作为两个独立状态变量，而不是 XOR 折叠。这提供了更大的内部状态（128 位 vs 64 位），在碰撞概率上有理论优势。

rapidhash

wyhash 的社区分支，由 Nicolas De Carli 维护。改进了 seed 预处理、ARM64 读取模式，并修复了 wyhash 在极端边界条件下的几个已知弱点。核心算法几乎相同，可以视为”wyhash 的生产级增强版”。

t1ha（Fast Positive Hash）

由 Leonid Yuriev 设计，有多个变体（t1ha0/t1ha1/t1ha2）。独特之处在于大量使用旋转（rotate）而不是移位（shift）来做位混合。旋转不丢失信息，且在大多数 CPU 上只有 1 个周期延迟。

CityHash 与 FarmHash（Google）

• CityHash（2011）：使用”多次 128-bit 乘法 + 旋转”的结构。短键路径做了大量手动优化。是 Google 内部使用最广泛的哈希之一。
• FarmHash（2014）：CityHash 的继任者。在有 CRC32 指令的 CPU 上使用硬件 CRC 加速，其他平台退回到 CityHash 风格的乘法链。

两者的设计思路与 wyhash 的区别：Google 使用更多轮次的混合（换取更好的统计质量），而 wyhash 追求最少轮次（换取更低的延迟）。

HighwayHash（Google）

明确使用 SIMD 指令（AVX2/SSE4.1/NEON），用 4 个 256-bit 向量作为状态。设计目标包含密钥安全性（keyed hash），有类似 SipHash 的安全保证。吞吐量不如 xxHash3（约 15-20 GB/s），但安全性更高。

选型速查

八、完整 C 实现

简化版 xxHash3 核心循环

以下是 xxHash3 长输入路径的纯 C 标量实现（不使用 SIMD intrinsic，用标量模拟逻辑）：

#include <stdint.h>
#include <string.h>

#define PRIME32_1  0x9E3779B1U
#define PRIME64_1  0x11111111111111C7ULL
#define STRIPE_LEN 64
#define ACC_NB     8

static inline uint64_t xxh_read64(const uint8_t *p) {
    uint64_t v; memcpy(&v, p, 8); return v;
}

static const uint8_t xxh3_secret[192] = {
    0xb8, 0xfe, 0x6c, 0x39, 0x23, 0xa4, 0x4b, 0xbe,
    0x7c, 0x01, 0x81, 0x2c, 0xf7, 0x21, 0xad, 0x1c,
    0xde, 0xd4, 0x6d, 0xe9, 0x83, 0x90, 0x97, 0xdb,
    0x72, 0x40, 0xa4, 0xa4, 0xb7, 0xb3, 0x67, 0x1f,
    0xcb, 0x79, 0xe6, 0x4e, 0xcc, 0xc0, 0xe5, 0x78,
    0x82, 0x5a, 0xd0, 0x7d, 0xcc, 0xff, 0x72, 0x21,
    0xb8, 0x08, 0x46, 0x74, 0xf7, 0x43, 0x24, 0x8e,
    0xe0, 0x35, 0x90, 0xe6, 0x81, 0x3a, 0x26, 0x4c,
    /* 后续 128 字节省略 */
};

static void xxh3_accumulate_one(uint64_t *acc,
                                 const uint8_t *input,
                                 const uint8_t *secret) {
    for (int i = 0; i < ACC_NB; i++) {
        uint64_t data_val = xxh_read64(input + 8 * i);
        uint64_t key_val  = xxh_read64(secret + 8 * i);
        uint64_t xored    = data_val ^ key_val;

        uint32_t lo32 = (uint32_t)xored;
        uint32_t hi32 = (uint32_t)(xored >> 32);
        uint64_t product = (uint64_t)lo32 * (uint64_t)hi32;

        acc[i ^ 1] += data_val;
        acc[i]     += product;
    }
}

static void xxh3_scramble(uint64_t *acc, const uint8_t *secret) {
    for (int i = 0; i < ACC_NB; i++) {
        acc[i] ^= acc[i] >> 47;
        acc[i] ^= xxh_read64(secret + 8 * i);
        acc[i] *= PRIME32_1;
    }
}

void xxh3_hash_long(uint64_t *acc,
                     const uint8_t *input, size_t len) {
    static const uint64_t init_acc[8] = {
        PRIME32_1, PRIME64_1, PRIME64_1, PRIME64_1,
        PRIME64_1, PRIME32_1, PRIME64_1, PRIME32_1
    };
    memcpy(acc, init_acc, sizeof(init_acc));

    size_t nb_stripes = (len - 1) / STRIPE_LEN;
    size_t stripes_per_block = 16;

    for (size_t s = 0; s < nb_stripes; s++) {
        const uint8_t *stripe = input + s * STRIPE_LEN;
        size_t secret_off = (s % stripes_per_block) * 8;

        xxh3_accumulate_one(acc, stripe,
                             xxh3_secret + secret_off);

        if ((s + 1) % stripes_per_block == 0) {
            xxh3_scramble(acc, xxh3_secret + 128);
        }
    }
}

两份代码的对比揭示了设计哲学的巨大差异：xxHash3 需要 accumulate + scramble + 多路分发 + 终结化，而 wyhash 全部逻辑在一个函数里完成。

九、SMHasher 质量测试

什么是 SMHasher

SMHasher 是 Austin Appleby（MurmurHash 的作者）创建的哈希函数质量测试套件。现在最活跃的版本是 Reini Urban 维护的 SMHasher3。它包含上百个统计测试，覆盖以下几个核心维度。

Avalanche（雪崩测试）

翻转输入的每一个比特，检查输出中翻转的比特数是否接近 50%。理想的哈希函数满足严格雪崩准则（SAC）：改变输入的任意一位，输出的每一位都有 50% 的概率翻转。

Avalanche test results (max bias, < 1% = PASS):
  xxHash3         0.04%   PASS
  wyhash          0.08%   PASS
  rapidhash       0.06%   PASS
  CityHash64      0.12%   PASS
  FNV-1a         49.21%   FAIL (几乎没有雪崩效应)
  MurmurHash3     0.15%   PASS

Bias（偏差测试）

检查输出的每个比特位是否有统计偏差。理想情况下每个位为 0 和 1 的概率都是 50%。测试生成大量随机输入的哈希值，统计每个输出位的偏差。

Collision（碰撞测试）

生成大量键（通常是数百万甚至数十亿个），检查碰撞数是否符合生日悖论的期望值。对于一个理想的 64-bit 哈希函数，在 2^32 个键中期望碰撞次数约为 0.5。

Collision test (4 billion 32-bit keys -> 64-bit hash):
  xxHash3         0 collisions (expected ~0.5)   PASS
  wyhash          1 collision  (expected ~0.5)    PASS
  CityHash64      0 collisions                   PASS
  FNV-1a          4217 collisions                FAIL

Distribution（分布测试）

检查哈希值在输出空间中是否均匀分布。常用方法包括：

• 卡方检验：将输出空间分成若干桶，检查每个桶的计数是否符合均匀分布
• 串行相关性检验：检查连续哈希值之间是否有相关性
• 位独立性检验：检查不同输出位之间是否独立

如何解读测试结果

SMHasher 的输出格式通常是：

--- Testing xxHash3 ---
[[[ Sanity Tests ]]]              PASS
[[[ Speed Tests ]]]               3.1 bytes/cycle (bulk)
[[[ Avalanche Tests ]]]           PASS  (max bias 0.04%)
[[[ Keyset 'Zeroes' Tests ]]]     PASS
[[[ Keyset 'Seed' Tests ]]]       PASS
[[[ Keyset 'Sparse' Tests ]]]     PASS
[[[ Diff Tests ]]]                PASS
[[[ MomentChi2 Tests ]]]          PASS

关键指标：

• bytes/cycle：越高越好。xxHash3 约 3.1 B/cycle（标量），wyhash 约 2.8 B/cycle
• max bias：雪崩偏差，低于 1% 即可接受，低于 0.5% 为优秀
• Keyset 测试：各种特殊模式的输入（全零、稀疏位、递增序列等），全部 PASS 才算合格

wyhash 和 xxHash3 都通过了 SMHasher3 的全部测试。FNV-1a、DJB2 等古老的哈希函数则在多项测试中失败。

十、基准测试

短键延迟

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

8-byte key latency (cycles):
  wyhash           ||||    5
  rapidhash        ||||    5
  xxHash3          ||||||||  8
  FarmHash         |||||||||  9
  MurmurHash3-x64  ||||||||||||  12
  CityHash64       |||||||||||||  13
  SipHash-1-3      ||||||||||||  12
  SipHash-2-4      ||||||||||||||||||  18

16-byte key latency (cycles):
  wyhash           ||||||  6
  rapidhash        ||||||  6
  xxHash3          ||||||||||  10
  Komihash         ||||||||  8
  MurmurHash3-x64  |||||||||||||||||  17
  SipHash-1-3      ||||||||||||||||  16
  SipHash-2-4      ||||||||||||||||||||||||  24

观察：

• wyhash/rapidhash 在短键上最快（一次 MUM 操作就够了）
• xxHash3 比 wyhash 稍慢（短键路径有更多分支和 avalanche 步骤）
• SipHash 明显更慢，但提供了安全性保证

长输入吞吐量

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

Throughput (GB/s) -- data in L1 cache (32 KB):
  xxHash3(AVX2)   ||||||||||||||||||||||||||||||||||||||||  42.0
  xxHash3(SSE2)   ||||||||||||||||||||||||||||  28.0
  wyhash          ||||||||||||||||||||||||||||||||||  34.0
  rapidhash       |||||||||||||||||||||||||||||||||||  35.0
  Komihash        ||||||||||||||||||||||||||||||  30.0
  CityHash128     ||||||||||||||||||||  20.0
  SipHash-2-4     |||||||  7.5

Throughput (GB/s) -- data in DRAM:
  xxHash3(AVX2)   ||||||||||||||||||||||||||||||||||||||||  28.0
  wyhash          ||||||||||||||||||||||||||||||||||||  25.0
  rapidhash       |||||||||||||||||||||||||||||||||||||  26.0
  CityHash128     ||||||||||||||||||||  14.0
  SipHash-2-4     ||||||  2.5

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

不同输入长度的综合对比

Throughput (bytes/cycle) by input length:

Length    xxHash3   wyhash   CityHash  SipHash-2-4
  4 B      0.50     0.80     0.31       0.22
  8 B      1.00     1.60     0.62       0.33
 16 B      1.60     2.67     1.23       0.57
 32 B      2.13     2.91     1.78       0.71
 64 B      3.56     3.20     2.46       0.89
128 B      5.33     3.37     2.84       0.94
256 B      7.11     3.43     2.91       0.97
  1 KB     8.00     3.47     2.95       0.98
  4 KB     8.40     6.80     3.01       1.00
 64 KB     8.40     6.80     3.01       1.00

明显的交叉点：在约 64 字节以下，wyhash 更快；64 字节以上，xxHash3 逐渐拉开差距。这正好对应了两者的设计目标——wyhash 优化短键延迟，xxHash3 优化长输入吞吐。

十一、工程陷阱清单

十二、个人观点

为什么 wyhash 是小键之王

在哈希表的实际使用中，键长度的分布高度偏斜：整数键（8 字节）、短字符串（16-32 字节）占了绝大多数。超过 128 字节的键极为罕见。

wyhash 处理一个 8 字节键只需要 5 个周期——一次 seed 预混合，一次读取 + XOR，一次 MUM 乘法。没有分支，没有循环，没有表查找。这是物理极限附近的延迟——你不太可能在保持同等质量的前提下做得更快了。

xxHash3 处理同样的 8 字节键需要 8 个周期。多出的 3 个周期来自更复杂的分支结构和更强的 avalanche 步骤。对于哈希表场景，这 3 个周期的差距可以转化为 5-10% 的端到端性能差异。

为什么 xxHash3 是大块之王

当输入超过几百字节后，wyhash 的 3 组 MUM 并行（48 字节/迭代）开始触及天花板——受限于乘法单元的吞吐和 load 端口的带宽。xxHash3 的 8 路 SIMD 累加器（64 字节/迭代，AVX2 一条指令处理 32 字节）仍有充裕的算力余量。

在 L1 cache 中，xxHash3（AVX2）比 wyhash 快约 24%。在 DRAM 中差距缩小到约 12%——因为内存带宽成了共同的瓶颈。

ILP 比 SIMD 更普适

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

如果你只能维护一套代码，wyhash 的”标量代码 + 隐式 ILP”策略是更明智的选择。只有当你像 Yann Collet 那样愿意为 AVX2、SSE2、NEON、标量各写一套实现并长期维护时，xxHash3 的策略才值得采用。

128-bit 乘法是被低估的原语

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

如果未来 SIMD 指令集引入了原生的 64x64 到 128 位向量乘法（比如 SVE2 或 AVX 的未来扩展），显式 SIMD 哈希的优势会更加明显。但在那之前，MUM 策略仍然是最高效的。

最好的 SIMD 哈希可能不需要你写 SIMD

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

系列导航： - 上一篇：密码学哈希 vs 非密码学哈希 - 下一篇：红黑树 vs AVL

相关阅读： - Swiss Table：Google 的 SIMD 加速哈希表 - SIMD 算法设计模式