主要观点:在业余时间开发 GxHash 时,作者通过不断优化得出“Unsafe Read Beyond of Death”(URBD)这一最厉害的优化方法,以使其成为至今最快的非加密哈希算法。
关键信息:
- 为实现最大性能,GxHash 设计目标之一是尽可能使用 SIMD 指令,输入数据需为 16 或 32 字节的倍数,其他依赖 SIMD 的哈希算法处理不均匀部分较慢。
- 原安全方法是将不均匀部分复制到零初始化临时缓冲区再加载到 SIMD 寄存器,虽简化代码但有性能成本(复制操作)。
- 为避免复制操作,尝试读取输入缓冲区末尾之外的字节(危险操作),可大幅提高小负载的速度,但会哈希不属于流的字节并可能使程序崩溃。
- 避免读取缓冲区末尾之外字节的技巧是确保缓冲区末尾在同一页,通过检查地址与页面大小的关系来判断。
- 安全读取超出部分后,用 SIMD 指令创建常量向量并与流长度比较生成掩码,应用于向量以屏蔽不属于流的字节。
- 读取 16 字节向量时会丢失不均匀部分长度的上下文,通过将不均匀部分长度包装加到掩码向量的每个字节来解决。
- 另一个优化技巧是先读取不均匀部分,再读取 16 字节块,对于大于 16 字节的输入可假设读取缓冲区末尾之外是安全的。
- 最终的 URBD 优化代码包含安全检查、快速路径(不安全读取)和回退路径(安全复制)。
重要细节: - 代码中使用
#[cfg(target_arch = "x86_64")]
进行架构配置,定义了State
类型为__m128i
,并通过各种unsafe
函数实现相关操作。 - 性能测试图表显示 GxHash 在各种负载下速度最快,给出了与其他哈希算法的吞吐量对比数据。
- 源代码可在GxHash 仓库找到。
**粗体** _斜体_ [链接](http://example.com) `代码` - 列表 > 引用
。你还可以使用@
来通知其他用户。