比你想象中更快地计数字节

主要观点

  • 作者受之前受欢迎的文章启发,在 HighLoad 上接受新挑战“Counting uint8s”,目前在排行榜居第 13 位,约落后第 1 名 7%,且已学到一些有趣的东西。
  • 介绍解决该挑战的完整方案,包括相比朴素顺序访问能提高约 30%传输速率的令人惊讶的内存读取模式。
  • 详细阐述内核的工作原理,通过几个指令对输入的 32 字节块进行处理和累加计数。
  • 重点介绍内存交错访问模式(交错 8 页)及预取 4 个缓存行 ahead 的优化方法,实验表明能显著提高性能。

关键信息

  • 输入为 250MB 全字节均匀采样的文件,找出值为 127 的字节数量。
  • 内核仅三指令长,通过vmovntdqa加载块,vpcmpeqb比较字节与 127,vpsubb进行减法累加。
  • 为防止窄累加器溢出,用vpsadbwvpaddq进行累加操作。
  • 内存交错访问模式可提高性能约 15%,预取 4 个缓存行 ahead 能在更内存受限情况下获得最多 30%增益。

重要细节

  • 程序针对 Intel Xeon E3-1271 v3 @ 3.60GHz、512MB RAM、Ubuntu 20.04 系统优化,仅使用 AVX2 ,未使用 AVX512。
  • 完整源代码包含多个函数和循环,通过内存映射读取输入文件,进行字节计数操作。
  • 给出不同预取步长的运行时实验图,展示预取 4 个缓存行 ahead 时性能最佳。
阅读 15
0 条评论