在 Haswell 上以 memcpy 的速度对 ASCII 编码整数求和

主要观点:

  • 要打印从([0, 2³¹−1])均匀采样的 5000 万 ASCII 编码整数的和,需快速完成,作者是某挑战的顶级竞争者,将展示最佳解决方案。
  • 其程序比朴素的 C++ 解决方案快约 320 倍,但更脆弱,约 1000000 倍,后续会详细介绍初始化稀疏查找表的技术。
  • 程序针对输入规格和特定主机进行了优化,仅使用到 AVX2 指令,假设输入符合规格,零错误处理,结果概率接近 1 但非 1。
  • 算法通过 SIMD 迭代输入的 32 字节块,从后往前,跟踪每个十进制位的数字和,最后通过乘以 10 的幂得到最终和,关键是查找表确定字节的十进制位。

关键信息:

  • 定义了各种变量如输入指针、偏移量等,常量如 ASCII 码等。
  • 先处理输入字节对齐,再进行性能关键部分,预取输入,加载 32 字节块,处理换行符和左数长度,获取查找表索引,进行字节洗牌和累加。
  • 累加到一定数量的块后将累加和存入数组,最后乘以 10 的幂得到最终和并输出。

重要细节:

  • 查找表索引计算方式特殊,避免了按正常方式计算导致的缓存关联问题。
  • 字节洗牌部分利用了特定输入分布,尽量在 2 次洗牌内完成累加以避免错误结果。
  • 处理左数长度时在 Haswell 上会生成额外指令,目前不知如何绕过。
阅读 10
0 条评论