“Both developer tools and compilers can be seen as special cases of a much simpler and more general pattern known as a graph database [3, 4, 5].”
按年被提到
20202022 · 2 次2026
egg: Fast and Extensible Equality Saturation
egg:快速且可扩展的等式饱和
Max Willsey, Chandrakana Nandi, Yisu Remy Wang, Oliver Flatt, Zachary Tatlock, Pavel Panchekha · 2020
提出重建与 e-class 分析,使 e-graph 等式饱和又快又易扩展
被提及 · 5 人首次 2020-10-02 · 最近 2023-12-16
5不同的人
4活跃月份
4讨论串
181被引(OpenAlex)
e-graph 能高效表示许多表达式上的同余关系,等式饱和技术把它用于重写驱动的编译优化和程序综合,但 e-graph 尚未针对这一用途做专门优化。论文提出两项技术:一种摊销式不变量恢复方法「重建(rebuilding)」,利用等式饱和负载的特点带来渐近加速;以及通用机制「e-class 分析」,把领域特定分析整合进 e-graph,减少临时性改动。作者把它们实现在开源库 egg 中,并在三个已有应用的案例中展示其性能与灵活性。
HN 为什么提它
HN 评论者把它当作 e-graph 与等式饱和最新、带实现洞见的描述来推荐,并把 egg 视为编译器优化遍中可选的一种基础设施。
方法难度 4 / 5约 60 分钟经得起时间
读之前最好知道
1e-graph 与同余闭包(congruence closure)
2项重写(term rewriting)
3编译器优化与程序综合
4Rust 或函数式编程基础
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及引用brzozowski · 2021-03
引用 egg 论证编译器和开发工具都是图数据库模式的特例
引用romes · 2022-07
“The most recent description of e-graphs with an added insight on implementation is egg to the best of my knowledge.”
称它是目前最新、且附带实现见解的 e-graph 描述
引用superlopuh · 2022-07
“Yes, at least these egg-based projects are usign this idea, but it looks like it's just one of the options:”
举 egg 项目为例,说明这个思路只是其中一种选择
引用jiggawatts · 2023-12
“One interesting approach would be to combine egg[1] with this style of vectorised trees for efficient optimisation passes.”
提议把 egg 与向量化树结合,做高效的优化 pass
被提交为 story · 1 次
- egg: Fast and Extensible E-graphs ↗matt_d · 2020-10-02 · 7 分