代码优化卷翻天：莫队交易赛复盘（下）

APSchmidt · 发表于 2022-3-11 12:55

两周前我参加了一场高频交易模拟赛，这一系列文章是我对这场为期一周比赛的复盘总结。在前两篇中我主要记录了从比赛开始到资格赛为止，我对程序做的各种优化手段和技巧。转眼两周时间过去了，曾经比赛时的那股激情也逐渐平复下来，是时候谈谈这一周经历带给我的感触和思考了。不过在此之前，我们先快速回顾一下比赛题目和决赛过程，然后揭晓其他选手使用的神奇策略吧。
比赛题目

给定一个实时推送的数字流，从中找出长度不超过 N 的连续数字串，满足其组成的正整数是任意 M 的倍数。其中给定常数：
N = 256
M1 = 20220217214410
M2 = 104648257118348370704723119
M3 = 125000000000000140750000000000052207500000000006359661
M4 = 3^50 * 7^30 * 11^20在比赛的前半阶段，我想到的做法是：对于每个 M，维护以当前位置结尾长度分别为 1-N 的数字串模 M 的余数，然后逐个追加数字递推后面的余数，公式为 $f_{i+1}=(f_i \times 10+x_i)\%M$ 。其中数据范围由 M 决定，分别可以放进 u64/u128/u192 整数类型计算。接下来我做的就是对这个计算过程的优化：第一篇文章介绍了对定长大整数类型实现乘加和取模运算的技巧，第二篇文章介绍了用 SIMD 加速数组运算的技巧。除此之外，第一篇文章中还提到了多线程和 TCP 链接等重要的优化技巧。
这些前期工作让我在决赛刚开始的时候短暂地获得第一，但随后又被其他选手纷纷超越。下面我们继续回放一下决赛过程，对细节不感兴趣的同学可以直接跳过看后面的内容。
比赛过程回放（决赛）

21. 模拟服务端测试

由于决赛时比赛服务器只对参赛选手的内网地址开放，其它机器无法访问，所以如何在不影响线上运行的同时进行调试就成了个问题。我们知道这个比赛是非常看重响应时延的，而且决赛时选手间的比拼已经卷进了 10us 量级。经过我的测试，一旦在比赛机器上进行编译等重 CPU 负载的工作，排名就会刷刷往下掉，说明此时程序的响应时延大大加长了（即使已经设置了实时调度和最高优先级）。
这样看来在比赛机上做测试是不太可能了。所以为了验证程序的正确性，我还是自己写了一个简单的服务端做 mock。它的数据生成方式非常简单，就是随机生成一些 M 的倍数，再随机生成一些数字串，最后随机地混合起来。如果我的程序识别出的数字串不符合服务端生成它的频率，就说明我的程序写错了。实践表明这个方法非常有用，多次识别出了程序中存在 bug，避免了直接上线出锅的惨剧发生。
22. 发现 M3 的质因数分解

虽然前面我对大整数运算做了很多优化，但最长的 M3 运算依然是开销很大的部分。我盯着 M3 = 125000000000000140750000000000052207500000000006359661 这个数字，陷入了久久的沉思：这明显是一个很有规律的数字，很有可能是精心构造出来的。我们把几个非零的部分拿出来分解一下试试看：
125 = 5 * 5 * 5
14075 = 5 * 5 * 563
522075 = 3 * 5 * 5 * 6961
6359661 = 3 * 3 * 3 * 7 * 7 * 11 * 19 * 23果然是这样。我们再数数 0，发现每一部分加上前导 0 都是 17 位，而 10^17 刚好在 u64 的表示范围内！这么看来应该把它表示成 10^17 进制做运算？但是这样似乎也没有什么好处……感觉真相近在眼前了，但就是隔了层窗户纸没法捅破，难受。
到最后我还是回到了质因数分解这条路上来，既然 factor 对此无能为力，那就试试更高级的工具吧！于是我打开了著名的 Wolfram Alpha，向它发出了灵魂之问：

结果没有响应。。。不管我问什么都没有响应，这破网属实不行！于是我继续搜索在线分解质因数的网站，终于找到了一家能够工作的，而且竟然支持分解 70 位：

https://zh.numberempire.com/numberfactorizer.php

原来是这样，我悟了。现在我还有点好奇它使用了什么算法能这么快分解大整数，但当时这都已经不重要了，赶快改代码卷上去要紧啊！
23. 回归单线程

到目前为止我的程序一直是以多线程模式在运行。虽然决赛机上有 2 vcpu，但后来我们意识到它其实只是一个物理核上的两个超线程（云厂商可真会做买卖）。这就意味着实际上我们只有一个核的计算资源，对计算密集型程序来说开两个线程几乎没有什么好处，还会增加线程之间同步的开销。

多线程模式下四个计算任务的平均时延（第二列）

于是我就把程序从多线程改回了单线程，并且彻底扬掉了 tokio，因为不再需要多线程调度器了。但是，我们依然需要一个后台线程来创建 TCP 连接，并通过 channel 发送给计算线程。这样改完以后，整体的计算时间并没有显著增加，反而使得第一个计算的 M1 平均时延降低到了 100us 以内。从排行榜上可以看出抢到前三的次数明显增加了，说明还是有一定效果的。
这一现象让我意识到，相比多线程自动调度来说，单线程具有计算顺序可控的优势。我们可以把计算量最小的放在第一个算，计算量最大的放在最后算，这样整体的平均时延是最低的。更进一步，在整体性能对别人没有明显优势的局面下，还可以使用田忌赛马的战术：优先处理自己最擅长的部分，放弃做的不好的部分。由于比赛规则接近于赢者通吃，因此通过合理地排列计算顺序，也能够抢到更多的分数。
最后还想说一下的是，我做这个优化通宵到了第二天早上 6 点。然而根据后来莫队放出的时延曲线图显示，还有不少选手也在同时通宵内卷，着实恐怖：

