+++
date = 2018-08-01T18:50:00+08:00
draft = false
tags = ["cache", "XDOJ-next"]
title = "Cache Unfriendly Program and Judging Issues"
summary = """
Some problems and solutions have caused strange behavior of XDOJ judging
system: when multiple solutions are executed simultaneously, the CPU time
consumed by **each** solution grows linearly with the number
of solutions. In this post we would reveal that these problems and
solutions are cache unfriendly in nature, and it's the memory model of
modern computers which leads to the behavior.
"""
authors = ["xry111"]
+++

{{% callout note %}}
Migrated from old blog, with minor changes.  If you can't read Chinese
but are interested in this topic, mail me.
{{% /callout %}}

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

在 2016 年西电 ACM/ICPC 校赛的最后准备工作中，为了测试评测效率，
本人写了一道题目（
[XDOJ 1152](http://acm.xidian.edu.cn/problem.php?id=1152)
）的效率极其低劣的[代码](/files/cache-unfriendly/xdu1152_bad.cc)。
提交这一代码后，果然得到了预期的上千毫秒的运行时间。
于是本人开心地徒手把这个代码交了几次，结果令人吃惊的事情发生了：
这些提交全都超时了！把时间限制改大，再进行测试，发现了下列经验规律：

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

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

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

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

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](/files/cache-unfriendly/xdu1179_better.cc)），
可以将运行时间从 3.0s 降低到 1.8s 。

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

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

最后推荐 [Brendan Gregg 的一篇文章][2]。

[2]: http://brendangregg.com/blog/2017-05-09/cpu-utilization-is-wrong.html