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

一位系统选手的算法赛之路 —— 从失败走向彻底失败

一周前，@莫涛组织了一场 “莫队交易赛”，我和十几位同学一起受邀参加。这是一场模拟高频交易的编程比赛，选手需要编写程序，在一个实时推送的数据流中找到符合规则的模式，然后不断优化，比谁的程序最快找到结果。这是一个完全内卷的游戏，因为每个数据点的总分是固定的，按照抢到的顺序分配，比较符合赢者通吃的原则，所以卷起来十分刺激。
在过去的一周里，我除了吃饭睡觉以外的大部分时间都在卷这个比赛。最终在 10 人决赛中以极其微弱的分差获得了能拿奖金的最后一位：第 6 名。比赛前天晚上 8 点结束，恰逢冬奥会闭幕。在闭幕式的过程中大家纷纷公布了自己的解法，看完以后我人都傻了：原来这是一个算法比赛，而我和几个高性能所的小伙伴都把它当成了高性能计算题来做，一个劲儿地卷性能，结果被人家几个算法优化轻松吊打。这场比赛带给我的收获和影响都非常大，我决定趁着这股热乎劲儿写一篇复盘总结，和大家分享一下一个系统开发者眼中的算法题是什么样的 。更为重要的是，反思一下自己为什么是这么想的。
本文的主要内容包括：

介绍比赛规则和题目
按时间顺序记录我对程序做的主要优化
介绍其他选手的解题思路，探讨系统优化的进一步方向
这场比赛带给我的收获与反思：系统思维和算法思维的区别

由于想写的东西太多，我打算把它拆成三篇边写边更：

上篇：主要包含比赛介绍和前半周我所做的优化
中篇：主要介绍后半周 SIMD 相关优化和决赛实况
下篇：主要介绍其他选手的精彩解法和自己的一些感悟

欢迎大家围观~
题目和比赛规则

官方链接：http://47.95.111.217:10000/most.txt

本次比赛的题目非常简单：给定一个无限长的数字流，从中找出长度不超过 N 的连续数字串，满足其组成的正整数是任意 M 的倍数。
以下是一组样例：
# 样例输入
123456789987654321......
N=6
M1=823
M2=108
# 样例输出
12345  # 823 的倍数
3456 # 108 的倍数
9876 # 823 的倍数
432 # 108 的倍数选手需要通过 HTTP 协议访问指定 IP 地址获取输入、提交输出。输入输出服务器分别位于两个端口。向输入服务器发送 GET 请求，服务器会返回一个流，表示输入的数字流。提交答案需要向输出服务器发送 POST 请求，内容是找到的数字串，服务器会返回是否提交成功。官方提供了一个 Python 写的样例程序，演示如何参与这个比赛：
import requests

N = 256
M = 20220217214410
user = &#34;user&#34;
passwd = &#34;passwd&#34;