决赛第一天各位选手的平均时延曲线图，横轴是时间，纵轴是时延（单位us）。红圈内的后半夜时段仍有多条曲线时延显著降低。

24. 优化 SIMD 取模

19 日白天我一直没有什么新的想法，只好继续琢磨怎么对 SIMD 进行优化。SIMD 开销最大的还是在取模操作上，需要四次比较和减法。之前我们提到过，两个数的比较可以转化为先做减法然后看正负，所以其实比较和减法可以合在一起来做，使用开销较低的判断正负代替两个数的比较。

上图是优化后的比较减法代码和生成的汇编指令。不过我感觉这份指令可能并不是最优的，因为出现了两个 vpcmpgtq 比较指令，并且它们的比较对象 zmm4 和 zmm5 都是一开始生成的常数（zmm4 我看出来是 0，zmm5 没看懂它生成了啥）。理论上和 0 比较大小只需要看符号位，所以用 vptestnmq 就够了，开销一定比 cmp 要低。不过虽然我能看出这里指令还有优化空间，但却也没有什么好办法去手动纠正它，只能等待日后 Rust 编译器或者 SIMD 库来解决了。
指令有问题，自然性能也没有太好，结果和优化前基本持平。所以可以说到这里 SIMD 的性能基本没有多少提升空间了。
25. 莫队算法？

各种方向都已经走入了死胡同，接下来只能再想想算法了。这时候我灵光一闪，别忘了这个比赛的主办者是谁，那可是我 10 年前高一的时候就知道的莫队啊。当年学过的莫队算法，不就是解决区间查询问题的嘛，跟这个题目很像啊！虽说我除了“莫队算法”和“区间查询”这几个字以外就不记得别的东西了，但这些年在贵系摸爬滚打，也算练就了一身在考场上现场预习的本领，不慌！于是我打开 Google 开始集成学习莫队算法。

https://oi-wiki.org/misc/mo-algo/ 感谢 OI Wiki！

看着看着我就感觉不太对劲了。因为莫队算法是给定若干查询做离线处理，但这个题目里并没有给查询啊，或者说任何一个子区间都是查询，不满足 N=M 的条件。在剩余系里做乘加运算好像也没什么可以投机取巧之处，只能一个一个硬算……总之这个思路也彻底失败了。
26. 算法优化3：跳过序列

随后我又开始想能不能从生成的数字串中挖掘一些规律出来。比如哪些数字、哪些长度的出现频率高，就可以优先算哪部分。于是我对匹配数字的日志做了一番统计，结果很遗憾地发现，各种特性都是均匀分布的：M1-M4 每种数字串出现的频率相同，各种长度的数字串出现的频率也相同。

不过最终通过观察日志，我还是意识到了两个有价值的性质：

任意一个能被整除的数字串后面跟上若干个 0 也可以被整除。
任意两个能被整除的数字串不会重叠。

第一个十分显然。第二个也很好理解，如果这些数字串都是分别独立构造生成的，然后再混入随机串里，那就几乎不可能出现重叠的情况。
利用这两个性质，我们可以对程序做出如下优化：

找到一个能被整除的数字串后，马上向后查看是不是跟着 0，如果有就一起提交答案。
做完第一步后，清空 M1-M4 的所有状态。扔掉前面的串从头来过。

这个优化对于以 0 结尾的答案和在一个输入块中的第二个答案，理论上都有比较好的效果。但是由于满足这两个条件的答案并不是很多，所以不会有显著的提升。
27. TCP 使用单连接

这里又一次吃了没学好网络原理的亏：HTTP 从 1.1 开始引入了长连接，所以一个 TCP 连接可以用来发多个请求，并不需要每次都新建连接。在上一步优化中，如果有答案数字串后面跟着 0 的情况，那么可以将多个请求打包在一个 TCP write 操作中一起提交。这个优化可以为后面的答案节省 20us 以上的时间。考虑到当我们发现一个答案后，肯定希望用最快的速度调用 TCP write 将它发出去，而不是再去计算后面的内容，所以整个程序其实只需要一个 TCP 连接发答案就够了。
另外前面其实还做了两个关于 TCP 的设置：NO_DELAY 和 NON_BLOCKING。前者是对低延迟很关键的一个配置，用来禁用 Nagle 拥塞控制算法，让每次写入的数据都立刻发出；后者是为了防止发送陷入阻塞，耽误后面的计算。但我观察到在实际运行中并没有出现阻塞的情况，应该是因为每次发送的包都比较小，几乎不会占满内核缓冲区。
28. 算法优化4：单质因子

决赛即将过半，卷不过的群友们开始分析排行榜上对手的性能指标。一番估算以后惊恐地发现，人家已经把平均一个数字的计算时间压到了 50ns，按照正常的计算方法是很难做到的。于是，群友从中得出了一个非常关键的信息：

