转自：https://zhuanlan.zhihu.com/p/478486523
https://tuna.moe/event/2022/high-frequency-trading/
一周前，莫涛组织了一场 “莫队交易赛”，我和十几位同学一起受邀参加。这是一场模拟高频交易的编程比赛，选手需要编写程序，在一个实时推送的数据流中找到符合规则的模式，然后不断优化，比谁的程序最快找到结果。这是一个完全内卷的游戏，因为每个数据点的总分是固定的，按照抢到的顺序分配，比较符合赢者通吃的原则，所以卷起来十分刺激。
在过去的一周里，我除了吃饭睡觉以外的大部分时间都在卷这个比赛。最终在 10 人决赛中以极其微弱的分差获得了能拿奖金的最后一位：第 6 名。比赛前天晚上 8 点结束，恰逢冬奥会闭幕。在闭幕式的过程中大家纷纷公布了自己的解法，看完以后我人都傻了：原来这是一个算法比赛，而我和几个高性能所的小伙伴都把它当成了高性能计算题来做，一个劲儿地卷性能，结果被人家几个算法优化轻松吊打。这场比赛带给我的收获和影响都非常大，我决定趁着这股热乎劲儿写一篇复盘总结，和大家分享一下一个系统开发者眼中的算法题是什么样的 。更为重要的是，反思一下自己为什么是这么想的。
本文的主要内容包括：
- 介绍比赛规则和题目
- 按时间顺序记录我对程序做的主要优化
- 介绍其他选手的解题思路，探讨系统优化的进一步方向
- 这场比赛带给我的收获与反思：系统思维和算法思维的区别
由于想写的东西太多，我打算把它拆成三篇边写边更：
- 上篇：主要包含比赛介绍和前半周我所做的优化
- 中篇：主要介绍后半周 SIMD 相关优化和决赛实况
- 下篇：主要介绍其他选手的精彩解法和自己的一些感悟
欢迎大家围观~
上篇：比赛介绍和前半周我所做的优化
文档， 备份
本次比赛的题目非常简单：给定一个无限长的数字流，从中找出长度不超过 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 = "user"
passwd = "passwd"
s = b""
with requests.Session().get("http://172.1.1.119:10001", 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[i] != ord("0") and int(s[i:]) % M == 0:
requests.post(f"http://172.1.1.119:10002/submit?user={user}&passwd={passwd}", data=s[i:])
print("submit", s[i:].decode("ascii"))
看上去非常简单，是不是有点跃跃欲试了？！当我们运行程序提交答案后，可以在一个页面上看到自己和其它选手的提交情况：
最上面是输入的常数 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
我的程序是用 Rust 写的，一方面是因为我已经发誓下半辈子再也不写 C++，另一方面这也是我第一次写针对低时延的程序，想知道用 Rust 效果如何。所以第一步是把官方提供的 Python 样例代码改写成 Rust。
这里有两个需求需要用第三方库解决，一个是大整数运算，一个是 HTTP 客户端。在 Rust 中我分别使用了 num-bigint 和 reqwest 库。考虑到涉及到网络 IO，还同时引入了 futures 和 tokio 异步框架。
为了提高性能，第一步想到的最简单的方法是用多线程加速。注意到每添加一个数字后的计算任务是互相独立的，所以每次就创建一个协程出来。然后将底层的 tokio 改成多线程执行器，这样就能够自动利用上所有 CPU 核的算力了。我的 MacBook 有 6 核 12 线程，因此运行时间即可降低到 1/6 以下。此时每找到一个数，从收到消息到发出答案的延迟一般在 100ms-1s 之间。
Rust 默认的编译配置出于兼容性考虑，不会利用上本机 CPU 支持的全部指令集，这其中就包括非常强大的 AVX2 等高级向量指令。于是我修改编译配置 -C target-cpu=native ，让程序利用上本机支持的 AVX2 指令集。
为了测试效果，我还用 criterion 框架编写了两个 micro benchmark。实验表明 num-bigint 的大整数一次字符串解析时间是 1.6us，一次取模的时间是 1.0us。修改编译配置前后几乎没有差别，说明向量指令没有派上用场。这也可以理解，因为目前没有什么规整的数组运算，编译器的自动向量化不起作用。不过我还是用 objdump 看了一下生成的汇编，并搜索 “ymm”，结果还真发现了不少。然而仔细一看都是用来加速数据移动的，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)
进一步还可以发现，由于每次取模的数都小于 10M，因此取模可以优化成最多 9 次减法。（事实上可以进一步降到 4 次，当时没有想到，见第 6 步优化）
重写完以后，单线程的平均延迟降低到了 90ms 左右。然后再次做多线程并行化，第一步是对每一个 M 并行，第二步是对每个 N 并行，将任务拆得足够细使得每个核的计算量尽量均衡。这样平均延迟降低到 20ms 左右。
看到这里各位 OI 选手可能已经开始豹笑了：折腾半天原来就写了个暴力啊。
这时我发现，发送答案的时间已经成为了瓶颈，有将近 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 = "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";
let content_length = format!("Content-Length: {}\r\n\r\n", 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。
在第 4 步中提到，
取模可以优化成 4 次减法，分别是 8M、4M、2M、M（或者两次 4M 也行）。注意到 M 是给定的常数，因此可以预先计算好这几个值。
更进一步，我们可以预先计算 [M, 2M, 3M, …, 9M]，然后在这个数组中二分查找，最多比较 4 次即可算出商，随后只需要 1 次减法即可算出余数。（在第 9 步中我们会利用 M 是常数的性质进一步优化这个计算）
接下来，我把目光投向了隐藏数字 M4 上。这怎么猜呢？还记得排行榜下面的提交信息吗：
我们发现如果答案比较长，那么中间就会以 ..... 省略，如果比较短就可以显示全，这其中肯定有些是 M4 的倍数！所以，我们可以写一个脚本定期爬 board，通过正则表达式 \n[0-9]+\n 提取出所有完整的答案，然后依次模 M1/2/3。如果都不能整除，那说明它肯定能被 M4 整除。然后分别提取它（3,7,11）因子的个数，对所有数取最小值即可（最大公约数）。
悲催的是，我的 Python 脚本写错了。整数除法 x // 3，我写成了 x / 3，然后变成了浮点，后面结果全错了。动态类型一时爽，算错了你都不知道。更恐怖的是，后面很长时间我都没有发现这个错误，白白浪费了很多算力。因为在输入流中根本找不到能被错误 M4 整除的数，所以榜上看不出有错误提交。并且我还没在 log 中输出每一个数的类型，看不出异常。这个教训说明：一定要尽量详细地打 LOG！
找到 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。
做完上一步之后我 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、K 是三个魔法常数。感兴趣的同学可以打开 Python 验算一下：
>>> m = 20220209192254
>>> c1 = 0x6f5d238e7a7e04bf
>>> c2 = 0x1263e262dd3e
>>> x = m * 5 + 23333
>>> x % m
23333
>>> x - ((x * c1) >> 107) * c2
23333
看上去是利用了一些神奇的数学原理，哪位大佬可以解释一下嘛。
UPDATE：评论区有同学给出了答案
SuperSodaSea：【编译笔记】变量除以常量的优化（一）——无符号除法
Barrett Reductionen.wikipedia.org/wiki/Barrett_reduction
在 perf 中我还发现了 malloc 占了 1% 左右的开销，于是我看了一下代码中哪里用到了动态内存分配。原来是在计算过程中我用了一个 VecDeque 也就是循环队列来维护最近 N 个数字，当发现答案后，将其拷贝到一个 Vec 的连续空间中。这一步也是不必要的，因为在循环数组中任意一个子区间只会由至多两个离散的 slices 组成，标准库中也提供了 VecDeque::as_slices API 来获取它们。所以，我们可以用两个 slices 来表示答案，然后通过 IO Vector 直接从 TCP 发出去。
这个优化不会对性能带来很大提高，但还是随手做了，因为实在是分秒必争啊。
由于我之前做的大部分都是面向高并发的工作，因此习惯性起手就是一个 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 处理大整数的乘加和取模运算。欢迎关注~
中篇：SIMD 相关优化和决赛实况
上周我参加了一场莫队举办的高频交易模拟赛。这篇文章作为比赛复盘系列的第二篇，主要介绍一下使用 Rust 编写 SIMD 加速计算的技巧和经验。
上回说到，在前半周的比赛中，我拿着暴力递推算法一通常数优化，凭借刷出低延迟服务器的加持，成功卷到第四位进入资格赛。随着比赛正式打响，战况也愈发激烈：前两名遥遥领先，后面的紧追不舍，场面看似波澜不惊、实则暗流涌动。每隔一段时间就出现一条曲线突然上扬，被卷过的选手纷纷躺平的场面上演。
抽到了低延迟服务器后，Omicron 毒株开始起飞（雾）
当然也会有黑天鹅现象出现，比如第一名突然卷飞了。。。
为了不被对手卷走，各位选手八仙过海各显神通。赛场上陆续出现了大预言家，还有潜伏的 OS 专家开始着手研发专用内核：
大预言家
现在开始写操作系统还来得及！
这个时候，我思考了一番接下来的玩法：既然已经抽到了 1.8ms 的服务器，资格赛保住前 10 名晋级应该比较稳了，那么可以直接为决赛作准备。而决赛和资格赛的环境是很不一样的，资格赛中排名靠前的选手很有可能是用了更多核的算力，但是决赛只有 2vcpu，所以多线程的作用不大，主要比的是单核的算力。而我之前已经把单核计算优化到了汇编级别，进一步提升的空间很小，因此是时候开始用 SIMD 挖掘更多的单核算力了！
这里简单做一下科普：SIMD 全称 Single Instruction Multiple Data，即单指令流多数据流。是 CPU 中用单条指令对一组数据执行相同运算的一种并行计算技术。SIMD 技术很早就被应用到主流处理器当中。x86 系列处理器从上个世纪开始就逐步引入了 MMX/SSE/AVX 系列扩展指令集，以及相应的 mm/xmm/ymm/zmm 向量寄存器。目前，最新的 AVX512 指令集已经完全部署到了近几年的 Intel 服务器 CPU 当中。它引入了 32 个 512 bits 的 zmm 寄存器，一条指令就可以同时对 8 个 64 位整数/浮点、或 16 个 32 位整数/浮点进行运算，大幅提升了并行计算效率。
x86 的三代向量寄存器，图源：https://cvw.cac.cornell.edu/vector/hw_registers
虽然 SIMD 的算力远不如同一时代的 GPU，但它在灵活性上远超 GPU：GPU 是独立的计算设备，通过 PCIe 总线与主板连接，需要厂家专用的驱动、指令集和开发工具才能使用。每次执行计算时，还需要 CPU 向 GPU 发送指令，将数据从内存搬到显存上，执行计算后再搬回来，整体延迟非常大。而 SIMD 是 CPU 的内置功能，直接编写向量指令就可以使用。现代编译器通常还可以做自动向量化，对数组循环计算等操作自动生成 SIMD 指令。此外，SIMD 还可以很好地和原有的计算逻辑相结合，数据移动的开销也很小。这些特性使得 SIMD 相比 GPU 具有更低的延迟，更容易上手开发，非常适合在这个比赛的场景下使用。
接下来我们继续复盘比赛过程，具体说明如何用 Rust 编写 SIMD 在支持 AVX512 的 CPU 上加速大整数运算。
比赛过程复盘（续）
分类索引：
- 计算优化：13 U256
- SIMD 优化：14 U128x8，15 U192x8，17 U64x8，19 进位处理
- 算法优化：18 质因数分解
- 系统优化：16 监控程序
在第 8 步优化中，我引入了第三方库 primitive-types 来做 256 位大整数运算。但随后的测试显示出它的性能并不好：
perf 显示有大量时间消耗在了 U256 相关计算上
首先，这几个函数没有被内联，这意味着每次都会有至少 4 个 u64 通过内存传递，而不是寄存器。其次，这个库的实现方法更加注重通用性，它可以同时生成 U128、U256、U512 等不同类型，但没有对性能做特别优化。我们进入 add 函数内部看看，发现简直一团糟：
明明可以做得更好！x86 指令集中有一条 ADC（Add with Carry）指令可以用来优化大整数加法。它相当于一个全加器，多条指令级联起来即可高效完成大数的加法运算。Rust 标准库中也有对它的封装函数 u64::carrying_add（不过还在 nightly 阶段）。有了这个函数，我们就可以写出既优雅又高效的代码：
pub struct U256(pub [u64; 4]);
impl Add for U256 {
type Output = U256;
#[inline]// 记得 inline
fn add(self, rhs: Self) -> Self::Output {
let [a0, a1, a2, a3] = self.0;
let [b0, b1, b2, b3] = rhs.0;
let (c0, carry) = a0.carrying_add(b0, false);
let (c1, carry) = a1.carrying_add(b1, carry);
let (c2, carry) = a2.carrying_add(b2, carry);
let (c3, _) = a3.carrying_add(b3, carry);
U256::new([c0, c1, c2, c3])
}
}
可以看到还是非常紧凑而高效的。
在具体实现上，由于我写的 U256 采用小端序存储，因此需要翻转顺序后再按字典序比较：
impl Ord for U256 {
#[inline]
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
let [a0, a1, a2, a3] = self.0;
let [b0, b1, b2, b3] = other.0;
[a3, a2, a1, a0].cmp(&[b3, b2, b1, b0])
}
}
而假如采用大端序存储就更简单了，可以直接写 #[derive(PartialOrd, Ord)] 生成默认的字典序比较。
impl Sub for U256 {
type Output = U256;
#[inline]
fn sub(self, rhs: Self) -> Self::Output {
let [a0, a1, a2, a3] = self.0;
let [b0, b1, b2, b3] = rhs.0;
let (c0, carry) = a0.carrying_add(!b0, true);
let (c1, carry) = a1.carrying_add(!b1, carry);
let (c2, carry) = a2.carrying_add(!b2, carry);
let (c3, _) = a3.carrying_add(!b3, carry);
U256::new([c0, c1, c2, c3])
}
}
接下来我们做一下性能测试。需要说明的是这个测试是我写这篇文章的时候补测的，当时就直接上线了。然而最终复盘的时候还是有必要知道一下每一步优化到底起到了多大效果。下图中左侧是前后两种实现每个基本运算的时间，右侧是算一轮 N=256 个元素 M3 的完整时间：
可以看出我自己的实现相比原来的第三方库，在各种基本运算上的性能都有相当程度的提高。其中加法优化到了原来的 2.5 倍，减法 1.3 倍，移位和比较运算则达到了离谱的 10 倍以上，最终计算 M3 的整体性能提高了整整一倍。可见原来的实现性能实在是不行啊。
在实现过一遍完整的 U256 之后，我发现自己写一个定长大整数还是挺简单的。下面就可以正式开始卷 SIMD 了！我们首先拿 128 位试试水。
需要回答的问题有两个：
- 如何用向量寄存器表示大整数？
- 在这种表示下，如何用 CPU 提供的指令实现大整数的加法、减法、移位、比较运算？
我的第一想法是，把一个大整数完整塞进一个寄存器里。比如我们有一个 128bits 的 xmm 寄存器，那就让它像普通的通用寄存器一样表示一个 u128。
但随后问题来了，CPU 中没有一个指令能够把 xmm 看作一个完整的 128 位整数做加法，而只能把它看作 2 个 u64 分别做加法。
既然如此，有没有可能使用 2 个 64 位加法分别计算高低位，然后自己处理进位呢？似乎是可行的，我们只需要把低位的进位结果平移到高位，然后再相加即可。其中平移这步需要用到一种 shuffle 指令，它能够将原向量的各个元素按指定顺序重组成一个新的向量。
并且这种方法不限于 xmm，还可以扩展到 2 个 128 位整数的 ymm 和 4 个 128 位整数的 zmm：
减法运算和加法同理。而对于左移运算，我们也需要用类似的做法，将低位的溢出部分移动并组合到高位去：
最有意思的是比较运算。对于 128 位整数来说，我们需要先比较高位，如果高位相等再比较低位。因此这里会有一个 select 或者叫 blend 操作：根据一个 mask 向量的值来决定从 A/B 两个向量中选取哪个。
以上我们就完成了用 SIMD 进行 128 位整数运算的一个完整设计！看上去还不错，但是总觉得有点麻烦。麻烦的原因在于 SIMD 的一组数据之间是完全无关的，然而大整数的高低位之间却存在着数据依赖性，比如加减要进位、移位要填充、比较也有先后。这就使得即使 SIMD 可以一次性做完对等位置的运算，也还需要将低位移动到高位再算一次。更加麻烦的是，如果数字的长度发生变化，比如变成 192 位不能整除了，甚至变成 1024 位直接越界了。这种情况下各种边界处理将成为一大噩梦。有没有更加简单且自然的方法呢？
我上网搜索了一下相关话题，找到了 StackOverflow 上的一篇回答，它给出了完全另一种角度的实现：用两个向量寄存器分别存储一组数的高低位！
当时我就惊呆了，原来这才是使用 SIMD 的正确姿势！在这种数据排布下，一组向量寄存器内的数据是完全无关的，这样向量和标量的计算过程就完全统一了，在代码中直接把原来的数据类型和运算改成向量版本即可。
这篇文章还同时指出了 SIMD 处理加法进位的问题：传统的标量指令会在发生进位时设置特定的标志位（CF），而向量指令则是直接丢弃溢出的部分，所以我们无法直接地知道是否发生了进位。那怎么办呢？文中给出的方法是再对运算结果做一次比较，如果和小于其中一个被加数，就说明发生了进位。利用这一特性，我们可以在 AVX512 中仅用 4 条指令实现 128 位整数加法：
vpaddq xmm2, xmm0, xmm2 # x_low += y_low;
vpcmpuq xmm0, xmm0, xmm2 # x_low < y_low
vpaddq xmm1, xmm1, xmm3 # x_high += y_high
vpsubq xmm0, xmm1, xmm0 # x_high += xmm0
不过在 AVX2 及以前的指令集中，并没有一条直接对无符号整数比大小的指令，只支持有符号整数比较，因此需要额外两条 vpxor 指令来对符号位做反转。后面我们会发现，由于这一点差异导致 AVX2 和 AVX512 的性能产生了天壤之别。
在学习完先进设计后，下面我们就来在 Rust 中实现这个做法！
自 SIMD 诞生以来，开发者想在自己写的程序中用上它基本上只有三种途径：要么让编译器自动向量化，要么使用编译器提供的 intrinsic 内置函数，或者干脆自己手写汇编代码。这三种做法的灵活性和可达的性能上限依次提高，但是开发成本也随之陡然上升。一般最常用的 intrinsic 函数通常画风这个样子的：
// 节选自上面 Stack Overflow 的回答
__m256i sign64 = _mm256_set1_epi64x(0x8000000000000000L);
__m256i aflip = _mm256_xor_si256(a, sign64);
__m256i bflip = _mm256_xor_si256(b, sign64);
__m256i cmp = _mm256_cmpgt_epi64(aflip, bflip);
实际上它们就是对底层向量指令的一个简单包装，跟直接写汇编区别不大，只是编译器帮你处理了寄存器分配这种脏活累活。一旦使用的指令集发生变化，比如从 x86 迁移到 ARM，或者是从 AVX2 升级到 AVX512，基本都要对整个代码进行重写，开发成本十分巨大。我的另一个参赛同学就花了一整天将 C++ AVX2 代码迁移到 AVX512，过程中不但要学习新的指令集，还要处理各种细节的差异，花了非常多时间 debug。
Rust 也支持使用 intrinsic 函数编写 SIMD（需要 nightly），不过我们今天要介绍一种更简单的方法。Rust 社区从 2020 年开始就组建了可移植 SIMD 工作组，目前他们的成果——平台无关的 std::simd 模块已经初步完成并进入了主线 nightly 版本中。下面我们就来感受一下用这个模块编写 SIMD 是一种怎样的体验。
// 需要使用 nightly-2022-02-01 以上版本
// 目前使用此模块还需要开启指定 feature
#![feature(portable_simd)]
// 导入向量类型。为了最大化并行度，直接一次拉满 8 组数据。
use std::simd::{mask64x8, u64x8};
// 模仿上面的风格，定义一个 128 位无符号整数的向量类型
#[derive(Default, Debug, Copy, Clone, PartialEq, Eq)]
pub struct U128x8 {
// 高位和低位分别存储在两个 512 位向量中
hi: u64x8,
lo: u64x8,
}
impl U128x8 {
// 构造函数：从给定标量扩展为每一个元素都相同的向量
#[inline]
pub const fn splat(x: u128) -> Self {
Self {
hi: u64x8::splat((x >> 64) as u64),
lo: u64x8::splat(x as u64),
}
}
}
// 实现加法，减法是类似的略过
impl Add for U128x8 {
type Output = U128x8;
#[inline]
fn add(self, rhs: Self) -> Self::Output {
let lo = self.lo + rhs.lo;
// 将进位扩展为全 0 或全 1（即 -1）
let carry = lo.lanes_lt(rhs.lo).to_int().cast::<u64>();
// 所以这里 -carry 也就是 +1
let hi = self.hi + rhs.hi - carry;
Self { hi, lo }
}
}
// 实现移位
impl Shl<u8> for U128x8 {
type Output = U128x8;
#[inline]
fn shl(self, rhs: u8) -> Self::Output {
let lo = self.lo << u64x8::splat(rhs as u64);
let hi = self.hi << u64x8::splat(rhs as u64);
let hi = hi | (self.lo >> u64x8::splat(64 - rhs as u64));
Self { hi, lo }
}
}
impl U128x8 {
// 比较操作（大于）
#[inline]
fn lanes_gt(self, other: Self) -> mask64x8 {
let hi_eq = self.hi.lanes_eq(other.hi);// 先看高位是不是相等
let hi_gt = self.hi.lanes_gt(other.hi);// 如果不等取高位比较结果
let lo_gt = self.lo.lanes_gt(other.lo);// 如果相等取低位比较结果
hi_eq.select_mask(lo_gt, hi_gt)
}
// 条件减法：如果不会下溢出就相减，否则保持不变
#[inline]
fn sub_on_ge(self, other: Self) -> Self {
let c = self - other;
let underflow = other.lanes_gt(self);
Self {
hi: underflow.select(self.hi, c.hi),
lo: underflow.select(self.lo, c.lo),
}
}
// 取模，假设被除数范围是 [0,10M)
#[inline]
pub fn rem10(mut self, m: u128) -> Self {
// 向量取模采用四次比较减法的方式，因为之前标量优化中手动二分的方法难以使用
// 由于 inline，当传入的 m 是常数时，编译器可以将下面的减数都提前计算出来
self = self.sub_on_ge(U128x8::splat(m * 4));
self = self.sub_on_ge(U128x8::splat(m * 4));
self = self.sub_on_ge(U128x8::splat(m * 2));
self = self.sub_on_ge(U128x8::splat(m * 1));
self
}
}
是不是非常简洁优雅？最关键的是，这份代码是平台无关的，也就是说它会在支持 AVX512 的机器上将 u64x8 映射为 zmm，在支持 AVX2 的机器上映射为两个 ymm，在 Apple M1 上映射为四个 Qn，在没有任何 SIMD 扩展的指令集上映射为 [u64; 8] 数组。
接下来是激动人心的时刻，我们快速跑一下 benchmark 来看看 SIMD 带来了多大的性能提升：
测试环境 Intel(R) Xeon(R) Gold 6240R CPU @ 2.40GHz（并不是比赛当时的环境）
从左到右分别是 8 组乘加运算、8 组取模运算、N=256 计算一轮 M2 整体的时间开销。这个结果让我非常沮丧：取模的时间开销竟然是标量版本的 2 倍以上，而乘加操作也没有提高多少，所以整体算一轮 M2 的时间也远不及标量版本。当时我给出的解释是，一方面因为标量版本已经非常优化了，一次 u128 的取模只需要 4 次 u64 比较和 1 次 u128 减法；另一方面向量版本由于无法利用分支跳转，所以只能靠大量的计算，一次 u128 取模需要 12 次 u64 比较和 4 次 u128 减法，还有不少 select 操作。整体来说 SIMD 算力的优势难以抵消计算量的劣势，所以性能还不如原来好。
当时测出这个结果以后，我几乎已经要放弃 SIMD 这条路了。不过随后我跟师兄
@Liu Yiyuan
交流了一番，发现他也写了 AVX2，并且表示效果显著：
得知这个情报以后，我马上就放心多了。这说明 SIMD 这个方向是对的，肯定是我哪里搞错了，这里面一定还有优化空间。到底是哪里搞错了呢？我 lscpu 一看，原来这台测试机上没有 AVX512。这是因为我为了避免编译和测试影响线上程序的运行，用了另一台阿里云免费送给我 1 个月的 ECS 做开发，而这台 ECS 的 CPU 比较古老只有 AVX2（果然便宜没好货啊）。其实对于这两种指令集我之前都没怎么接触过，只是看过一篇 Linus 狂喷 AVX512 的文章，给我留下了一种 AVX512 华而不实的印象。这让我当时对它并没有抱很大的期待，但还是死马当活马医，把程序换到支持 AVX512 的机器上测试了一发：
好家伙！时间直接缩短到 1/3，让 SIMD 的性能一举超过了标量版本。可为什么这两个指令集之间会有如此大的差距呢？我们看看生成的汇编代码就能发现一些端倪：
上图是我分别 perf 了 AVX2 和 AVX512 运行取模 bench 的结果。第一眼从颜色分布上就可以看出，右边 AVX512 具有更高的性能密度，基本上每条指令都利用上了，看不出有什么瓶颈；而左边 AVX2 就明显稀疏了很多，除了多出了 xor 指令外，还意料之外地出现了不少 extract 和 pack 指令（提取元素并重组）。我猜测这些都是由于 AVX2 不支持无符号整数比大小而生成的辅助指令。再进一步看看内容，右边 AVX512 使用的都是 zmm 和新引入的 kn mask 寄存器，而左边的 AVX2 主要使用 ymm 和少量 xmm，数据密度低了一倍，因此指令数量也就多了一倍。我还仔细过了一遍 AVX512 生成的指令，感觉基本已经是最优解了。
通过以上分析，我觉得可以得出这样的结论：
- Rust SIMD 模块能够生成接近最优的本机向量指令。
- AVX512 相比 AVX2 有不小的改进，并且在无符号整数比较方面有巨大优势，并不像人们所说的那样一无是处。
在解锁了 AVX512 的洪荒之力之后，经过 SIMD 优化的 M2 和 M4 计算时间降低到了原来的一半左右。曲线一下子就起飞了，最终卷到了和 OS 专家（chi）并列第二名的位置：
AVX512 助力 omicron 迅速起飞
SIMD 获得大成功之后，我继续乘胜追击，打算将 M1 和 M3 也 SIMD 化。此时开销最大的已经变成了 M3，所以就先从它下手。
首先我注意到，M3 的数据范围并不需要 256 位，其实 192 位就够了，这样可以从 4 个 u64 减少到 3 个。于是我先把标量版本的 U256 优化到了 U192。
接下来我们仿照上面的过程实现 U192x8。整体逻辑是差不多的，唯一的区别是多了一个中间位：
pub struct U192x8 {
hi: u64x8,
mi: u64x8,
lo: u64x8,
}
这个中间位给计算加法进位造成了不小的麻烦，因为原来的算法失效了：如果低位有进位的同时加数为全1，那么 a+b+carry 就会等于 a，结果和 a 比较大小无法判定是否发生了进位。解决方法是多做一次比较，增加了不少计算量：
impl Add for U192x8 {
type Output = U192x8;
#[inline]
fn add(self, rhs: Self) -> Self::Output {
let lo = self.lo + rhs.lo;
let lo_carry = lo.lanes_lt(rhs.lo);
let mi = self.mi + rhs.mi - to_u64x8(lo_carry);
let mi_carry = mi.lanes_lt(rhs.mi) | (self.mi.lanes_eq(u64x8::splat(u64::MAX)) & lo_carry);
let hi = self.hi + rhs.hi - to_u64x8(mi_carry);
Self { hi, mi, lo }
}
}
类似地，其它操作也都增加了不少计算量。直接来看性能测试的结果：
基本上也获得了接近一倍的性能提升，其中主要贡献来自乘加运算（不知为何标量 u192 这么慢）。然而悲催的事情又出现了，当时我在写性能测试的时候，把 U192 改成 U192x8，却忘了将数组长度缩小到 N/8，导致 SIMD 的结果变成了真实值的 8 倍。因此迟迟没有将 M3 改写成 SIMD，很久之后才发现这个乌龙。
在比赛开始后，由于选手们纷纷建立多个连接导致服务器压力过大，有时会被主动限流导致连接断开。此时程序中的 TCP socket 就会返回错误，如果没有处理好就会导致程序卡死或者崩溃。下图就展示了一段网络不是很稳定的时期，可以看到在多个时间点上出现了部分选手直接“躺平”的场面。
为了避免网络原因导致程序崩溃造成的损失，我从网上抄来了一份监控脚本：
while true
do
ps -ef | grep most | grep -v "grep"
if [ "$?" -eq 1 ]
then
nohup nice -n -20 ./target/release/most >> nohup.out &
echo "restart"
fi
sleep 5
done
它的功能就是定期检查指定程序是否还活着，如果没了就自动重启。接下来只需应用 “let it crash” 的思想，让程序发生任何错误都直接崩溃，就可以避免意外躺平。这里需要提醒 Rust 开发者注意的是，在 tokio 中运行的协程 panic 并不一定会导致程序崩溃退出。部署完监控脚本后还带来了另一个效果，那就是新版本上线只需要先编译然后 killall most 即可。
最后我们来用 SIMD 优化 M1 的 64 位整数计算。在上篇的第 9 步优化中我们提到，编译器会利用数学原理自动将 u64 % 常数 u64 优化为两次乘法。这个优化在 SIMD 中是否依然有效呢？经过实验，答案是否定的。因为计算过程需要取乘积的高 64 位，而主流的 SIMD 指令集都是没有这种操作的。Rust 面对这种情况会将 u64 从向量寄存器中逐一提取出来，进行标量计算后再逐一塞回去。。。
同样的代码重复了十几次，真是辛苦您了（
既然这条路行不通，那只好复用之前的老套路做四次减法了。不过其中有一处计算可以简化，那就是比较-选择可以用 min 代替：
#[inline]
fn rem_u64x8(mut f: u64x8, m: u64) -> u64x8 {
f = f.min(f - u64x8::splat(M1 * 4));
f = f.min(f - u64x8::splat(M1 * 4));
f = f.min(f - u64x8::splat(M1 * 2));
f = f.min(f - u64x8::splat(M1 * 1));
f
}
原理也很简单：如果减法发生下溢出，那么在无符号数的表示下一定是一个很大的数。把它跟原来的数取个最小值就能过滤掉溢出的结果。
然而，接下来的性能测试却显示出这里有一个天坑！虽然我想用的是 Simd 结构上的 min 函数，但实际上编译器使用的是标准库中的 min 函数。由于 Simd 结构实现了 PartialOrd 和 Ord trait，因此标准 min 函数会进一步调用 Simd 的 cmp 函数，反映到指令上就是要把所有元素从向量寄存器中逐一提取出来做比较，然后从两个输入中选它认为“小”的那个。很明显这无论在性能还是正确性上都是不对的！
从指令和调试信息上都能明显看出它使用了错误的函数
我尝试了很久也没能找到一种让它选择正确函数的方法，所以迫不得已在这里写了 intrinsic，成为了整个程序中唯一不 portable 的部分（
#[inline]
fn rem_u64x8(x: u64x8, m: u64) -> u64x8 {
use std::arch::x86_64::_mm512_min_epu64;
use std::mem::transmute;
unsafe {
let mut x = transmute(x);
x = _mm512_min_epu64(x, transmute(u64x8::from(x) - u64x8::splat(m * 4)));
x = _mm512_min_epu64(x, transmute(u64x8::from(x) - u64x8::splat(m * 4)));
x = _mm512_min_epu64(x, transmute(u64x8::from(x) - u64x8::splat(m * 2)));
x = _mm512_min_epu64(x, transmute(u64x8::from(x) - u64x8::splat(m * 1)));
u64x8::from(x)
}
}
以下是性能测试结果，从左到右分别是标量实现、SIMD 的错误实现和 intrinsic 实现。可以看出 SIMD 相比标量性能提升了 2 倍以上。
18. 算法优化2：质因数分解
终于又出现一个算法优化了。。。我们小学二年级就知道：一个数被 M 整数，当且仅当它能够被 M 的每一个质因子 P 整除。所以我们只需对每一个 M 做质因数分解，然后分别对每一个质因子计算即可。什么？你问我怎么连这都想不到？其实我一开始就想到了，并且发现 M1 可以分解成若干小质数的乘积，M2 是个质数，M3 太大了计算机算不出来，而 M4 干脆就是以 3 个质因子的形式给出的。
$ factor 20220217214410
20220217214410: 2 5 431 46589 100699
$ factor 104648257118348370704723119
104648257118348370704723119: 104648257118348370704723119
$ factor 125000000000000140750000000000052207500000000006359661
...
好吧我来自己打脸了，这个优化对于标量的性能提升还是相当可观的，而对于向量也有 20% 的提升。多会一点小学数学就能分分钟大幅提高性能，怎么看都比吭哧吭哧搞性能优化要强啊。
到这里我们已经对所有计算完成了向量化改造，下面需要对 SIMD 的实现做进一步的调优了。
之前我在和
@Liu Yiyuan
交流 SIMD 的时候，他问我你是怎么处理进位和溢出的，结果发现我们对此的处理方式并不一样。@Liu Yiyuan 提出了一种预留进位的方式，让所有低位都预留 4bits 的进位，平时只保存 60bits 的有效数字。选择 4bits 是为 x10 考虑的。这样在 x10+b 以及加减法的时候就可以直接计算然后处理进位。跟我之前的实现相比，多了一些移位和 mask 操作，但避免了很多比较。
另外，我还想到一处代码细节的优化。在取模运算中，减法是非常耗时的。所以如果一组数据中的 8 个元素全部都下溢出了（这种情况在 -8M 的时候是容易出现的），就没必要执行减法了，可以提前返回：
#[inline]
pub fn sub_on_ge(self, other: Self) -> Self {
let underflow = other.lanes_gt(self);
+ if underflow.all() {
+ return self;
+ }
let c = self - other;
Self {
hi: underflow.select(self.hi, c.hi),
mi: underflow.select(self.mi, c.mi),
lo: underflow.select(self.lo, c.lo),
}
}
同理在比较运算中，高位全部不相等的情况也是非常可能出现的，这时候就可以跳过所有后面低位的比较。不过这个优化只对 192 位比较有意义，因为在 128 位中只能跳过一次比较，有些得不偿失。
#[inline]
pub fn lanes_gt(self, other: Self) -> mask64x8 {
let hi_eq = self.hi.lanes_eq(other.hi);
let hi_gt = self.hi.lanes_gt(other.hi);
+ if !hi_eq.any() {
+ return hi_gt;
+ }
let mi_eq = self.mi.lanes_eq(other.mi);
let mi_gt = self.mi.lanes_gt(other.mi);
let lo_gt = self.lo.lanes_gt(other.lo);
hi_eq.select_mask(mi_eq.select_mask(lo_gt, mi_gt), hi_gt)
}
加上这两步优化以后，M2 和 M3 的计算时间进一步降低到 1/3 和 1/4 左右，相比原始的标量实现已经有了一个数量级的提升！
20. 决赛开始
做完上面这些优化以后，差不多也快到了决赛开始的时间。2 月 18 日晚 8 点，随着莫队在微信群里一声令下，比赛正式开始。排行榜和形势图清零，页面放出了新的 N 和 M——看上去和资格赛没有什么不同，按惯例做一番质因数分解，跑脚本爬一遍 M4 即可。10 分钟后，我的程序就改完数据上线了。在此期间，其他选手也陆续冲出了起跑线：
令我十分惊喜的是，我的程序 omicron 曲线斜率超过了所有人，竟然一路狂飙不久就冲到第一了。没想到卷王就是我自己！哈哈，提前写了 SIMD 真是个明智的决定！
合影留念：omicron 第一次拿到第一，也是最后一次（
然而好景不长，半个小时后，官方号 alpha 突然大幅升级，马上又把我反超了过去。几个小时后，又有四大天王陆续觉醒，纷纷超过了 alpha。一个晚上的时间，我就从第一名被卷到了第 8 名，心里哇凉哇凉的。这个比赛可真是太卷了！
下篇预告
这篇文章主要介绍了我在资格赛期间用 SIMD 所做的优化，相比标量版本取得了近 10 倍的性能提升，并借此短暂地拿下了增长曲线的第一名。
经过这段时间的实践后我认为，Rust 的 SIMD 模块是一个相当优雅的解决方案：它对底层指令做了跨平台的封装，能够在不同平台上自动生成高效的向量指令，并且写起来十分方便。强烈推荐各位开发者在需要 SIMD 的时候尝鲜体验一下。
下篇文章我会继续记录我在决赛期间垂死求生的故事，分享其他选手的精彩做法，以及我在比赛后的收获和反思。欢迎继续关注~
下篇：其他选手的精彩解法和自己的一些感悟
两周前我参加了一场高频交易模拟赛，这一系列文章是我对这场为期一周比赛的复盘总结。在前两篇中我主要记录了从比赛开始到资格赛为止，我对程序做的各种优化手段和技巧。转眼两周时间过去了，曾经比赛时的那股激情也逐渐平复下来，是时候谈谈这一周经历带给我的感触和思考了。不过在此之前，我们先快速回顾一下比赛题目和决赛过程，然后揭晓其他选手使用的神奇策略吧。
比赛题目
给定一个实时推送的数字流，从中找出长度不超过 N 的连续数字串，满足其组成的正整数是任意 M 的倍数。其中给定常数：
N = 256
M1 = 20220217214410
M2 = 104648257118348370704723119
M3 = 125000000000000140750000000000052207500000000006359661
M4 = 3^50 * 7^30 * 11^20
这些前期工作让我在决赛刚开始的时候短暂地获得第一，但随后又被其他选手纷纷超越。下面我们继续回放一下决赛过程，对细节不感兴趣的同学可以直接跳过看后面的内容。
比赛过程回放（决赛）
由于决赛时比赛服务器只对参赛选手的内网地址开放，其它机器无法访问，所以如何在不影响线上运行的同时进行调试就成了个问题。我们知道这个比赛是非常看重响应时延的，而且决赛时选手间的比拼已经卷进了 10us 量级。经过我的测试，一旦在比赛机器上进行编译等重 CPU 负载的工作，排名就会刷刷往下掉，说明此时程序的响应时延大大加长了（即使已经设置了实时调度和最高优先级）。
这样看来在比赛机上做测试是不太可能了。所以为了验证程序的正确性，我还是自己写了一个简单的服务端做 mock。它的数据生成方式非常简单，就是随机生成一些 M 的倍数，再随机生成一些数字串，最后随机地混合起来。如果我的程序识别出的数字串不符合服务端生成它的频率，就说明我的程序写错了。实践表明这个方法非常有用，多次识别出了程序中存在 bug，避免了直接上线出锅的惨剧发生。
虽然前面我对大整数运算做了很多优化，但最长的 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
原来是这样，我悟了。现在我还有点好奇它使用了什么算法能这么快分解大整数，但当时这都已经不重要了，赶快改代码卷上去要紧啊！
到目前为止我的程序一直是以多线程模式在运行。虽然决赛机上有 2 vcpu，但后来我们意识到它其实只是一个物理核上的两个超线程（云厂商可真会做买卖）。这就意味着实际上我们只有一个核的计算资源，对计算密集型程序来说开两个线程几乎没有什么好处，还会增加线程之间同步的开销。
多线程模式下四个计算任务的平均时延（第二列）
于是我就把程序从多线程改回了单线程，并且彻底扬掉了 tokio，因为不再需要多线程调度器了。但是，我们依然需要一个后台线程来创建 TCP 连接，并通过 channel 发送给计算线程。这样改完以后，整体的计算时间并没有显著增加，反而使得第一个计算的 M1 平均时延降低到了 100us 以内。从排行榜上可以看出抢到前三的次数明显增加了，说明还是有一定效果的。
这一现象让我意识到，相比多线程自动调度来说，单线程具有计算顺序可控的优势。我们可以把计算量最小的放在第一个算，计算量最大的放在最后算，这样整体的平均时延是最低的。更进一步，在整体性能对别人没有明显优势的局面下，还可以使用田忌赛马的战术：优先处理自己最擅长的部分，放弃做的不好的部分。由于比赛规则接近于赢者通吃，因此通过合理地排列计算顺序，也能够抢到更多的分数。
最后还想说一下的是，我做这个优化通宵到了第二天早上 6 点。然而根据后来莫队放出的时延曲线图显示，还有不少选手也在同时通宵内卷，着实恐怖：
决赛第一天各位选手的平均时延曲线图，横轴是时间，纵轴是时延（单位us）。红圈内的后半夜时段仍有多条曲线时延显著降低。
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 的条件。在剩余系里做乘加运算好像也没什么可以投机取巧之处，只能一个一个硬算……总之这个思路也彻底失败了。
随后我又开始想能不能从生成的数字串中挖掘一些规律出来。比如哪些数字、哪些长度的出现频率高，就可以优先算哪部分。于是我对匹配数字的日志做了一番统计，结果很遗憾地发现，各种特性都是均匀分布的：M1-M4 每种数字串出现的频率相同，各种长度的数字串出现的频率也相同。
不过最终通过观察日志，我还是意识到了两个有价值的性质：
- 任意一个能被整除的数字串后面跟上若干个 0 也可以被整除。
- 任意两个能被整除的数字串不会重叠。
第一个十分显然。第二个也很好理解，如果这些数字串都是分别独立构造生成的，然后再混入随机串里，那就几乎不可能出现重叠的情况。
利用这两个性质，我们可以对程序做出如下优化：
- 找到一个能被整除的数字串后，马上向后查看是不是跟着 0，如果有就一起提交答案。
- 做完第一步后，清空 M1-M4 的所有状态。扔掉前面的串从头来过。
这个优化对于以 0 结尾的答案和在一个输入块中的第二个答案，理论上都有比较好的效果。但是由于满足这两个条件的答案并不是很多，所以不会有显著的提升。
这里又一次吃了没学好网络原理的亏：HTTP 从 1.1 开始引入了长连接，所以一个 TCP 连接可以用来发多个请求，并不需要每次都新建连接。在上一步优化中，如果有答案数字串后面跟着 0 的情况，那么可以将多个请求打包在一个 TCP write 操作中一起提交。这个优化可以为后面的答案节省 20us 以上的时间。考虑到当我们发现一个答案后，肯定希望用最快的速度调用 TCP write 将它发出去，而不是再去计算后面的内容，所以整个程序其实只需要一个 TCP 连接发答案就够了。
另外前面其实还做了两个关于 TCP 的设置：NO_DELAY 和 NON_BLOCKING。前者是对低延迟很关键的一个配置，用来禁用 Nagle 拥塞控制算法，让每次写入的数据都立刻发出；后者是为了防止发送陷入阻塞，耽误后面的计算。但我观察到在实际运行中并没有出现阻塞的情况，应该是因为每次发送的包都比较小，几乎不会占满内核缓冲区。
决赛即将过半，卷不过的群友们开始分析排行榜上对手的性能指标。一番估算以后惊恐地发现，人家已经把平均一个数字的计算时间压到了 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 掉内核的网络协议栈。我能想到大致有四种方案，按照实现难度排序依次是：
- 使用 Raw Socket 代替 TCP
这种方案只绕过了内核的 TCP 协议栈，由用户程序从二层或三层开始接管特定 IP 网络包的处理过程。这样不会对其它网络包造成影响，因此可以在云上直接开发调试。但是很有可能对性能不会有显著提高。
- 使用 DPDK 等用户态协议栈
这个是业界标准的 kernel bypass 方案，将网卡驱动和协议栈都移到了用户态，从收包到发包的整个过程都可以留在用户态处理，彻底绕过了内核。但是由于目标机器在阿里云上，并且只有一个虚拟网卡，因此一旦部署 DPDK 接管网卡，随时都有 ssh 失联的危险。另外 DPDK 目前只有几个实验性质的 Rust binding，不知是否好用。虽说也可以将我的程序导出成 C 库用 C 代码粘起来，但是无论怎样都有不小的学习和试错成本。
- 注入内核模块
这种方案和 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 的数字串
平方递推
所有选手一开始都能想到这个平方级别的递推算法。准确地说它的复杂度是
，N 是答案的最大长度，L 是输入串的总长度。我在第 4 步优化和本文开头提到过，这里再复述一下：
对于每个 M，维护以当前位置结尾的长度分别为 1-N 的数字串模 M 的余数，然后逐个追加数字递推后面的余数，公式为
线性递推
预处理
在这个比赛中输入的数字串是一块一块发过来的，而在发送的间隙 CPU 是闲置状态，因此我们可以在这期间做一些预处理以加速下一次的计算。
预言
预处理更进一步就是预言：在输入发过来之前就提前猜测并提交答案。能这么做的基础假设是，答案都是人为生成的。所以如果发现结尾的串再加几个数字就能被整除，那它很有可能就是答案。
这种预言所需的计算量比较大，是平方级别的，并且只能对 M 整体进行取模，所以需要高精度运算。不过好在这部分不在关键路径中，稍微慢一点也是可以接受的。在比赛过程中，群友 @大嗨子 很早就点亮了预言的技能，在前期借此获得了大量 +8，决赛时又开了一个 ping 接近 1ms 的外网机器专门做预言。不过由于能够预言的数字串出现频率较低，加上后来好多选手都学会了预言，所以到后期这个策略的收益就不高了。
以上我们揭晓了这个题目在算法上的正确做法和一些优化技巧。如果全部实现应该就可以拿第一了。不过虽然比赛已经结束了，但是我们对于极致的追求是永无止境的！下面我们就来继续探讨，在算法已经做到最优的基础上，系统方面还有哪些可以挖掘的地方吧。（别忘了还有一位选手写了 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 @松 @大嗨子 @小源 同学。我个人对这种比赛形式是非常资瓷的，因为这是对主办方和参赛方都非常有利的一件事。对于公司来说，我理解办比赛的最大作用是宣传自己、招揽人才，让更多同学了解工业界在做的事情；对于参赛同学来说，这是一个学习各种奇怪知识的非常难得的机会！除此之外，还可以认识更多大佬，了解一个行业，顺便投个简历……两边都赢麻了。
正如松给出的参赛理由一样：机会难得！
希望日后还有机会参加这样有意思的比赛。我们下场比赛再见！
