High performance E-graphs on multi-core CPUs
Speaker: Fritz Obermeyer2026-08-20
Abstract
Recent benchmarks (https://arxiv.org/abs/2605.19005) compare sequential E-graph saturation against parallel alternative algorithms. However equality saturation is highly parallelizable. In this talk I’ll discuss two decades of low-level performance learnings around an E-graph + datalog engine for single-sorted arity-restricted languages: nullary and binary functions, and unary and binary relations. For rules that create only E-nodes and relational facts (no new E-classes), this engine scales to hundreds of millions of facts in tens of minutes, getting >95% average core utilization on a 32-core AMD zen5 machine.