重点不是快速找到答案，而是快速排除非答案！哪怕排除算法不是 100% 准确，有一些漏网之鱼也是可以接受的！这让我立刻回忆起了曾经学过的费马小定理和快速判定质数等算法。不过对于这个题目来说根本不用这么复杂，有一个显而易见的判定方法：对于任何非质数的 M 来说，一个数能被 M 整除意味着一定能被 M 的任何一个因子整除。反过来，如果一个数对于 M 的某一个因子不能整除，那么它也不能被 M 整除。所以对于每个 M，我们都只需选一个因子来递推计算余数就好了。所有余数非 0 的直接排除掉，筛选出余数为 0 的再做一次验算即可。例如对于 M1 = 20220217214410 = 2 * 5 * 431 * 46589 * 100699，我们可以只算 1006990 的余数，找到余 0 的数字串后，再递推一遍算它对 431 * 46589 的余数。这样计算量就变成了原来的一半。对于 M3 和 M4，计算量可以降低到 1/3。并且由于它们的因数非常大，在随机数中出现假阳性的概率已经很低了，因此甚至可以不做验算直接提交答案。当然能这么做也是得益于莫队没有故意构造这样的数据来卡。
经过这个优化以后，计算量降低到了原来的 1/2-1/3 左右，大幅降低了计算时间。下图展示了我的程序从决赛开始到结束，测量的从收到数据到提交答案的时延分布变化情况。

决赛期间三个时间点的时延分布情况

从图中可以看出，10% 分位延迟基本维持在 50us 左右，中位数从 150us 降低到了 80us，90% 分位从 500us 降低到了 200 us，看起来相当不错了。
29. 思考内核旁路

然而，如果我们再看看榜上的统计数据……

……就会发现，本地延迟和服务端看到的延迟之间有 250-350us 左右的差值，这其中有 130us 的网络延迟，剩下 200us 左右就是操作系统和网络协议栈带来的开销了。对程序的 perf 结果也表明，内核的开销占到了整体的 7% 以上，其中大部分都和 TCP 相关。

终于，我们的瓶颈转移到了 OS 上面！
在决赛的最后一天，我开始思考如何 bypass 掉内核的网络协议栈。我能想到大致有四种方案，按照实现难度排序依次是：
1. 使用 Raw Socket 代替 TCP
这种方案只绕过了内核的 TCP 协议栈，由用户程序从二层或三层开始接管特定 IP 网络包的处理过程。这样不会对其它网络包造成影响，因此可以在云上直接开发调试。但是很有可能对性能不会有显著提高。
2. 使用 DPDK 等用户态协议栈
这个是业界标准的 kernel bypass 方案，将网卡驱动和协议栈都移到了用户态，从收包到发包的整个过程都可以留在用户态处理，彻底绕过了内核。但是由于目标机器在阿里云上，并且只有一个虚拟网卡，因此一旦部署 DPDK 接管网卡，随时都有 ssh 失联的危险。另外 DPDK 目前只有几个实验性质的 Rust binding，不知是否好用。虽说也可以将我的程序导出成 C 库用 C 代码粘起来，但是无论怎样都有不小的学习和试错成本。
3. 注入内核模块
这种方案和 kernel bypass 反其道而行之，将计算逻辑封装成内核模块注入内核，并挂载到网络协议栈的特定位置执行。它和 DPDK 方案一样都能避免上下文切换和进程调度的开销，也同时具有把内核搞崩溃导致失联的风险。与 DPDK 不同的是，写内核模块需要熟悉 Linux 内核环境和相关 API。
和内核模块类似的方案是 eBPF，这是一种在能在内核虚拟机中运行的程序，主要用来过滤网络报文。但是由于它在虚拟机中解释执行或 JIT 执行，性能肯定会受影响，而且八成无法利用 SIMD 指令做加速。因此从性能角度考虑这个方案并不适合。
4. 扔掉 Linux 自己写内核
这就是在上篇文章开头 @松提出的方案。由于 OS 跑在阿里云的 KVM 虚拟机上，所以至少需要实现 virtio-net 驱动和网络协议栈。这种方案可以对整个软硬件系统有最彻底的控制，避免 OS 中断开销，并且可以简化 TCP 复杂的状态机模型，以达到最极致的性能。但是即使有丰富的内核和网络开发经验，要实现这样一个工程并调试正确也至少需要几天的时间。
开了这么多脑洞，到最后其实哪个也没动手做，因为实在来不及了。在最后一天下午，我用 Rust 又写了一版高性能的服务端，并开了一个内网机器，全真模拟测量端到端的延迟。这么做其实是为了执行上面第一个 Raw Socket 方案做准备，但这也就是我最后的挣扎了。剩下的几个小时，我开始躺平等死。
30. 决赛结束

2 月 20 日下午 5 点 26 分，在距离比赛结束还有 3 个小时之际，本次比赛的最后一个逆转出现——松的 OS 上线了！！！

Welcome to JudgeDuck-OS-64 !!!

随即，松的得分曲线也开始起飞：

在这个时候，按照积累的总分排名，我排在第 5，@Liu Yiyuan 排第 6，@松排第 7。按照比赛规则，前六名可以获得奖金，所以这个位置的排名是非常关键的。而此时恰好我们三人的分数都很接近，并且差距还在不断缩小，所以在比赛的最后时刻开始了一场精彩的奖金争夺战。首先是松的分数开始快速增长，半个小时后超越 @Liu Yiyuan 来到第六，两个小时后又超过了我拿到第五。而 @Liu Yiyuan 和我之间的分差也在以每小时 2000 左右的速度逼近，经过估算大约 4 个小时后能够反超，然而此时比赛只剩下 3 个小时了。所以最后就差这么一点点，我保住了自己的第六名，拿走了最后的奖金 23333

