Strongly universal string hashing is fast
Owen Kaser, Daniel Lemire
cs.DB, cs.DS
2012-02-23
Multilinear 哈希用普通 64 位乘加实现、右移取高 32 位即强通用,桌面 CPU 上 0.2~0.5 周期/字节,比 Rabin-Karp 快 1.7 倍以上。
哈希表、布隆过滤器、基数估计、集合求交,这些数据结构的性能保证都建立在「哈希函数够随机」上。教科书答案是从强通用(strongly universal)哈希族里随机抽一个函数:任意两个不同输入的哈希值严格独立。现实工程里跑的却是 Rabin-Karp、SAX 这类没有任何理论保证的函数,理由是快。这篇在 12 颗处理器上实测给出的答案相反:在 64 位桌面与服务器 CPU 上,强通用方案不仅不慢,还普遍快 1.73.3 倍。
顺带检验了两条行业常识:「乘法次数越少越快」「有限域运算有硬件指令(CLMUL)加持就该用有限域」。两条都没站住。
Multilinear 哈希本来定义在有限域上:h(s) = m1 + Σ m(i+1)·si,系数 m 是随机数。它在域上是强通用的,但有限域乘法的软件实现很贵。
这篇的核心构造把 Dietzfelbinger 1996 年处理单个整数的技巧推广到字符串:同样的内积放进普通 64 位无符号运算,全程不取模,算完右移 32 位只取高 32 位。定理 3.1 证明这样得到的族仍是强通用的。证明的关键可以一句白话讲清:乘以奇数在 mod 2^64 下是双射;乘数带 τ 个尾部二进制零时低位确实丢信息,但命题 3.1 证明方程 (ax+c) mod 2^K ÷ 2^(L-1) = b 恰好有 2^(L-1) 个解,解的数目分毫不差,独立性因此保住。
落到 C 代码就是三行循环:sum += m p,最后 return sum >> 32。每个 32 位字符一次乘法一次加法,共 2n+1 次操作,距离计数下界最多差 2 倍。
乘法减半的变体 Multilinear-HM 用恒等式把相邻两个标量积并成一次乘法:(m2i+s(2i-1))·(m(2i+1)+s(2i))。变长字符串在结尾补一个字符 1(保证不以 0 结尾),或把长度拼进首字符。
账单在随机数:每 32 位输入字符要配 64 位随机数。Stinson 下界表明强通用本身就需要约 32(n+1) 位随机性,这笔内存开销省不掉,是结构性价格。
64 位处理器、32 位哈希值,单位为每字节 CPU 周期(摘自 Table 2/3):
| 处理器 | 最佳 Multilinear | Rabin-Karp | SAX |
| Intel i7-2677M | 0.20 | 0.64 | 0.82 |
| Intel Core 2 Duo | 0.52 | 1.3 | 1.3 |
| AMD FX8150 | 0.51 | 0.86 | 1.3 |
八颗 64 位桌面/服务器处理器上,理论保证最强的方案全线领先。
乘法减半的 Multilinear-HM 只在 AMD(快约 33%)和 VIA(快 45%)赢;Intel 上与乘法数翻倍的版本打平,作者归因于 Intel 的乘法流水线。ARM 上更反直觉:带乘加指令的 Apple A4 与 Tegra 2,乘法最多的 2-by-2 循环展开版反而最快。
CLMUL 路线全面落败。i7-2600 上最快的 GF 变体 1.1 周期/字节,是 Multilinear-HM(0.27)的 4 倍慢,瓶颈在 Intel 当时代码每 8 个周期才完成一次无进位乘法的吞吐上限。软件有限域库 mpFb 慢一个数量级(4 kB 字符串 7.69 µs,整数版 0.78 µs);GMP 512 位大字运算慢 12 倍;GCC uint128 扩展慢 38%。
唯一能打的是 NH,UMAC 作者的 almost universal 方案:八颗里五颗基本打平,i7-2600、i7-2677M、FX8150 三颗上 NH 明显更快(0.16 对 0.27、0.12 对 0.20、0.17 对 0.51)。NH 省约一半随机位,但输出必须 64 位宽才有同等的 1/2^32 碰撞概率,且不满足均匀性。放弃保证换速度,在五分之三的芯片上换不到。
32 位嵌入式是另一个世界:Atom N270 上最佳 Multilinear 要 3.6 周期/字节,Rabin-Karp 只要 1.1。结论明确限定在 64 位桌面/服务器。
随机化哈希是哈希表对抗哈希洪泛攻击的标准手段:攻击者构造同桶键,把插入拖回平方级时间,Ruby 1.9 与 Perl 5.8.1 因此内置随机化。这篇把「上强通用会慢」的借口拿掉了:64 位服务器 CPU 上理论最硬的方案就是最快的,只用普通整数乘法,不需要 SIMD,不需要特殊指令集。
方法论的教训比数字更长寿:在超标量 CPU 上数操作数会得出错误结论。乘法一旦进入流水线就近乎免费,省乘法的代数技巧可能白做甚至倒贴。任何以「少几次乘法」为卖点的优化,都该先过基准测试再谈证明。
做 sketch、cuckoo hashing、集合交这类依赖 pairwise independence 的算法,这里有可以直接抄的三行实现。
随机数缓冲是真成本:哈希 4 kB 输入要消耗 8 kB 随机材料,生成、存储、缓存行为都是开销,作者自己称之为「主要困难」。Stinson 下界保证这不是实现问题,是强通用固有的价格。
计时条件是实验室最优:同一条随机字符串反复哈希,编译器 flag 逐个手工调优,作者注明进真实应用会因带宽与缓存变差。
硬件全部来自 20112012 年:Core 2 到 i7-2600、ARM A4、Tegra 2、GCC 4.x。「每 8 周期一次无进位乘法」是那一代 Intel 的数字,现代 CPU 的 CLMUL 吞吐高得多,这条判决值得在当前芯片上重跑;乘法流水线更深,「省乘法无用」的方向上只会更成立。
文中还留了一个小猜想:对任意 L 都存在满足 degree(p(x)−x^L) ≤ L/2 的不可约多项式,这是 Barrett 约化提速的前提,没给证明。