Cache Unfriendly Program and Judging Issues

Migrated from old blog, with minor changes. If you can’t read Chinese but are interested in this topic, mail me.

缓存不友好的程序及相关评测问题

在 2016 年西电 ACM/ICPC 校赛的最后准备工作中,为了测试评测效率, 本人写了一道题目( XDOJ 1152 )的效率极其低劣的代码。 提交这一代码后,果然得到了预期的上千毫秒的运行时间。 于是本人开心地徒手把这个代码交了几次,结果令人吃惊的事情发生了: 这些提交全都超时了!把时间限制改大,再进行测试,发现了下列经验规律:

xdoj1152_bad.cc 编译后,若在 k 个进程中同时运行产生的目标代码, 则每个进程耗费的用户态 CPU 时间都是单独在一个进程中运行目标代码所耗费的 k 倍。

这是非常诡异的,而且在实际评测中可能导致相同的提交有时通过, 有时(服务器重载时)超时! 于是fpcsong巨巨花了一个通宵进行调试, 最终得到的结论是这一问题暂时无法解决, 且在无数代码中只有这份代码会导致这一问题,因此就先这样进行比赛了。 幸运的是,并没有人把代码写成我这样,因此没有触发这个问题。

后来大家就把这件事忘了,不料在 2016 年的暑期集训中,这个问题又出现了。 这道题目是 XDOJ 1179。 本人求解这一问题的代码在这里。 注意这份代码并不像上次那样,是一份专门编写的效率低劣的代码,而是正确的解法 其他选手解决这道题的代码也是大同小异的。结果在吃了两个答案错以后, 本人发现输入数据有错,就呼叫命题人做了改正。之后裁判要进行重判, 重判时自然是十几发针对这题的提交一起运行。于是,再一次地,所有提交都超时了。 本人向裁判通知了上次出现的问题,并告诉他我也没有什么办法。 最终裁判只得手工对所有提交一个一个重测。

与上次故意折磨评测机不同,这次的奇怪现象完全是在对正常程序的评测中发生的。 因此,必须找出这一现象的根源。我们提出了下列几个可能的原因:

  1. XDOJ 计时系统故障。
  2. Linux 内核计时系统故障。
  3. Glibc 在 I/O 操作中对某个系统共享资源进行轮询。
  4. 磁盘 I/O 拥堵。

其中 4 首先被排除。在现代的 x86-64 计算机系统中,磁盘控制器都装备了 DMA , 磁盘 I/O 几乎不会消耗任何 CPU 时间。更重要的是, XDOJ 会把待测的程序和输入文件放在 tmpfs 中, 所以在程序运行时根本就没有磁盘 I/O。

然后是 1 ,用/usr/bin/time进行了类似的测试, 同样得到并行环境下 CPU 时间变长的结果。可见,除非这两个计时系统同时故障, 否则 XDOJ 就是运行良好的。

至于 2 和 3,除非我们假设 Linus 和 Glibc 的开发者都是笨蛋, 他们才不会解决这种明显的问题,而这是不可能的。

于是所有假设都被毙掉了。为了找出真正的原因,我们使用 profiler 对上述两段代码(下面以 xdoj1152_bad.cc 为例)进行计时分析。 gprof 没有给出什么有用的信息,为了获取尽可能多的信息, 采用 Linux 内核开发者提供的 perf 工具对代码进行采样分析, 结果发现了问题。无论是单独执行一个进程,还是并发执行两个进程, 每进程执行的机器指令条数都为 1.15 亿条左右。可见,Glibc 很好地完成了工作, 并没有在并行条件下消耗更多的指令。 然而,连 perf 工具本身都注意到了令人不安的事情,并用红字给出:

单次执行:

2,178,115,949 stalled-cycles-frontend:u # 85.75% frontend cycles idle

翻译成人话,就是有大量时钟周期未能进行有用的工作,因为流水线发生了阻塞, CPU 只能空转。那么,并行执行的情况如何呢?

并行执行:

4,664,914,578 stalled-cycles-frontend:u # 93.31% frontend cycles idle
4,667,261,704 stalled-cycles-frontend:u # 93.28% frontend cycles idle

看上去只提高了几个百分点,并没有什么问题,但是看一下前面的数就傻眼了: 空转周期数增加了一倍以上!注意这样的空转是 CPU 内部的数字电路在空转, 操作系统根本不知道发生了什么。在操作系统看来,每条指令执行的时间都变长了, 它又不能强行打断指令进行调度。因此,空转的时间都是要算进进程 CPU 时间的, 这就导致 CPU 时间的加倍。至于百分比的变化比较小,只是因为有用周期太少, 空转周期的比例已经接近 100% ,自然增长缓慢了。