比赛结束时的排行榜

晚上 8 点，比赛结束。与此同时，2022 北京冬奥会闭幕式开始。放下了这场连续 10 天不眠不休的内卷，我怀着 emo 的心情，去欣赏张 emo 的艺术盛会了。

解题报告

比赛结束后，选手们陆续在群里公布了自己的代码和解题报告。正如第一篇文章开篇所提到的，整个比赛从头到尾我都认为这是一场低延迟系统优化赛，所以想当然地以为别人都写了 SIMD 并且代码优化得比我好。因此当看到别人做法的时候我整个人都傻了：原来这真的是一个算法题啊！除了我和师兄 @Liu Yiyuan 在平方级算法上玩命卷 SIMD 以外，其他选手基本都想到了线性算法，并且做了预处理等优化，跟我们完全不在一个赛道上，是妥妥的降维打击啊。
下面的内容我综合了排名靠前的几位选手 xi, gamma, lambda, epsilon 和 chi 的解题报告，向大家展示一下这个比赛的“正确”做法是什么样的。
利用 M 的性质

首先不管使用了怎样的算法，各位选手基本都想到了利用 M 本身的性质来降低数据规模和计算量。其中最重要的是我在第 28 步优化中提到的，首先对 M 做质因数分解，然后使用一个小因子来快速排除不可能整除的数。利用这一性质可以使 M1-M4 的数据规模分别下降到 u32/u128/u64/u32，避免高精度运算。
以外，还可以利用的性质有：

对于 M1 = 20220217214410，直接排除结尾非 0 的数字串
对于比较长的 M3 / M4，可以排除长度小于 54 / 71 的数字串

平方递推

所有选手一开始都能想到这个平方级别的递推算法。准确地说它的复杂度是 $O(N \times L)$ ，N 是答案的最大长度，L 是输入串的总长度。我在第 4 步优化和本文开头提到过，这里再复述一下：
对于每个 M，维护以当前位置结尾的长度分别为 1-N 的数字串模 M 的余数，然后逐个追加数字递推后面的余数，公式为 $f_{i+1}=(f_i \times 10+x_i)\%M$ 。
线性递推

接下来是整个算法中的重头戏——使用数学变换将递推做到线性！也就是 O(L)。基本上前五名选手都想到了这个做法。
这个算法的核心思想是，将区间和转化为两个前缀和的差值。我们将从第 i+1 位到第 j 位数字组成的数字串记为 $S_{ij}$ ，其中从第 1 位开始的简记为 $S_j$ ，那么 $S_{ij} = S_j - S_i \times 10^{j-i}$ 。我们希望找到 $S_{ij} \equiv 0 \mod M$ 。
接下来我们要用到一点中学数学的知识了，它叫做 乘法逆元：在 M 和 10 互质的前提下，在 mod M 的剩余系中 ÷10 就等价于乘上 10 的逆元。这个逆元可以通过扩展欧几里德算法求出，下面记为 $r$ ，满足 $10 \times r \equiv 1$ 。于是在 mod M 剩余系中：

$0 \equiv S_{ij} \equiv S_j - S_i \times 10^{j-i} \equiv (S_j - S_i \times 10^{j-i}) \times r^j \equiv S_j \times r^j - S_i \times r^i$
所以我们只需要找到两个相同的 $T_i = S_i \times r^i$ 即可。而 $T_i$ 又可以通过以下方法递推求出：

$T_i = S_i \times r^i = (S_{i-1} \times 10 + x_i) \times r^i = S_{i-1} \times r^{i-1} + x_i \times r^i = T_{i-1} + x_i \times r^i\\ T_0 = 0$
每当递推出 $T_i$ 之后，我们还需要找到之前 N 个元素也就是 $T_{i-N}...T_{i-1}$ 中所有和它相等的数。这个操作可以用哈希表做到 O(1)，所以整体的复杂度是线性的。
预处理

在这个比赛中输入的数字串是一块一块发过来的，而在发送的间隙 CPU 是闲置状态，因此我们可以在这期间做一些预处理以加速下一次的计算。
在上面的线性递推中，由于 $x_i$ 只有 0-9 几种可能的取值，所以整个 $x_i \times r^i$ 都可以提前计算存下来。当下一块数据过来的时候只需要查表做加法即可。而对于平方递推的公式，由于每次都要 x10，似乎就没有很好的预处理方法。
预言

预处理更进一步就是预言：在输入发过来之前就提前猜测并提交答案。能这么做的基础假设是，答案都是人为生成的。所以如果发现结尾的串再加几个数字就能被整除，那它很有可能就是答案。
具体的计算过程是，假设当前有一个数字串 i-j，向后猜到第 k 位是答案： $0 \equiv S_{ik} \equiv S_{ij} \times 10^{k-j} + S_{jk}$ 。我们虽然不知道还没发过来的 $S_{jk}$ ，但是可以肯定它的长度一定是小于 k-j 的，也就是： $S_{jk} \equiv -S_{ij} \times 10^{k-j} < 1 0^{k-j}$ 。因此我们只需先枚举起点 i，再枚举结尾 k，找到所有满足上面条件的即可。为了保证正确率，向后猜测的位数应该小于 M 的长度。
这种预言所需的计算量比较大，是平方级别的，并且只能对 M 整体进行取模，所以需要高精度运算。不过好在这部分不在关键路径中，稍微慢一点也是可以接受的。在比赛过程中，群友 @大嗨子很早就点亮了预言的技能，在前期借此获得了大量 +8，决赛时又开了一个 ping 接近 1ms 的外网机器专门做预言。不过由于能够预言的数字串出现频率较低，加上后来好多选手都学会了预言，所以到后期这个策略的收益就不高了。
<hr/>以上我们揭晓了这个题目在算法上的正确做法和一些优化技巧。如果全部实现应该就可以拿第一了。不过虽然比赛已经结束了，但是我们对于极致的追求是永无止境的！下面我们就来继续探讨，在算法已经做到最优的基础上，系统方面还有哪些可以挖掘的地方吧。（别忘了还有一位选手写了 OS 呢）
SIMD