s = b&#34;&#34;
with requests.Session().get(&#34;http://172.1.1.119:10001&#34;, stream=True, headers=None) as fin:
   for c in fin.iter_content():
      s += c
      if len(s) > N:
         s = s[-N:]
      for i in range(len(s)):
         if s != ord(&#34;0&#34;) and int(s[i:]) % M == 0:
               requests.post(f&#34;http://172.1.1.119:10002/submit?user={user}&passwd={passwd}&#34;, data=s[i:])
               print(&#34;submit&#34;, s[i:].decode(&#34;ascii&#34;))
看上去非常简单，是不是有点跃跃欲试了？！当我们运行程序提交答案后，可以在一个页面上看到自己和其它选手的提交情况：

最上面是输入的常数 N 和 M，这个我们后面再具体讨论。接下来是排行榜，展示了每位选手的分数和性能指标。前面几列 +8/+4/+2/+1 表示每个人获得了多少次对应分数。具体的计分规则是，对于每个合法数字串出现前后 5 秒内的提交：（注意这个“前后”很有意思）

第 1 名：+8

第 2-3 名：+4

第 4-6 名：+2

第 7-10 名：+1

之后的不得分

继续往后看，>5s/wrong/dup 都是异常提交情况，同样不得分。submit 是总提交次数，比赛中每次提交都有固定 -1 分的成本。所以如果卷不到前 10 位，还不如不提交，不然还扣分。接下来是所有提交延迟的统计指标，10%/50%/90%/99% 是分位数，mean/std 是平均值和标准差。在这个比赛中延迟分位数是最重要的性能指标，它决定了你的每次提交能卷过多少对手。可以看出最终的分数排名和 10%/50% 延迟分位数基本是正相关的。
最后一个关键指标是 ping，表示你的机器和服务器之间的网络延迟。服务器位于北京阿里云上。在资格赛中，选手自己找机器部署程序，通过公网访问服务器，ping 本身的延迟就高达 2-5 ms。此外，每位选手的机器算力不同，其实也不是公平竞争。所以资格赛出线的秘诀其实就是在阿里云上开奖开出一个低延迟的多核机器。到了决赛，官方为每位选手提供了统一的内网服务器（2vcpu 4GB 内存），ping 降低到 130±10us 的范围。所有人又回到了同一起跑线，此时比拼的就是程序本身的运行速度了。
在排行榜下面还公布了最近生成的答案和每位选手提交的时间点。这张图是决赛结束后的截下来的，可以看到竞争已经进入了 10us 级别，甚至有时 1us 的差别就能分出胜负，实在是太卷了！为了更直观地看出各位选手的内卷情况，官方还提供了最近一小时的分数增长曲线：

这张图是决赛刚刚开始半小时的赛况。由于每位选手的起跑时间不同，场上依然是一种你追我赶的局面。但是长期来看体现选手实力和排名的是曲线的增长速度，也就是相同时间内能够卷到多少分数。决赛开始几个小时后，场面就变得稳定下来：

这时候其实还是相对势均力敌的，曲线均匀分布意味着每个人都有一些机会抢到 +8 或 +4。到了决赛后期，真正的卷王会让你们知道什么叫赢者通吃、菜鸡互啄。
看到这里，各位同学是不是已经摩拳擦掌、准备好一起卷翻天了？接下来我就带大家看看过去一周我是怎么（被）卷的。
比赛过程复盘

这里我回看了一下自己的 git log，按时间顺序以流水账的形式整理了一下做的每一步优化，主要是为了给自己留个记录。各位同学可以只看标题，然后选感兴趣的内容阅读，点击标题可以传送到代码。
按照类别索引：

算法优化：4 基本递推，7 猜 M4

计算优化：6 优化取模，8 定长整数，9 手动二分取模

系统优化：2 多线程，3 编译参数，5 提前 TCP 连接，10 避免 malloc，11 避免 async，12 低延迟服务器

SIMD 优化：TODO

1. Rust 实现样例代码

我的程序是用 Rust 写的，一方面是因为我已经发誓下半辈子再也不写 C++，另一方面这也是我第一次写针对低时延的程序，想知道用 Rust 效果如何。所以第一步是把官方提供的 Python 样例代码改写成 Rust。
这里有两个需求需要用第三方库解决，一个是大整数运算，一个是 HTTP 客户端。在 Rust 中我分别使用了 num-bigint 和 reqwest 库。考虑到涉及到网络 IO，还同时引入了 futures 和 tokio 异步框架。
2. 多线程并行化

为了提高性能，第一步想到的最简单的方法是用多线程加速。注意到每添加一个数字后的计算任务是互相独立的，所以每次就创建一个协程出来。然后将底层的 tokio 改成多线程执行器，这样就能够自动利用上所有 CPU 核的算力了。我的 MacBook 有 6 核 12 线程，因此运行时间即可降低到 1/6 以下。此时每找到一个数，从收到消息到发出答案的延迟一般在 100ms-1s 之间。
3. 利用本机指令

Rust 默认的编译配置出于兼容性考虑，不会利用上本机 CPU 支持的全部指令集，这其中就包括非常强大的 AVX2 等高级向量指令。于是我修改编译配置 -C target-cpu=native ，让程序利用上本机支持的 AVX2 指令集。
为了测试效果，我还用 criterion 框架编写了两个 micro benchmark。实验表明 num-bigint 的大整数一次字符串解析时间是 1.6us，一次取模的时间是 1.0us。修改编译配置前后几乎没有差别，说明向量指令没有派上用场。这也可以理解，因为目前没有什么规整的数组运算，编译器的自动向量化不起作用。不过我还是用 objdump 看了一下生成的汇编，并搜索 &#34;ymm&#34;，结果还真发现了不少。然而仔细一看都是用来加速数据移动的，llvm 你可真是个小机灵鬼！
100006e26: 0f 84 72 02 00 00          je    0x10000709e <__ZN88_$LT$hyper..client..dispatch..Envelope$LT$T$C$U$GT$$u20$as$u20$
core..ops..drop..Drop$GT$4drop17h1f08c1f01b0c4845E+0x2ae>
100006e2c: c5 fc 10 87 c0 00 00 00    vmovups 192(%rdi), %ymm0
100006e34: c5 fc 11 85 60 fe ff ff    vmovups %ymm0, -416(%rbp)
100006e3c: c5 fc 10 87 a0 00 00 00    vmovups 160(%rdi), %ymm0
100006e44: c5 fc 11 85 40 fe ff ff    vmovups %ymm0, -448(%rbp)
100006e4c: c5 fc 10 87 80 00 00 00    vmovups 128(%rdi), %ymm0
100006e54: c5 fc 11 85 20 fe ff ff    vmovups %ymm0, -480(%rbp)4. 算法优化1：基本递推

通过上面的 bench 可以发现，目前从字符串解析大整数是个瓶颈。有什么办法消除它呢？很明显可以想到，随着数字一个个加入，%M 的余数是可以递推计算的：。由于已知答案长度不超过 N，我们只需要维护当前字符前长度分别为 1-N 的数字串的余数即可。问题转化为对长度为 N 的数组中每个元素反复做上述递推运算，然后找 0。
进一步还可以发现，由于每次取模的数都小于 10M，因此取模可以优化成最多 9 次减法。（事实上可以进一步降到 4 次，当时没有想到，见第 6 步优化）
重写完以后，单线程的平均延迟降低到了 90ms 左右。然后再次做多线程并行化，第一步是对每一个 M 并行，第二步是对每个 N 并行，将任务拆得足够细使得每个核的计算量尽量均衡。这样平均延迟降低到 20ms 左右。
看到这里各位 OI 选手可能已经开始豹笑了：折腾半天原来就写了个暴力啊。
5. 提前建立 TCP 连接

这时我发现，发送答案的时间已经成为了瓶颈，有将近 10ms。仔细一想，我是在要发送的时候才开始建立连接。HTTP 基于 TCP，TCP 建立连接需要三次握手，消耗 1.5 RTT 的时间，而我的 ping 就有 4.8ms，这开销可就大了。显然，我们可以预先建立好 TCP 连接，等算出答案后立刻发送，避免三次握手的延时。
但在实现的时候，我又被自己给坑了。因为一开始使用了 reqwest 库，而这个库是个 high-level 的封装，我没法控制让它建立连接和发送数据分开啊。于是我找到了它依赖的另一个更 low-level 的 HTTP 库：hyper。研究半天接口以后，实现了这样的逻辑：开一个协程循环做 TCP 握手——接收答案——发送，用一个 channel 连接计算协程和网络协程。看到自己写出了这种非常 async 的代码，我露出了满意的笑容。然后笑容逐渐僵硬——因为我发现答案发不出去了！
一开始我怀疑是网络问题，但随后我试着用 curl 发——正常，退回到上一个版本——也正常。这说明锅在新的库 hyper 头上！然而原来的 reqwest 底下也是 hyper 怎么就没事呢？一定是我用法不对！
为了搞清楚到底发生了什么，我打开了 Wireshark 抓了个包：

原来是发出的 POST 请求服务端不给回复了！那应该是 HTTP 头有问题，于是我又仔细看了看 HTTP 包的内容，发现 hyper low-level 接口发的包没有填 Host 等字段，手动填上以后的包是这样的：

结果依然没有回复！对比 curl 的包看一下，我发现有两处区别：一个是没有 User-Agent ，另外就是 key 首字母没有大写。于是我立刻上网集成学习了一下 HTTP 协议，得知 HTTP 头是大小写不敏感的。但是我不信邪，非得把它整成大写不可！接下来我对着 hyper 的源码折腾了几个小时，就是没办法发出正确的包。绝望之时，我开始想能不能绕过 hyper 自己发包，于是再次上网集成学习 HTTP……
突然之间，我悟了：md HTTP 就是个基于 TCP 的简单文本协议啊，你直接把 curl 发的包粘贴过来发 TCP 不就完了，用什么库？？？这一刻，我沉默了。我就知道自己当年没有好好学网络原理，早晚会为此付出代价。我怀着沉重的心情删掉 hyper，换上自己构造的 HTTP 头：
const HEADER: &str = &#34;POST /submit?user=omicron&passwd=y8J6IGKr HTTP/1.1\r\nHost: 47.95.111.217:10002\r\nUser-Agent: Go-http-client/1.1\r\nContent-Type: application/x-www-form-urlencoded\r\n&#34;;
let content_length = format!(&#34;Content-Length: {}\r\n\r\n&#34;, body.len());
let iov = [
   IoSlice::new(HEADER.as_bytes()),
   IoSlice::new(content_length.as_bytes()),
   IoSlice::new(&body),
];
stream.write_vectored(&iov).await.unwrap();
还不忘秀一把零拷贝的 IO Vector 接口。终于，提交成功了，延迟降到 10ms。
6. 计算优化：递推乘加取模

在第 4 步中提到，取模可以优化成 4 次减法，分别是 8M、4M、2M、M（或者两次 4M 也行）。注意到 M 是给定的常数，因此可以预先计算好这几个值。
更进一步，我们可以预先计算 [M, 2M, 3M, ..., 9M]，然后在这个数组中二分查找，最多比较 4 次即可算出商，随后只需要 1 次减法即可算出余数。（在第 9 步中我们会利用 M 是常数的性质进一步优化这个计算）
7. 猜 M4

接下来，我把目光投向了隐藏数字 M4 上。这怎么猜呢？还记得排行榜下面的提交信息吗：

我们发现如果答案比较长，那么中间就会以 ..... 省略，如果比较短就可以显示全，这其中肯定有些是 M4 的倍数！所以，我们可以写一个脚本定期爬 board，通过正则表达式 \n[0-9]+\n 提取出所有完整的答案，然后依次模 M1/2/3。如果都不能整除，那说明它肯定能被 M4 整除。然后分别提取它（3,7,11）因子的个数，对所有数取最小值即可（最大公约数）。
悲催的是，我的 Python 脚本写错了。整数除法 x // 3，我写成了 x / 3，然后变成了浮点，后面结果全错了。动态类型一时爽，算错了你都不知道。更恐怖的是，后面很长时间我都没有发现这个错误，白白浪费了很多算力。因为在输入流中根本找不到能被错误 M4 整除的数，所以榜上看不出有错误提交。并且我还没在 log 中输出每一个数的类型，看不出异常。这个教训说明：一定要尽量详细地打 LOG！
8. 变长大整数转定长

找到 M4 以后，仔细观察这四个数的长度：
M1 = 20220217214410
M2 = 104648257118348370704723119
M3 = 125000000000000140750000000000052207500000000006359661
M4 = 10885732038215355481752285039386319187390558900925053798518152998488201发现都不怎么长啊：M1 可以用 u64 放下，M2 可以用 u128 放下，M3、M4 可以用 u256 放下。
可能因为从样例程序一路改过来的缘故，在改成递推算法时竟然没有意识到其实并不需要高精度运算，用定长类型就够了。u64 和 u128 都是 Rust 内置的基本类型，其中 u128 会由编译器拆开放在两个 64 位寄存器中，由 compiler_builtin 库软件实现所有运算。但是 u256 就不支持了，于是我又上 docs.rs 搜索到一个定长整数运算库 primitive-types，分分钟换掉 num-bigint。
9. 计算优化2：手动展开二分比较取模

做完上一步之后我 perf 了一下程序：

发现开销最大的是一个叫 __umodti3 的函数，这个就是上面提到的编译器内置函数，用来计算 u128 % u128。可见取模运算是非常慢的！
在第 6 步优化中我们提到可以利用二分查找将取模优化成 4 次比较和 1 次减法。但是在数组中二分查找每一步都需要访问内存。虽然这个数据量很小，肯定能在 L1 Cache 中命中，但毕竟 CPU 执行访存指令还是比计算要慢不少的。回头看我们的数组 [M, 2M, ..., 9M]，一共没几个数，所以干脆把整个二分比较的过程硬编码到代码中：

由于函数标记了内联，编译器知道传入的 M 是个常数，因此会自动做常数传播优化，最终生成如下指令：

可以看到编译器把每个常数都计算出来，然后塞到了 mov 指令里面！这样就避免了访问内存。更加亦可赛艇的是，由于 u128 需要拆成高低两个 u64 进行比较，只有在高位相等的情况下才需要比较低位，而高位相等是极其罕见的，因此低位比较几乎不会被执行（除了二分的最后一轮）。所以整个取模操作平均只需要 4 次 u64 比较 + 1 次 u128 减法即可完成，是非常高效的。同样的方式也可以应用到 u256 上面，平均是 7 次 u64 比较 + 1 次 u256 减法。
但是，这种将逻辑硬编码到大量分支中做法的也有它的问题，那就是难以扩展到 SIMD 并行化。在第 14 步优化中我们会讨论如何在 SIMD 中实现取模。
另外我还发现了一个很有趣的现象：对于 u64 % 常数 u64，编译器会将其优化成两次乘法：

我人肉反汇编了一下，算法大概是，其中 C1、C2 是两个魔法常数。感兴趣的同学可以打开 Python 验算一下：
>>> m = 20220209192254
>>> c1 = 0x6f5d238e7a7e04bf
>>> c2 = 0x1263e262dd3e
>>> x = m * 5 + 23333
>>> x % m
23333
>>> x - ((x * c1) >> 107) * c2
23333看上去是利用了一些神奇的数学原理，哪位大佬可以解释一下嘛。
10. 避免动态内存分配和数据拷贝

在 perf 中我还发现了 malloc 占了 1% 左右的开销，于是我看了一下代码中哪里用到了动态内存分配。原来是在计算过程中我用了一个 VecDeque 也就是循环队列来维护最近 N 个数字，当发现答案后，将其拷贝到一个 Vec 的连续空间中。这一步也是不必要的，因为在循环数组中任意一个子区间只会由至多两个离散的 slices 组成，标准库中也提供了 VecDeque::as_slices API 来获取它们。所以，我们可以用两个 slices 来表示答案，然后通过 IO Vector 直接从 TCP 发出去。
这个优化不会对性能带来很大提高，但还是随手做了，因为实在是分秒必争啊。
11. 避免 async，使用阻塞 IO

由于我之前做的大部分都是面向高并发的工作，因此习惯性起手就是一个 async。然而稍微想想就会发现，异步模式是不适用于低时延场景的，因为一条 IO 路径可能会被拆成多段由不同的人执行，它们在交接时调度器会引入额外的延迟。
以 tokio 的 TcpStream 为例，它的 read 操作是个异步函数。如果此时服务器还没有发数据过来，read 系统调用会返回 WouldBlock 错误，导致上层协程挂起，并向后台 reactor 注册一个回调函数等待唤醒。当输入数据到达内核后，内核首先唤醒 epoll 线程，然后根据事件查表触发回调函数唤醒协程，随后还要等待调度器重新调度协程，才能开始执行真正的计算逻辑。而最原始的阻塞 read，当数据到达内核后就会立刻唤醒线程开始计算，延迟最低。
想明白这一点后，我返璞归真，把 tokio::net::TcpStream 换回了 std::net::TcpStream。
12. 获得低延迟服务器

到目前为止，我的程序一直是在我的 MacBook 上跑的，距离阿里云上的服务器有 5ms 的 ping 延时，而榜上最低的 ping 只有 1.8ms。

一跳一跳又一跳

此时我的平均计算延迟已经进入了 3ms 级别，感觉卷不动了，于是将希望寄托在了降低 ping 上面。此前我曾经尝试过在服务器所在的阿里云北京 H 区开服，但是开出来 ping 竟然有 4.6ms，十分不理解。后来我发现是交换机选错了，选成了 A 区。改成 H 区以后第一次就开出了一个 1.8ms 的服！后来我又先后尝试以同样的配置开服，但开出来 ping 都在 2ms 以上，再也没能复现第一次 SSR 的欧气。我的小伙伴们说他们甚至搞过 100 连抽，无一命中，还给阿里云送了不少银子。

氪金玩家

将程序迁移到服务器上后，曲线一下就卷上去了，总分排到了第四位。可以看到，排名靠前的基本都是抽到好机器的欧皇，这充分说明一个好的出生点是多么重要。这次比赛后，我对北京市内的网络延迟有了更加刻骨铭心的认识。

资格赛前的排行榜

下篇预告
到这里比赛进程已经过半，接下来是两天的资格赛和两天更加激烈的决赛。在后半周的时间里，我主要利用 Rust 的 SIMD 模块来对计算做进一步加速，在服务器 CPU AVX512 的加持下成效显著。
下篇文章我们来讨论一下 Rust 独特的可移植 SIMD 模块，以及如何用 SIMD 处理大整数的乘加和取模运算。欢迎关注~