那么,难道 Intel 的工程师都是笨蛋吗, 为什么好好的双核 CPU (我的笔记本)跑两个进程就会导致这么多时钟周期空转呢? 并不是这样的。我们用 perf stat -d 显示一下存储器访问事件,就会发现

单次执行:

141,661,244 L1-dcache-load-misses:u # 123.13% of all L1-dcache hits

也就是说,这程序执行的时候, L1 缓存几乎没有命中过。 读一下代码也能直观地看到,该程序不断地将字符串复制到内存中几乎随机的位置, 毫无局部性可言。xdoj1179.cc 也一样,不断对数组f进行跳跃式的访问, 必然会导致大量缓存 miss。

L1 miss 本身并不是什么可怕的问题, 然而它揭示出了这两段“奇异”代码局部性差的本质。 这样的代码几乎一定会继续导致 L2、L3 缓存的 miss 。 此时 CPU 就必须从内存寻找数据填充缓存,于是两个核心开始争用内存总线, 当一个核心访问数据时,另一个核心就要空转。 这就导致大量时钟周期被白白浪费掉了。

那么,如何解决这个问题呢?

  • 鸵鸟法,即假装这个问题不存在。 对于 xdoj1152_bad.cc 这样的奇葩解法和暑期集训这种小规模提交来说,
    几乎不会出现内存争用的问题。 然而,如果像 XDOJ 1179 这样的题目出现在大规模比赛(如校赛)中, 后果一定是灾难性的。

  • 改变计时规则,采用指令数估计“无干扰”的运行时间。 初看上去这很好,然而编写常数更小的程序也是选手能力的一部分, 如果只考虑指令条数,就为随便胡乱取模、 编码完全不考虑局部性的选手大开方便之门,反而对了解缓存体系的选手不公平。

  • 采用多台评测机,每台一次只评测一个提交。现场赛就采用这种方法, 而且把 XDOJ 服务器卖了,拿钱买十几台低端 PC 也不是什么困难的事情, 但是这会导致 OJ 的开发和维护工作都变困难。

  • 采用 NUMA。NUMA 是解决这类内存争用问题的标准方案,即装配多套内存控制器, 并将它们和 CPU 核心按照合理的拓扑结构进行互联。 实际上现在的 XDOJ 服务器就是简单的 NUMA 结构,拥有两套内存控制器, 分别与一半数量的 CPU 核心交互。当然,这么简单的结构是无法解决我们的问题的, 它只是解决了在主板上安装两个 CPU 的问题。 如果能够设计更加复杂和精巧的 NUMA 拓扑结构,就能很好地解决内存争用问题。 然而,我们并没有钱购买强大的 NUMA 服务器。

  • … … 还是鸵鸟法吧。

虽然我们无法彻底解决这一问题,但还是可以提供一些有用的提示:

  • 从出题人的角度来说,要注意减小标准解法的工作集,不要为了吓人强行加大数据。 这样做只会增加缓存 miss,从而增大常数,反而可能导致暴力跑得都比正解快。

  • 从选手的角度来说,要注意减小自己程序的工作集。 某些选手上来就把所有整数全写成 64 位,反正内存限制是 128MB 又爆不了, 而且评测机是 64 位的,理论上 64 位算术和 32 位一样快。 然而,这样工作集就会直接增大一倍。如果存在跳跃访问,这还会增大访问步长, 从而增大跨越内存页面的访问,严重干扰硬件预取,更加恶化缓存性能。 比如说,对于 xdu1179.cc,根据题目描述的限制, 将数组 f 改为使用 8 位整数 (xdu1179_better.cc), 可以将运行时间从 3.0s 降低到 1.8s 。

  • 从 OJ 开发和运维的角度来说, 可以考虑对某些题目强行串行评测。另外,注意及时更新 CPU 微码, 有时能够提高缓存命中率。

  • 从科研人员的角度来说,买工作站的时候要注意考虑内存总线带宽和缓存大小, 而不是只数 CPU 核心和看主频。在进行计算时, 要使用性能分析工具分析计算程序的工作状态,并调整系统参数或适当升级硬件, 使之达到最佳状态。

最后推荐 Brendan Gregg 的一篇文章

Xi Ruoyao
Xi Ruoyao
PhD Student

Retired from ICPC, now a PhD student and an assistant ICPC coach (with no salary).