首先是我和 @Liu Yiyuan 主攻的 SIMD。在平方递推中，由于有数组运算，SIMD 能发挥很大的威力。但是在线性递推中，SIMD 似乎就没什么用了。考虑到经过预处理之后，我们只需要查表计算前缀和，而前缀和的计算是一个严格顺序的过程，很难并行化。尽管我找到一些关于 SIMD 加速前缀和的研究，但是也需要多线程的辅助才有比较显著的加速效果。所以结论是在正确算法下 SIMD 没什么用，呜呜呜。
OS

当计算时延进入 10us 量级以后，OS 内核就成为了整个系统的瓶颈。为了让大家了解内核中都有哪些开销，我们写一个最简单的 echo 程序（不停地从 TCP Socket 中收发包），然后对它 perf 一下：

可以看出，这个程序有接近 90% 的时间都在内核态执行，其中 20% 的时间在查文件描述符表，10% 的时间在做系统调用的上下文切换，还有 30% 的时间在处理 TCP。如果只看有效工作的话，其中至少一半开销都是可以避免的。
在第 29 步优化中我简单介绍了绕过内核的四种方案：Raw Socket，DPDK，内核模块，自己写 OS。猛男松爷选择了最硬核的手撸 OS 并成功上线，让我们直接看 @松自己写的解题报告吧：

…… （前三条是算法就不再贴了）
4. 此时操作系统已成瓶颈（计算 30us，内核协议栈 ??us……），因此考虑任何一种 kernel bypass 的方案（DPDK？eBPF？Linux 内核模块？自己写个 OS？）
5. 曾经写过一个带 UDP/IP 协议栈的纯内核态 OS，还缺个 TCP 和云服务器的网卡驱动（virtio-net），搞了两个通宵之后放弃了 TCP，写好了网卡驱动然后接了 lwIP 库上去，好用
6. 想办法如何在云服务器这种困难环境下部署：用 grub 启动，且设置 GRUB_DEFAULT=saved 及使用 grub-reboot 命令来保证从自己的 OS 重启后能回到 Linux，以防止丢失控制权
7. 应该还可以优化，lwIP 很慢（应自行实现 TCP 协议栈）、上述离线算法也很慢（启动一次附带 O(N) 时间）

我来具体解读一下：松之前自己写过一个操作系统内核 “评测鸭”，为了上云也曾尝试写过 virtio-net 网卡驱动，但是当时没有成功。这次比赛松又拿出了自己的鸭子，修好了网卡驱动，接上了嵌入式网络协议栈 IwIP，然后把计算逻辑塞了进去。为了在没有控制台的云服务器上部署调试，松首先在网络上做了特殊配置，当收到某种特定的网络包时就立刻重启（称为 GG reboot）。然后松把编译好的内核放在 grub 中，使用 grub-reboot 进入自己的内核，通过 VNC 远程连接获取屏幕输出，之后想离开时就发送特殊的网络包触发 GG reboot，接着就回到了 Linux！这一系列操作让我直接跪倒在地 _(:з」∠)_

评测鸭内核标志性技术：GG, reboot

通过 VNC 获取远端的屏幕输出

松的定制版评测鸭内核上线后，拿到了全场最低的 10% 延迟 188us，比第二名快了 16us。然而松表示，现在用的 lwIP 还是太菜了，如果换成自己写的网络协议栈还可以再快 20us！

lwIP 太菜了

内核态选手，respect！
FPGA

那么，自己手写内核就是这个比赛的终点了吗？并不是！因为在理论上还存在着一种终极解决方案：FPGA——把所有逻辑全部固化到硬件上，直接 bypass 掉整个冯诺依曼机！
在 FPGA 方案中，输入的网络包到达网卡，通过总线协议直接进入 FPGA 上的硬件协议栈，抽取出数字串后，再进入运算电路，可以一个时钟周期做一次递推计算。在这里算法复杂度已经不重要了，因为即使是平方级别的算法，也可以通过大规模并行电路变成线性的。对于线性递推中找相同数的操作，可以开 N 个寄存器连接 N 个比较电路，在一个时钟周期内获得结果。最后再通过硬件协议栈把答案发送出去即可。
如果我们假设 FPGA 的时钟频率是 100MHz 的话，一个长度为 100 的输入串只需 1us 的计算时间。但是考虑到 CPU 具有主频优势，如果使用线性算法的话谁快谁慢还真不好说。不过再考虑到 FPGA 中硬件协议栈和网卡之间可以近乎无缝衔接，从收到数据到发出答案的时延应该可以做到 10us 以下。整体来看 FPGA 还是要比传统计算机快很多的。

