主要观点:
- 要打印从([0, 2³¹−1])均匀采样的 5000 万 ASCII 编码整数的和,需快速完成,作者是某挑战的顶级竞争者,将展示最佳解决方案。
- 其程序比朴素的 C++ 解决方案快约 320 倍,但更脆弱,约 1000000 倍,后续会详细介绍初始化稀疏查找表的技术。
- 程序针对输入规格和特定主机进行了优化,仅使用到 AVX2 指令,假设输入符合规格,零错误处理,结果概率接近 1 但非 1。
- 算法通过 SIMD 迭代输入的 32 字节块,从后往前,跟踪每个十进制位的数字和,最后通过乘以 10 的幂得到最终和,关键是查找表确定字节的十进制位。
关键信息:
- 定义了各种变量如输入指针、偏移量等,常量如 ASCII 码等。
- 先处理输入字节对齐,再进行性能关键部分,预取输入,加载 32 字节块,处理换行符和左数长度,获取查找表索引,进行字节洗牌和累加。
- 累加到一定数量的块后将累加和存入数组,最后乘以 10 的幂得到最终和并输出。
重要细节:
- 查找表索引计算方式特殊,避免了按正常方式计算导致的缓存关联问题。
- 字节洗牌部分利用了特定输入分布,尽量在 2 次洗牌内完成累加以避免错误结果。
- 处理左数长度时在 Haswell 上会生成额外指令,目前不知如何绕过。
**粗体** _斜体_ [链接](http://example.com) `代码` - 列表 > 引用
。你还可以使用@
来通知其他用户。