借用生物学家的方法来更快速地编译Haskell

# 从生物学家那里偷师，让 Haskell 编译更快 来源：https://www.iankduncan.com/engineering/2026-05-30-stealing-from-biologists-to-compile-haskell-faster 事情始于有人随口提到，GHC 有一个 ApplicativeDo 的标志（`-foptimal-applicative-do`），默认是关闭的，因为它背后的算法太慢，无法使用。 这在我看来就像个 bug。一个正确但因慢而被禁用的优化，我以为可以在一个下午搞定。 结果并不是；这实际上是一个相当困难的问题，而且这个问题困扰了我好几个月。 `ApplicativeDo` 一开始就是 GHC 中一个不起眼的角落。大多数程序从不开启它，而开启的大多数程序用默认设置就足够了，很少会去碰那个最优标志，所以即使按编译器内部标准来看，我们也已经深入杂草了。但这个标志下的问题是个好问题，而追求最优布局算法在算法复杂度上的改进，带我去了一个意想不到的地方：生物学家用来预测 RNA 链如何折叠的同一套动态规划方法。 ## 什么是 ApplicativeDo，它为什么很酷？ 考虑一个经典例子：从远程社交图中获取两个人的共同好友数量： ``` numCommonFriends x y = do fx <- friendsOf x fy <- friendsOf y return (length (intersect fx fy)) ``` 标准的 `do` 脱糖会变成顺序绑定： ``` friendsOf x >>= \fx -> friendsOf y >>= \fy -> return (length (intersect fx fy)) ``` 这是严格的顺序执行。第二次 `friendsOf` 调用必须等第一次完成才能开始，因为 `>>=` 把左边的结果传给右边。尽管 `fy` 不依赖 `fx`，但 `>>=` 无法表达这种独立性。我们需要两次独立的网络往返。 这两个获取操作可以用 `Applicative` 来写： ``` (\fx fy -> length (intersect fx fy)) <$> friendsOf x <*> friendsOf y ``` 现在独立性被编码在类型中。`<*>` 的类型是 `f (a -> b) -> f a -> f b`，意味着第二个参数不能依赖第一个。像 Haxl 这样的单子利用这一点，将 `<*>` 组合的计算批处理成一次往返。两次好友列表查询变成一次数据库访问。 手动编写 `<*>` 版本很脆弱。在两个语句之间添加依赖需要重构回 `>>=`；移除依赖则可能因为忘记切换成 `<*>` 而留下性能隐患。`ApplicativeDo` 允许开发者编写普通的 `do` 表示法，而编译器自行判断何时可以合法地使用 `<*>`。 编译器的任务是接受一系列语句，确定依赖关系，并将独立语句分组在 `<*>` 下，只有当依赖强制时才回退到 `>>=`。 ## 最优调度的代价 分组独立语句并不总是直截了当的，不同的分组会产生不同的性能特征。考虑这个代码块： ``` do aFriends <- friendsOf alice aInfo <- profilesOf aFriends -- 需要 aFriends bFriends <- friendsOf bob bInfo <- profilesOf bFriends -- 需要 bFriends score <- compatibility aFriends bInfo -- 需要 aFriends 和 bInfo return (aInfo, bInfo, score) ``` 追踪依赖关系：`aInfo` 需要 `aFriends`；`bInfo` 需要 `bFriends`；`score` 需要 `aFriends` 和 `bInfo`。两个 `friendsOf` 调用完全独立。 因为 Haxl 将 `<*>` 下的所有内容批处理成一轮，我们关心的指标是总轮数。轮数越少，延迟越低。 两种调度并排比较。默认的贪心算法需要四轮：第一轮只有 aFriends；第二轮批处理 aInfo 和 bFriends；第三轮是 bInfo；第四轮是 score。最优调度只需三轮：第一轮批处理 aFriends 和 bFriends；第二轮批处理 aInfo 和 bInfo；第三轮是 score。 GHC 的默认算法是贪心的：它从开头抓取最长的独立语句序列，发射它，然后重复。从开头开始，`aFriends` 不能与 `aInfo`（依赖它）分组，所以第一个组只有 `aFriends` 单独。这个贪心决策将其他所有事情推迟了一轮，总共四轮。 最优方案将两半并排放置。两次好友查询共享第一轮，两次个人资料查询共享第二轮，`score` 在第三轮等待两者。这节省了整整一次往返。 最优算法能找到这个三轮调度，但它的复杂度是 `O(n^3)`。在介绍该功能的原始论文（*Desugaring Haskell's do-notation Into Applicative Operations* (https://www.microsoft.com/en-us/research/wp-content/uploads/2016/08/desugaring-haskell-haskell16.pdf)）中，一个最坏情况下的 `do` 块包含 1000 个顺序语句，使用最优算法编译需要 55 秒，而贪心启发式算法不到两秒。因此，最优算法被隐藏在一个很少启用的标志后面。 目标是在不支付 `O(n^3)` 代价的情况下达到最优答案。 ## 问题简化 语句及其内容无关紧要；只有依赖关系重要。我们可以将语句建模为一系列节点，有向边代表依赖关系： 五个语句排成一行，标记为 aFriends、aInfo、bFriends、bInfo、score。箭头从 aFriends 指向 aInfo，从 bFriends 指向 bInfo，从 aFriends 指向 score，从 bInfo 指向 score。 编译器在不重排这些语句的情况下构建一棵树。每个节点要么是顺序组合，要么是并行组合： ``` data Tree = Leaf Stmt | Seq Tree Tree | Par Tree Tree ``` `Par` 仅当它的两边之间没有依赖时才合法。一棵树的代价是它所需的轮数： ``` cost (Leaf _) = 1 cost (Seq l r) = cost l + cost r -- 顺序：轮数相加 cost (Par l r) = max (cost l) (cost r) -- 并行：等待较慢的分支 ``` 目标是找到最小代价的合法树。论文中给出的递推关系作用于从 `i` 到 `j` 的一段跨度： `O(n^3)` 的复杂度完全来自最后一行。有 `O(n^2)` 个跨度，对于每个纠缠的跨度，算法尝试 `O(n)` 个分割点。 论文通过注意到在纠缠的节点块中，只需要检查两个极端切割——剥离第一条语句或最后一条语句——来优化这一点。除非这两个切割打成平手，否则其中一个被证明是最优的，将工作减少到 `O(1)`。 为什么这个极端切割捷径有效？任何一个纠缠块的任何分割都必须是顺序的，所以在 `k` 处分割的代价是 `C[i,k] + C[k+1,j]`。因为向一个块添加语句只会增加其代价（或保持不变），代价函数是单调递增的。如果我们只剥离第一条语句（`k=i`），代价是 `1 + C[i+1,j]`。如果我们剥离最后一条语句（`k=j-1`），代价是 `C[i,j-1] + 1`。任何更靠中间的分割都会求和两个更大的子块，根据单调性，它们不可能比从边缘剥离一条语句更便宜。唯一需要进一步搜索的情况是这两个极端切割打成平手，因为更深的切割 *可能* 也与之平手，但除非极端切割本身平手，否则它永远不会打败它们。剩下的挑战就是解决这些平局。 两个四语句示例。左边箭头从一到三和从二到四：代价为二，因为没有什么能阻止它分割成一二然后三四。右边箭头从一到二、从一到四和从三到四：代价为三，因为从一到四的长箭头跨越了整行，阻止了任何干净的分割。 两个几乎相同的依赖结构可能具有不同的代价，完全取决于是否有一个长依赖跨越了其他依赖。论文将有效解决这些平局的问题留作开放问题。 ## 失败的启发式方法 一个自然的直觉是假设代价只是最长的依赖链。如果语句 A 提供 B，B 提供 C，那么它们至少需要三轮。然而，上面右边的例子有一条最长为两个箭头的链，但代价是三个。禁止重排意味着跨越箭头阻止了将两半分开，强制多一轮。导致额外一轮的因素在局部是不可见的；它需要在一个真正的搜索上进行真正的求最小值。 另一种方法是将二维跨度表反转：对于每个起始语句和每轮预算，计算序列能向右延伸多远。这种一维、单调的方法将平局转化为一个布尔检查，看下一个块是否符合预算。 差异测试器很快否定了这种方法： 七个语句，带有若干依赖箭头。高亮窗口跨越语句二到六。一条箭头从语句三一直延伸到语句七，而语句七位于窗口之外。在窗口内部，语句四和五之间有一条虚线接缝，标记了这一行可能并行分割的位置。 在高亮窗口（语句二到六）中，左右两半之间没有依赖，允许它们并行运行，代价为二。然而，从左到右扫描，从语句二开始，跟随一条箭头向外到语句七。因为箭头的头部在窗口外，扫描假设这个块一直延伸到七，完全错过了语句四和五之间的并行接缝。 一个窗口内部的结构依赖于它的两个端点。从右侧离开的箭头改变了内部结构，单侧扫描无法检测到它。二维表是必要的。 ## 限制搜索范围 导致 55 秒编译时间的病态输入是一条长链，其中每个语句依赖于前一个，零并行。该输入中的每个跨度都会产生平局，而朴素算法对每个跨度检查 `O(n)` 个切割。 在平局中，已知答案要么是 `c` 要么是 `c+1`，最长链是下界。如果通过该跨度的最长链已经等于 `c+1`，那么下界等于上界，搜索可以立即终止： ``` -- 在平局中，答案被确定为 c 或 c+1： if longestChain[i,j] == c + 1 then c + 1 ``` 对于一个纯链，通过一个跨度的最长链就是它的长度，这总是 `c+1`。这个条件在每个平局上都会触发，所以无需搜索排除更便宜的分割就能知道代价。我们仍然需要扫描来恢复树的实际切割，但第一次尝试的分割点就已经是见证者——因此每个跨度的工作从线性下降到单次检查，整个过程从 `O(n^3)` 降到 `O(n^2)`。 结合论文已有的优化——在可行时采用并行，对非平局使用极端切割捷径——大大减少了工作量： | 输入 | 朴素切割检查次数 | 优化切割检查次数 | |------|-------------------|-------------------| | 50 链 | 20,825 | 1,225 | | 100 链 | 166,650 | 4,950 | | 200 链 | 1,333,300 | 19,900 | | 50 现实 | 1,550 | 322 | | 100 现实 | 4,544 | 1,426 | | 200 现实 | 47,471 | 3,583 | | 100 双链 | 166,551 | 7,252 | | 50 密集 | 20,729 | 1,521 | | 150 密集 | 562,178 | 14,554 | | 50 枢纽 | 1,225 | 1,225 | | 200 枢纽 | 19,900 | 19,900 | 优化后的计数是总工作量：为产生最优树而执行的每次切割评估，而不仅仅是代价。在链上，每个跨度的搜索消失了，只留下不可避免的 `O(n^2)` 见证恢复过程；现实块大约比朴素方法低一个数量级。（树与朴素方法在每一行都是相同的——相同的调度，只是做了更少的工作。）这并不保证平方的最坏情况：一个由长跨度箭头连接并带有内部并行的密集块仍然趋向立方。`枢纽` 行——每个语句馈送给一个最终 sink——是唯一一个打成平手的模式：每个跨度平局代价为二，但最长链也是二，所以界从不会闭合，优化器扫描的数量与朴素方法一样多。捷径在长链固定代价时有用；当一开始就没有长链时，它无法帮助。这种形状在实际代码中很少见，而残余的密集情况正是下面的算法所要处理的。 ## 与计算生物学的联系 为了理解为什么这个问题是可处理的，我们可以看看计算生物学。 RNA 通常是一条单链（`A`、`U`、`G`、`C`）。没有第二条链可以配对，链与自己配对。互补的片段折叠回来，粘在一起形成茎和发夹环。 ``` 5'─ G C A U U ... │ │ │ │ │ 一段折叠回来与后面互补的片段配对 C G U A A ... ``` 产生的结构就是链的二级结构。物理上，它会稳定在自由能最低的构型（大致是最多配对）。预测这个折叠是一个优化问题，传统上用 Nussinov 算法（1978）解决。 对于从 `i` 到 `j` 的一段，要么第一个碱基未配对，要么它与某个碱基 `k` 配对，在内部围出一个子结构，外部围出另一个：`best[i,j] = max over split point k of (inside + outside)`。这与 `ApplicativeDo` 代价函数使用相同的三角形表、相同的 `O(n^3)` 复杂度、以及相同的在分割点上组合的递推关系。 一个 `do` 块在结构上与一条聚合物相同。语句是骨架上的残基。依赖箭头是限制折叠的键。编译器在执行结构预测，寻找能量最低的构型，其中“能量”是延迟。单子绑定是僵硬的骨架段；应用子组是独立折叠的结构域。 这种相似性源于一个共同的约束。在 RNA 二级结构预测中，标准模型禁止键交叉：如果碱基 `i` 与 `j` 配对，且 `k` 位于它们之间，那么 `k` 的伙伴也必须位于它们之间。键嵌套；它们不交错。 在 `ApplicativeDo` 中，匹配规则是语句不能重排。结果树是序列的一个有序括号化，它整洁地嵌套。非交叉和禁止重排是同一个数学禁令，正是这种嵌套将指数搜索空间压缩为多项式搜索空间。 如果允许 RNA 键交叉（假结），折叠就变成 NP 难。如果允许 `ApplicativeDo` 重排语句（仅对交换单子是安全的），你也会失去嵌套结构，问题同样变成 NP 难。 由于问题共享这种结构，我们可以借用高级解决方案。顺序组合取两部分之和的最小值（`min(C[i,k] + C[k+1,j])`）。这在数学上是 `(min, +)` 运算——通常称为 min-plus 或热带矩阵乘法，其中最小值代替加法，加法代替乘法。在矩阵上计算这个通常与全对最短路径问题一样难。然而，`ApplicativeDo` 代价表得益于论文的单调性引理：相邻条目相差最多为 1。 这就是与解析的联系回归的地方。1975 年，Leslie Valiant 证明了上下文无关文法解析（`O(n^3)` 的 CYK 算法）可以归约为布尔矩阵乘法，突破了立方界限，实现了亚立方时间。几十年来，开放的问题是同样的技巧是否适用于像 RNA 折叠这样的优化问题，它们使用 `(min, +)` 而不是布尔运算。Bringmann 等人的算法（*Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product* (https://arxiv.org/pdf/1707.05095), FOCS 2016）最终实现了这一点——它本质上是热带半环上的 Valiant 解析器，之所以可能，只是因为有界差分性质使得数字不会增长得太大。