虽说本次比赛的环境并不允许 FPGA 部署，但是如果未来真的开放线下接入的话，那么 FPGA 将成为整场比赛的终极大杀器。不过，FPGA 的实现难度也是很大的，主要是硬件调试起来非常困难，而且每次调试的反馈周期很长，光编译就要等十几分钟。但是，既然同学们可以三星期造台计算机，一学期造出路由器，想必距离造出“莫队交易机”也是指日可待了！
总结与反思

以上是我对整场比赛技术上的分析，最后和大家聊聊这一周经历带给我的收获和思考。
技术上的收获

首先是技术上的收获。通过这次比赛的实践，我改变了一些固有观念，同时也获得了一些教训。这些内容在前面的流水账中也都有提到，这里再集中总结一下：
1. 异步编程模式不适用于低延迟系统
异步模式本是为高并发而生，虽然能提升整体性能，但却是以牺牲每条链路的延迟为代价的。因此在这种对实时性要求很高的场景下，异步模式并不适用，传统的同步阻塞 IO 反而是更好的选择。
2. Rust SIMD 非常好用
本次比赛是我第一次对 Rust SIMD 库进行深入体验，感觉确实相比传统 intrinsic 在开发效率上有巨大提高，而且生成的指令质量也可以接受。相信等它稳定之后，会大幅降低开发者使用 SIMD 的门槛，使得 SIMD 的全面普及成为可能。
3. 性能关键部分慎用第三方库
Rust 一个很香的地方就是可以方便地引用第三方库，让我们得以快速实现功能。但这也容易让人产生依赖，不加思考和审查就随手调库。事实上这些库的质量可能并没有我们想象的高，尤其是性能方面。对于程序中性能关键的部分，最终很可能需要手动对这些第三方库做优化，甚至自己重新造一遍轮子。就像我在比赛前期引入了很多看上去很 fancy 的库，到最后还是全都扬掉了。所以对于性能来说，大道至简永远是真理，没有代码胜过一切代码。
4. 多打日志以洞察程序的行为特征
详细的日志可以帮你尽早发现程序中的异常，将 Bug 扼杀在萌芽时期。此外多输出一些统计数据也可以帮你更精准地把握程序的性能特征，甚至从数据中发现更多的 insight。
做系统做傻了怎么办

其实上面这些收获都是小菜，打完这场比赛真正让我大受震撼，直击心灵的问题是：为什么我没想到这是算法题？！
更加震撼的是，不光我一个人没想到，和我一起参加比赛的两位群友——曾经的 OI 金牌选手统统都没想到：

为什么会这样呢？只能有一个解释，那就是最近几年我们一直都在做系统，给人做傻了。

三位精通网络、操作系统、体系结构和高性能计算的专家在得知真相后逐渐自闭

当然，「做傻了」只是一种调侃的说法，这背后的原因其实相当值得回味和讨论。在我看来，这件事至少能反映出几个问题：
1. 思维定势
很明显，我们都陷入了自己的思维定势之中。由于长期做系统相关方向，我们拿到一个问题自然会想用系统的方法解决。而恰好这个比赛的背景又是量化投资公司组织的一场“交易赛”，很容易让人联想到低延迟高频交易系统，而这又是我们比较擅长的方向。所以当球向着系统的方向踢出去之后，很容易就一条路走到黑，再也停不下来了。
2. 信息茧房
在参加比赛的选手中，我和两位群友平时很熟，会经常在群里讨论比赛话题。而剩下还有一半的选手据说都来自公司内部，想必他们之间也会有一个群来讨论这些话题。然而我们两拨人之间却互相不认识，不知道对方是怎么做的。这样就形成了各自独立的讨论圈，或者叫信息茧房，因为你获得的信息是不断被周围环境所强化的：既然我周围的人都在讨论系统，那我就更加相信这是系统题，并且以为系统就是整个世界，完全没有意识到还有另一个世界的存在。
3. 知其可为
所以事情的关键不在于知道它怎么做，而是知道这件事可以做。如果莫队一开始就告诉我们这是算法题，或者有人告诉我们存在线性时间的算法，那么凭借我们的知识储备总是能把它想出来的。

而事实上在比赛过程中，大部分时候我们也是看到了排行榜上别人能做到多快，才开始逼自己去想怎么才能做到这么快。最初大家都在毫秒级别互啄的时候，我是万万想不到存在微秒级别的解法的。或许有一天会出现一位大佬能把时延做到 1us 以下，我想到那时仅仅是知道这条消息就足以让人万分激动了。
4. 用进废退
当然，上面扯了这么多，说到底还是要承认一个基本规律：人的技能是用进废退的。长期不碰算法，不写代码也不刷题，对算法的敏感度就是会衰退。其实我在比赛中也多次尝试思考算法，但是就碰到这么一个简单的区间求和问题，愣是想不到前缀和。只能说是脑子笨了，长期思考工程和哲学问题，导致数理逻辑能力下降了。
意识到这些问题，接下来是该亡羊补牢了。这件事对我有什么启示呢？其实道理大家都懂，但很多时候只有自己掉进坑里了才能意识到它们真的有用：
1. 对于系统开发者来讲，要保持对算法和其它计算机领域的敏感度。
算法的重要性就不多说了。尽管我一直很鄙视的认为做系统不需要会算法，但不可否认目前算法能力依然是整个计算机行业里唯一的硬通货：凭竞赛上大学要考算法，上研究生要考算法，公司面试也还是考算法。
保持对其他领域的敏感同样很重要，虽说计算机系统是一切上层应用的基础，但是系统不是万能的、也没什么可高贵的。很多时候对上层应用做一点小小的改进就能起到四两拨千斤的效果。
2. 保持开放的心态，多多接触其它圈子和不同领域的人。
过去一年的时间里我借着秋招的机会接触了很多公司和各种领域的人，给我的感觉就像打开了新世界的大门。让我意识到除了自己所在的象牙塔小圈子以外，外面其实还有很多广阔的世界：有做 DB 的，做 AI 的，做交易的；在技术之外，还有重业务的，做产品的，推商业的，搞投资的；在人生道路的选择上，有读博当老师的，有去公司挣钱的，有创业当老板的，还有在家躺着享受生活的……到处都有成功人士，人生并不是只有卷 GPA 写代码发论文这一条路，而且现实中很多事情比在学校里做一个玩具项目、水几篇论文要困难得多——这也是我很想对还在学校里的贵系同学们分享的话。所以我认为，要想避免自己被困在思维定势和信息茧房当中，就要不断扩展视野、接触更广阔的世界。只有知道了更多事情可以做，才能更从容地去选择做什么，去思考怎么做。
系统思维与算法思维

