egg: Fast and Extensible Equality Saturation
summary
Equality saturation is implemented as the egg Rust library, which applies rewrites into an e-graph and then runs a single rebuild once per iteration rather than repairing congruence on every merge, cutting congruence-maintenance cost (benchmarks show up to ~30× speedup on tests). Egg also embeds e-class analyses to attach lattice facts (constants, nonzero proofs) and enable conditional or semantic rewrites. Case studies: Herbie speeds simplification 3,000×, a deep-learning graph search runs 48× faster, and linear-algebra kernels improve up to ~1.2–5×.
AI-written summary · about
chapters (6)
- 0:00Introduction to egg
- 1:33Equality saturation basics
- 6:06Understanding e-graphs
- 11:31Deferred invariant maintenance
- 20:49E-class analyses
- 26:08Egg features and case studies
related talks
20mEquality Saturation and Joins
17mBetter Together: Unifying Datalog and Equality Saturation
24mIncremental Equality Saturation
17mContextual Equality Saturation
13mMind the Abstraction Gap: Bringing Equality Saturation to Real-World ML Compilers
19meqsat: An Equality Saturation Dialect for Non-destructive Rewriting
25mDisequalities in E-Graphs: An Experiment
23mRewrite System Showdown: Stochastic Search vs. EqSat