超出死亡范围的不安全读取

主要观点:在业余时间开发 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 仓库找到。
阅读 10
0 条评论