上面有点扯远了，我们继续说回系统和算法。在这个比赛中，为了做到极致的低时延，系统和算法二者都是缺一不可的。但是它们之间的思维方式其实有很大的差别，甚至可以说是正交的。

系统的思维是：假设计算量不变，挖掘硬件性能，增加算力，减少不必要的开销
算法的思维是：假设硬件性能不变，挖掘计算特征，减少计算量

回顾我的整个比赛过程，我觉得非常明显地受到了系统思维的影响：

首先开局无脑把一个能工作的原型实现出来，而不是去想这个问题的正确解法
接着为了提高性能直接上多线程增加算力，而不是想算法能怎么降低计算量
后面的优化完全通过性能测试指导前进的方向
- 在宏观上：通过端到端的 perf 找出整个系统目前最大的瓶颈
- 在微观上：通过 microbenchmark 判断一个改进是不是有效
- 甚至于说算法上的改进，比如最简单的递推，我都是通过 benchmark 找到大整数解析的瓶颈，然后才想到的。
当简单的线程级并行挤不出牙膏之后，我又开始去搞更困难的指令级并行，也就是 SIMD
随后陷入到 SIMD 的自我娱乐当中——现代 CPU 真神奇，大整数计算真好玩
当 CPU 的性能被榨干之后，开始思考整个系统的瓶颈，然后打开 OS 工具箱，从里面翻出锤子扳手之类的东西，反复掂量做 tradeoff
然后发现所有方案的工作量都太大了，全部放弃
最后实在卷不过别人，达成精神胜利法：给我足够多的时间，一定能做出一个很 nb 的系统出来，大不了上 FPGA 嘛，谁能卷得过我

而一个正常的算法选手会怎么做这个题呢？我大概设想了一下 2014 年的我会怎么想：

首先读题，发现是个数论题。观察数据范围，发现 M 的范围有 64/128/256，可能需要使用高精度
思考暴力算法：发现可以用平方级别的复杂度递推
思考有没有线性算法
- 结局 A：对递推公式一通变换之后，发现问题转换为在一定范围内找两个相同数字，加一个哈希表解决
- 结局 B：没推出来，继续思考可不可以分块或者分治
思考常数优化：发现可以将 M 分解成多个因数分别计算
思考骗分策略：发现其实只算一个因数就可以了，正确率也挺高
思考在输入空闲期间能做什么：发现可以打表预处理后面的计算，还可以预测后面的输入……

很明显，算法思维是针对具体问题的，而系统思维更像是一种工程经验。科学的做法应该是先想算法，然后再优化系统。换言之，先思考再动手，想得越多写的越少。我觉得我做系统时间长了，就不自觉地陷入了工程师的思维陷阱，过于注重实践，认为 talk is cheap，code 才是真理。很多时候遇到问题就不会去想根本性的解决方案，而是习惯性地去找 workaround。这是一个比较危险的信号，以后真的需要多动动脑子了。
计算机系统能力

还有一个我特别想在这里讨论的话题：什么是真正的计算机系统能力？
最近几年教育部陆续举办了多场“全国大学生计算机系统能力大赛”，分别面向 CPU、编译器和操作系统（其中 CPU 赛就是同学们比较耳熟的“龙芯杯”）。虽然我有些遗憾没有参加过这些比赛，但我认识很多同学他们都在这些比赛的历练中展示出了极为惊人的能力水平。在我看来，“莫队交易赛”在某种意义上来说也是一种“计算机系统能力大赛”，而在本次比赛中 @松的表现向我们诠释了“系统能力”的真正内涵，那就是：利用计算机系统的原理和手段 去解决实际问题的能力。
解决问题！而不是自己造轮子玩儿。这才是做系统的终极目的——这也是让我感触最深的一点。
莫队交易赛所体现出的实际问题就是，怎样以最快的速度做交易，从而在市场上赚钱。这是一个很现实的问题，也是一个很有诱惑力的问题，同时是一个很有挑战的问题。要解决这个问题，除了算法上的优化以外，还需要懂网络的原理、CPU 的原理、体系结构的原理、操作系统的原理，而这些都不是比赛规则会告诉你的。更重要的是，你需要在有限的时间里，依据这些原理，选择适当的工具，运用合理的手段，改造一个系统或者做一个新系统出来，使得你比别人快。只有做到这一点，我认为才算掌握了真正的计算机系统能力。

重温经典。试问一下如果是你你能完成吗？

