Equality saturation tools have long struggled to balance theory and practice—keeping e-graphs clean while avoiding the exponential term explosion that kills performance. Philip Zucker spent over a year chasing this problem. His latest encoding runs in half a second on a benchmark that previously either timed out or took minutes. The approach puts competitive equality saturation within reach for Souffle-based tools.
The Problem With Naive Encodings
Zucker's early attempts revealed why this problem is harder than it looks.
The first approach used algebraic data types (ADTs) to represent terms. Conceptually clean—ADTs hash-cons themselves, preventing duplicate generation—but the encoding didn't share pieces the way proper e-graphs do. Acceptable for modeling, unacceptable for performance.
The second attempt hacked a union-find primitive into Souffle through user-defined functors. The operational dependence proved impossible to reason about. Souffle shreds complex rules into simpler components at compile time, making imperatively-constructed state unreliable. A rule that looks like it should execute as a unit instead expands immediately into separate rules.
Both approaches shared a fatal flaw: benchmarks testing associativity and commutativity across "1 + 2 + … + 9" either ran for over a minute or failed to terminate.
Three Ideas That Worked
The breakthrough combines three separate insights.
External iteration.** Rather than relying on Souffle's internal fixedpoint mechanism, Zucker wrote the datalog program to consume a database and produce a database. A bash loop runs Souffle repeatedly until saturation. This keeps the e-graph clean—rebuilding shrinks it, ematching grows it. Cramming everything into a single fixedpoint lets the representation space become "horrifically exponential" before meaningful work completes.
External unionfind.** This idea failed in earlier attempts but became essential here. By keeping the union-find structure outside Souffle's awareness, Zucker sidestepped operational dependence problems. The key: Souffle's stratification guarantees that if strata n relies on a relation from strata m (where m < n), Souffle truly calculates m first. This lets the union-find reset cleanly between iterations, filtering stale data and reducing the need for subsumption.
Change tracking.** Congruence closure is straightforward in datalog—rules express when two terms with identical substructures should be considered equivalent. But Souffle doesn't know that adding to an equality relation could trigger more rebuilding. The change-tracking approach limits canonicalization to only nodes affected by recent modifications, preventing unnecessary recomputation across the entire graph.
Why It Matters
The benchmark confirms correctness: 18,660 e-nodes equals the theoretical value for a fully associative-commutative expansion of 1 + 2 + … + 9. Performance—0.544 seconds with four parallel threads—puts this squarely in egg's territory.
This matters for different audiences:
| Audience | Why it matters |
|---|---|
| Program synthesis developers | Souffle offers different trade-offs than egg's Rust foundation—static analysis tooling, predictable performance profiles |
| Compiler writers | Equality saturation enables aggressive optimization passes; Souffle integration opens new backend options |
| DSL implementers | Reasoning about algebraic properties (associativity, commutativity) becomes tractable in datalog |
| Formal methods researchers | The pattern—external loops, change tracking, strategic stratification—appears applicable beyond this specific problem |
The practical win: before this work, developers needing equality saturation reached for egg or wrote custom C++. Now there's a viable Souffle path.
Bottom Line
Zucker achieved what seemed impossible: a Souffle e-graph encoding fast enough for real work. External iteration prevents exponential blowup. External unionfind avoids Souffle's rule-shredding surprises. Change tracking limits canonicalization to affected nodes. The combination is specific enough to replicate and general enough to adapt.
Key takeaways
- External fixedpoints (rebuilding between iterations) can turn nonterminating datalog into fast datalog
- Keeping imperative structures outside the datalog engine avoids Souffle's rule-expansion surprises
- Tracking only changed nodes prevents exponential blowup during canonicalization
- This work makes Souffle viable for equality saturation tasks previously requiring egg
- Benchmark performance went from minutes/nonterminating to under one second
Frequently asked questions
What is an e-graph?
A data structure that efficiently represents large sets of equivalent terms by sharing common subexpressions, crucial for equality saturation where many expressions represent the same value.
How does this differ from egg?
Both achieve competitive performance, but egg uses a Rust-based architecture while this approach runs on Souffle datalog, offering different tooling, static analysis capabilities, and integration patterns.
What was wrong with the previous approaches?
Earlier encodings didn't properly share e-graph pieces or collapsed everything into one fixedpoint, causing term-space explosion before useful results emerged.
What does "external fixedpoint" mean practically?
Rather than relying on datalog's built-in fixedpoint computation, Souffle runs in a loop at the shell level—producing output that becomes the next iteration's input until saturation.
Can I adapt this for my own datalog project?
The pattern—external iteration, change tracking, using stratification—applies beyond this specific benchmark. Zucker's posts contain implementation details for similar problems.