借鉴生物学家方法，优化 Haskell 编译速度，突破 `O(n³)` 复杂度瓶颈

从生物学家那里取经让 Haskell 编译更快[2026 - 05 - 30]有人顺带提到GHC 有个针对 ApplicativeDo 的标志-foptimal-applicative-do默认关闭因其背后算法运行慢无法投入使用。在作者看来这像个漏洞本以为花一个下午就能搞定这个因速度慢被禁用的优化然而并非如此这是个棘手问题困扰了作者几个月。ApplicativeDo 是 GHC 较冷门功能多数程序不启用启用的大多也用默认设置不用最优标志。但该标志背后问题值得研究改进最优布局算法复杂度后发现和生物学家预测 RNA 链折叠方式的动态规划方法一样。什么是 ApplicativeDo它为何如此强大以从远程社交图谱获取两人共同好友数量为例展示标准 do 语法糖转换为顺序绑定的情况这种执行是严格顺序的需两次独立网络往返。而用 Applicative 实现两次好友列表查询可变成一次数据库访问。手动编写 * 版本易出错ApplicativeDo 允许开发者用普通 do 表示法由编译器决定何时用 *。编译器要处理语句确定依赖关系独立语句用 * 组合有依赖关系用 。最优调度的代价组合独立语句不易不同组合方式性能不同。通过代码块分析依赖关系因 Haxl 会将 * 下计算批量处理成一次往返所以关注总往返次数往返越少延迟越低。GHC 默认算法用贪心策略需四轮最优方案并行处理需三轮节省一次往返。但最优算法时间复杂度是 O(n³)最初论文中含 1000 条顺序语句的最坏情况 do 代码块用最优算法编译需 55 秒贪心启发式算法不到两秒所以最优算法放在很少启用的标志后面。目标是不付出 O(n³) 代价得到最优结果。问题简化语句内容不重要关键是依赖关系可将语句建模为节点用有向边表示依赖。编译器构建树节点有顺序组合和并行组合树的代价是所需轮数。要找到代价最小的合法树论文发现复杂代码块只需检查两个极端分割点除非结果相同否则其中一个最优工作量减到 O(1)。相同结果情况需进一步解决论文将其作为开放性问题留下。失败的启发式方法一种直觉认为代价是最长依赖链但实际并非如此不允许重新排序会增加轮数需真正的最小化搜索。另一种反转二维区间表的方法也被差异测试器证明错误窗口内结构取决于两端二维表是必要的。限制搜索范围病态输入是长链无并行性朴素算法为每个区间检查 O(n) 个分割点。出现相同结果时若最长链等于 c 1搜索可终止。对于纯链无需搜索就知代价工作量从 O(n³) 减到 O(n²)。结合现有优化方法可减少工作量但不能保证最坏情况是二次复杂度密集代码块仍趋向立方复杂度hub 行优化器扫描量和朴素算法一样。与计算生物学的联系RNA 链会自身配对形成二级结构预测折叠是优化问题用 Nussinov 算法解决。ApplicativeDo 代价函数与 RNA 折叠有相同的三角表、复杂度和递归关系。do 代码块与聚合物结构相同编译器进行结构预测。RNA 二级结构预测和 ApplicativeDo 有共同约束禁止键交叉和语句重新排序嵌套结构将指数级搜索空间压缩成多项式级。允许键交叉或语句重新排序会使问题变成 NP 难问题。可借鉴生物学方法顺序组合是 (min, ) 操作ApplicativeDo 代价表受益于单调性引理。与解析建立联系Bringmann 等人的算法实现亚立方时间。但该方法在编译器上下文中不太实用前一节方法让最优算法在实际代码中快速运行亚立方结果是关于问题的结论非编译器实用方案。结论实际和理论解决方案基于每个区间并行性全有或全无的观察可将代码块分割限制昂贵搜索。O(n³) 复杂度影响编译时间应用最长链界限和极端分割捷径可消除编译时间瓶颈密集最坏情况与自然界计算机制有相似之处。