返回资讯中心
外部精选
软件工程
#开发者实时流

Efficient Extraction for Effectful E-graphs

E-graphs have enabled recent advances in program optimization, synthesis, and verification, yet remain difficult to apply to effectful programs whose memory and I/O operations must respect execution order. Existing effe…

Hacker News 最新dverlaeckt802026/10/19 · 28 天前4 分钟阅读

以下正文同步自 Hacker News 最新,版权归原站所有,已转换为易读排版。

E-graphs have enabled recent advances in program optimization, synthesis, and verification, yet remain difficult to apply to effectful programs whose memory and I/O operations must respect execution order. Existing effect-aware extraction algorithms rely on integer linear programming (ILP) and dominate total runtime. We introduce statewalk DP, a new extraction algorithm that enforces effect ordering efficiently without external solvers. We prove that finding any effect-safe extraction is NP-complete, but show that statewalk DP is tractable in statewalk width, a parameter that measures the complexity of dataflow interactions among effects. In practice, statewalk width generally remains small, enabling statewalk DP to achieve order-of-magnitude speedups over ILP extraction while producing programs comparable to LLVM across our benchmarks. We implement the algorithm in eggcc, a prototype e-graph-based compiler for imperative Bril programs, and demonstrate that effect-aware extraction is no longer a bottleneck.

@article{2026-oopsla-eggcc, author = {Flatt, Oliver and Pal, Anjali and Zhang, Yihong and Tjoa, Ryan and Graham, Kirsten and Fischman, Alex and Nandi, Chandrakana and Rosenthal, Eli and Tatlock, Zachary and Ni, Haobin}, title = {Efficient Extraction for Effectful E-graphs}, year = {2026}, month = oct, journal = {Proceedings of the ACM on Programming Languages}, volume = {10}, number = {OOPSLA2}, articleno = {398}, numpages = {28}, publisher = {Association for Computing Machinery}, url = {https://doi.org/10.1145/3839530}, doi = {10.1145/3839530} }

📝 publications index

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →