Oatlog: A high-performance e-graph engine

Abstract

Modern software development depends on efficient and reliable optimizing compilers. Traditional compilers apply a sequence of transformations to a single version of a program, with the final result being dependent on the order in which optimizations are applied. However, no single ordering can capture all beneficial optimizations for all programs, a limitation known as the phase ordering problem. This motivates equality saturation, a technique in which the compiler compactly represents many program variants using e-graphs and later extracts the optimal representation using a global profitability heuristic. Equality saturation can improve code quality while simplifying compiler development. Despite these advantages, the adoption of e-graphs in compilers and other domains is limited by performance challenges. These arise from a combinatorial explosion in rewrite possibilities, requiring sophisticated e-graph engines and motivating research into e-graph technology. We introduce Oatlog, an ahead-of-time compiling e-graph engine that significantly outperforms egglog, the currently fastest mainstream e-graph engine. Oatlog achieves speedups over 100x for very small e-graphs, gradually decreasing to a 2x speedup at 106 e-nodes and roughly matches egglog’s performance beyond 107 e-nodes. Oatlog implements a subset of the egglog language and can itself be seen as a compiler from egglog to Rust. As a Rust procedural macro, it complements egglog by focusing on being embeddable within applications rather than on interactive use. We primarily attribute Oatlog’s performance gain to careful programming and performance engineering, but it also benefits from two novel techniques. The first, invariant permutations, exploits commutative relations to optimize queries and reduce memory usage. The second, trie query planning, amortizes index lookups across rewrite rules during e-matching.