北京
E-graph（等价图）这几年在程序优化、综合和验证里出尽风头，但一碰到带副作用的程序就卡壳——内存读写和 I/O 操作必须遵守执行顺序，顺序一乱，优化出来的程序就是错的。
更麻烦的是"提取"这一步。已有的效应感知提取算法靠整数线性规划（ILP）来解，结果它反过来吃掉了总运行时间的大头。优化器没把程序优化快，先把自己优化成了瓶颈。
一篇发表在 OOPSLA 2026 的论文给出了新解法：statewalk DP。作者包括 Oliver Flatt、Anjali Pal、Yihong Zhang、Ryan Tjoa、Kirsten Graham、Alex Fischman、Chandrakana Nandi、Eli Rosenthal、Zachary Tatlock、Haobin Ni。
先说清楚这道题本身有多硬。研究团队证明：只要想找到一个"效应安全"的提取结果，问题就是 NP-complete 的。也就是说，不存在既通用又快的简单答案。
但证明难，不等于所有实例都难。他们引入了一个参数——statewalk width，用来衡量效应之间数据流交互的复杂程度。结论是：statewalk DP 在这个参数上是可 tractable 的。
关键在于，实际程序里这个宽度通常保持得很小。理论上的最坏情况没有在日常代码里兑现，算法就有了用武之地。
效果直接体现在数字上：相比 ILP 提取，statewalk DP 实现了数量级的速度提升，而且不需要外部求解器。省掉的不只是时间，还有一整套求解器依赖。
速度上去了，质量有没有掉？论文给出的答案是：在他們的基准测试上，生成的程序与 LLVM 相当。
团队把算法实现在 eggcc 里——一个基于 e-graph、面向命令式 Bril 程序的原型编译器。实测下来，效应感知提取不再是瓶颈。
这件事的意义可以拆成几层看：
- 问题定性：效应安全提取被证明是 NP-complete，难度有了明确边界；
- 参数化出路：statewalk width 把"难不难"从问题本身转移到了具体实例上；
- 工程落地：不依赖外部求解器，数量级加速，程序质量对标 LLVM；
- 瓶颈转移：提取不再是编译器流水线上拖后腿的那一环。
对做编译器的人来说，最后一条可能最实在。一个环节从"主导总运行时间"变成"不再是瓶颈"，意味着此前被它挡住的优化空间，现在可以重新算了。
当然，eggcc 目前还是原型，面向的是 Bril 这门命令式语言。从原型到生产编译器之间隔着多少坑，论文没有展开，也不该由这篇介绍替它承诺。
但至少有一件事被摆到了台面上：带副作用的程序做 e-graph 优化，卡脖子的地方未必是优化本身，而可能是最后那一步"从图里挑出正确程序"的提取。现在，这一步有了更快的走法。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
