全新高质量哈希算法在 M4 上测得 71GB/s 的速度

New high-quality hash measures 71GB/s on M4

Source | HN Comments

文章介绍了一种名为 `rapidhash` 的全新哈希算法，该算法具有快速、高质量和平台独立的特点。它在 Apple M4 芯片上测得高达 71GB/s 的速度，是 `SMHasher` 和 `SMHasher3` 测试中最快的哈希函数。`rapidhash` 是 `wyhash` 的继任者，针对 AMD64 和 AArch64 系统进行了优化，并兼容多种编译器。文章还提供了关于碰撞率的测试数据，表明其碰撞概率接近理想值。

Nicoshev / **rapidhash ** 公开

非常快速、高质量、平台独立的哈希算法。

许可

查看许可 345 颗星 22 个 Fork 分支标签活动

rapidhash - 非常快速、高质量、平台独立

SMHasher 推荐的最快哈希函数。

SMHasher3 中通过测试的最快哈希。

rapidhash 是 wyhash 的官方继任者，具有更高的速度、质量和兼容性。

快速: 对于短输入和长输入都非常快。在 Apple 的 M4 芯片上超过 70GB/s 。是通过 SMHasher 所有测试的最快哈希函数。是通过 SMHasher3 所有测试的最快哈希函数。

通用: 针对 AMD64 和 AArch64 系统进行了优化。兼容 gcc, clang, icx 和 MSVC。它不使用特定于机器的向量化或加密指令集。为 C 和 C++ 编译做好准备。

优秀: 通过了 SMHasher 和 SMHasher3 中的所有测试。基于碰撞的研究表明，碰撞概率低于 wyhash，接近理想值。使用 16B 和 66B 密钥的数据集进行测试时，具有出色的碰撞率：

| Input Len | Nb Hashes | Expected | Nb Collisions | |---|---|---|---| | 8 | 15 Gi | 7.0 | 3 | | 12 | 15 Gi | 7.0 | 4 | | 16 | 15 Gi | 7.0 | 8 | | 24 | 15 Gi | 7.0 | 7 | | 32 | 15 Gi | 7.0 | 3 | | 40 | 15 Gi | 7.0 | 3 | | 64 | 15 Gi | 7.0 | 8 | | 80 | 15 Gi | 7.0 | 6 | | 120 | 15 Gi | 7.0 | 5 | | 128 | 15 Gi | 7.0 | 6 | | 160 | 15 Gi | 7.0 | 9 | | 1024 | 15 Gi | 7.0 | 7 | | 4096 | 15 Gi | 7.0 | 8 | | 8 | 62 Gi | 120.1 | 123 | | 12 | 62 Gi | 120.1 | 108 | | 16 | 62 Gi | 120.1 | 102 | | 24 | 62 Gi | 120.1 | 112 | | 32 | 62 Gi | 120.1 | 137 | | 48 | 62 Gi | 120.1 | 149 | | 64 | 62 Gi | 120.1 | 161 | | 120 | 62 Gi | 120.1 | 172 | | 128 | 62 Gi | 120.1 | 187 | | 160 | 62 Gi | 120.1 | 183 |

更多结果可以在 collisions 文件夹中找到

出色的性能

对 4、8 和 16 字节的密钥进行哈希时的平均延迟

| Hash | M1 Pro | M3 Pro | Neoverse V2 | AMD Turin | |---|---|---|---|---| | rapidhash | 1.79ns | 1.38ns | 2.07ns | 2.31ns | | xxh3 | 1.92ns | 1.50ns | 2.15ns | 2.35ns |

哈希 16Kb-2Mb 文件时的峰值吞吐量

| Hash | M1 Pro | M3 Pro | M3 Ultra | M4 | Neoverse V2 | |---|---|---|---|---|---| | rapidhash | 47GB/s | 57GB/s | 61GB/s | 71GB/s | 37GB/s | | xxh3 | 37GB/s | 43GB/s | 47GB/s | 49GB/s | 34GB/s |

基准测试程序可以在 bench 文件夹中找到

基于碰撞的哈希质量研究

一个完美的哈希函数将其域均匀地分布到图像上。当域的基数是图像基数的倍数时，每个潜在输出具有相同的产生概率。产生 64 位哈希值的函数应该具有 $p=1/2^{64}$ 的生成每个输出的概率。

如果我们计算 $n$ 个哈希值，则碰撞的预期量应该是唯一输入对的数量乘以生成给定哈希的概率。这应该是 $(n*(n-1))/2 * 1/2^{64}$，或简化为：$(n*(n-1))/2^{65}$。在哈希 $15*2^{30}$ (~16.1B) 个不同密钥的情况下，我们应该期望看到 $7.03$ 个碰撞。

我们提出了一个实验，其中我们使用 rapidhash 来哈希 $77$ 个数据集，每个数据集包含 $15*2^{30}$ (15Gi) 个密钥。对于每个数据集，记录产生的碰撞量作为测量值。理想情况下，测量值之间的平均值应为 $7.031$，并且结果集合应为二项式分布。我们获得的平均值为 $8.026$，仅比 $7.031$ 高 $14$%。每个数据集的单独结果和碰撞测试程序都可以在 collisions 文件夹中找到。在所有实验中都使用了默认种子 $0$。