PLDI 2025 (series) / EGRAPHS 2025 (series) / EGRAPHS 2025 /
Oatlog: A performant ahead-of-time compiled e-graph engine
We introduce oatlog, an e-graph engine implementing the egglog language. Oatlog is intended for equality saturation (EqSat) and is implemented as a relational database using semi-naive evaluation. Concretely, oatlog is a Rust procedural macro that embeds EqSat theories into applications. We find that its ahead-of-time compilation of theories is a key asset, simplifying debugging and prototyping while being more amendable to performance engineering. Additionally, the ahead-of-time architecture naturally lends itself to relation and whole-ruleset optimization. Our experiments show that oatlog is faster than egglog for small e-graphs of up to about $10^5$ e-nodes.
Extended abstract (egraphs2025-paper9-oatlog.pdf) | 119KiB |