从生物学家那里“偷师”：如何加速 Haskell 的编译

背景

这一讨论的起源非常偶然。在 Hacker News 上，有人顺带提到 GHC（Glasgow Haskell Compiler）中有一个名为 -foptimal-applicative-do 的标志。该标志旨在启用一种更优的 ApplicativeDo 算法，但默认情况下它是关闭的，因为背后的算法过于缓慢，无法在生产环境中使用。

对于作者而言，这听起来像是一个 Bug。通常，如果一个优化是正确的但仅仅因为速度慢而被禁用，这应该是一个可以在一个下午内修复的问题。然而，事实并非如此。这是一个真正棘手的问题，并且困扰了作者数月之久。

ApplicativeDo 本身是 GHC 内部一个相对冷门的角落。大多数程序不会开启它，即使开启了，大多数用户也满足于默认行为，很少去触碰那个“最优”标志。即便在编译器内部标准看来，这也属于深奥的领域。然而，该标志背后的问题本身非常有价值。作者在追逐最优布局算法的算法复杂度改进时，意外地发现该问题与生物学家用于预测 RNA 链折叠方式的动态规划算法惊人地相似。

核心内容

什么是 ApplicativeDo，以及它为何出色？

为了理解其价值，我们看一个从远程社交图谱中获取两个人共同好友数量的经典例子：

numCommonFriends x y = do
  fx <- friendsOf x
  fy <- friendsOf y
  return (length (intersect fx fy))

标准的 do 语法糖解糖（desugaring）会将其转换为顺序绑定（sequential binds）：

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 这样的 Monad 可以利用这一点，将与 <*> 结合的计算批处理为单个往返。两次好友列表查找变成了一次数据库查询。

然而，手动编写 <*> 版本很脆弱。如果在两个语句之间添加依赖关系，需要重构回 >>=；如果移除依赖关系，忘记切换回 <*> 可能会损失性能。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 将所有位于 <*> 下的内容批处理为一个往返，我们关心的指标是总往返次数。往返次数越少，延迟越低。

GHC 的默认算法采用贪婪策略：它从前面抓取最长的独立语句序列，发出它，然后重复。从开头开始，aFriends 不能与 aInfo（依赖于它）分组，所以第一组只有 aFriends。这个贪婪的决定将其他所有内容推迟了一轮，导致总共四轮。

最优计划将两半并排排列。两次好友查找共享第 1 轮，两次资料查找共享第 2 轮，score 在第 3 轮等待两者。这节省了一个完整的往返。

最优算法能找到这个三轮调度方案，但其复杂度为 $O(n^3)$。在引入该功能的原始论文《将 Haskell 的 do 符号解糖为 Applicative 操作》中，一个包含 1,000 个顺序语句的最坏情况 do 块，使用最优算法编译需要 55 秒，而使用贪婪启发式算法则不到两秒。因此，最优算法位于一个很少启用的标志后面。

目标是在不支付 $O(n^3)$ 成本的情况下获得最优答案。

问题简化

语句及其内容无关紧要；只有依赖关系才重要。我们可以将语句建模为一系列节点，有向边代表依赖关系：

节点序列: [1] -> [2] -> [3] ...
依赖边:   1->2, 2->3, 1->3 等

编译器在这些语句之上构建一棵树，而不重新排序它们。每个节点要么是顺序组合，要么是并行组合：

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$ 的语句跨度：

$$ C[i, j] = \min_{k} (C[i, k] + C[k+1, j]) $$

其中最小值是在所有可能的分割点 $k$ 上取的，但前提是分割后的两部分是独立的（即没有从左侧部分指向右侧部分的依赖边，反之亦然，否则只能作为 Seq 处理）。

$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，它们强制至少三轮。然而，上述右侧示例的最长链只有两个箭头，但成本为三。禁止重排的限制意味着跨越箭头阻止了分离两半，强制了额外的一轮。强制额外轮次的因素在局部不可