所以我很敬佩松爷的一点是，他从一开始做系统的出发点就是为了解决问题。因为观察到信息竞赛中选手程序运行时间总是测不准的问题，松自己做了一个操作系统内核评测鸭，并且把它封装成了 OJ 供大家使用。在这个 OJ 上面你的程序运行时间可以稳定在微秒级别，再也不用担心评测机波动被卡常了。松在造鸭子的过程中，陆续掌握了手撸内核、手撸驱动、手撸协议栈的技能。因此他在本次比赛中故技重施，拿鸭子一通魔改，最终成功翻盘，完全是在情理之中的事情。
相比之下，我倒要问问自己：你有勇气拿出 rCore 来和松爷对卷吗？？我觉得我属实不行，系统能力有待提高。
比赛周的精神状态

最后讲讲我在比赛周的生活状态。尽管莫队在首页上友情提醒过：「不要因为比赛影响到正常的学习工作生活」，但是面对这么刺激的场面，谁能坚持得住啊！整整一周我的大脑里面就只有这一件事：MOST！白天卷，晚上卷，上午做梦还在卷。

做梦还在卷

那一周我停下了手头所有工作，甚至组会都不开了，带着老板一起讨论这个比赛策略（康总饶命）。经常整个人处于一种极度亢奋的状态，大脑完全停不下来，因此晚上也根本睡不着觉，常常是想到了什么就立刻爬起来“再卷卷”。最后一天吃午饭的时候我甚至收到了 Apple Watch 的预警：

现在我有点理解为什么有些同学不去做量化交易了，确实太刺激了，小心脏承受不住啊。这次比赛还仅仅是模拟了在线交易中手快者得、赢者通吃的环境，就已经让人魂牵梦绕了。如果再让选手能够影响“市场”，增加策略和对打的成分，更加接近真实的交易环境……想想就更可怕了。所以为了选手的身心健康，建议下次再办比赛可以和股市交易时间同步：上午 9 点开盘，下午 3 点收盘。帮助大家养成良好的作息习惯：）
致谢

以上就是我想说的全部内容了，感谢各位读者坚持看到这里！
过去几天我陆续收到了多位读者的催更请求，也感谢各位的期待。久等了！拖了两周才更完。主要是我无法做到下笔文思泉涌，以后还是要常写点儿东西才行。
最后，还要特别感谢组织本次比赛的 @莫涛和罡兴投资团队，以及和我一同参赛的 @Liu Yiyuan @松 @大嗨子 @小源同学。我个人对这种比赛形式是非常资瓷的，因为这是对主办方和参赛方都非常有利的一件事。对于公司来说，我理解办比赛的最大作用是宣传自己、招揽人才，让更多同学了解工业界在做的事情；对于参赛同学来说，这是一个学习各种奇怪知识的非常难得的机会！除此之外，还可以认识更多大佬，了解一个行业，顺便投个简历……两边都赢麻了。

正如松给出的参赛理由一样：机会难得！

希望日后还有机会参加这样有意思的比赛。我们下场比赛再见！

JoshWindsor · 发表于 2022-3-11 13:05

读完本文，感觉润基先生系统做的属实不行，建议去 @madsys 读个博升级一下思维

RhinoFreak · 发表于 2022-3-11 13:10

既然瓶颈是网络，那卷计算没有用啊（不管是用SIMD卷还是用算法卷），定制OS才是正道。这就是为什么量化交易公司要建自己的信号塔

stonstad · 发表于 2022-3-11 13:15

还会有下一次的

johnsoncodehk · 发表于 2022-3-11 13:17

补充：即使只考虑系统思维，也应注意顶层设计，而不是一味地增量优化。应该一开始就对系统有整体的认识，对各种方法进行合理评估（Linux 内核协议栈有多慢？SIMD 加速计算逻辑能快多少？），然后直接选择一种工作量可接受的最优方案；如果比赛开始后再逐个 perf，恐怕真的会来不及[思考]

RhinoFreak · 发表于 2022-3-11 13:21

factor 125000000000000140750000000000052207500000000006359661 - Wolfram|Alpha 为啥我可以。

量子计算9 · 发表于 2022-3-11 13:26

膝盖碎裂！

xiaozongpeng · 发表于 2022-3-11 13:28

这是因为数据规模比较小，平方算法和线性算法差距不大，所以瓶颈才体现在网络上吧，不知道数据规模是不是估计设置的，但是我猜莫队原意应该还是考验选手系统能力吧，只是没想到有选手系统能力过于nb，硬是靠平方算法卷出来了[捂脸]

KaaPexei · 发表于 2022-3-11 13:38

随着优化过程的推进，瓶颈是不断变化的。在 1s 的时候瓶颈是语言，10ms 的时候瓶颈是网络延迟，100us 的时候瓶颈是算法复杂度，10us 的时候瓶颈才到 OS。虽然决赛的网络延迟有 100us，但是这块每个人都是一样的，而且没法降低。真实世界的量化公司肯定会去卷网络链路的。

Ilingis · 发表于 2022-3-11 13:46

“异步编程模式不适用于低延迟系统“，收交易所的包也是RPC啊，Execution确实同步快。纯算法思路不可取，快速的套DPDK这种框架也不可取，还是得完整分析完问题了在想解决方案。重头写kernel是弱智行为。我认为的系统思维，只是get hand dirty，也没有比推bound和形式化的东西高尚。

		自动登录	找回密码
密码			立即注册

代码优化卷翻天：莫队交易赛复盘（下）

本帖子中包含更多资源