Rewrite System Showdown: Stochastic Search vs. EqSat
For researchers and practitioners in program optimization, this work provides the first rigorous comparison of two approaches, revealing that the dominant paradigm (equality saturation) may not always be optimal.
This paper compares equality saturation to stochastic search for equational program optimization across five benchmarks, finding that equality saturation is not universally superior and that stochastic search can be competitive or better in some cases.
Equality saturation has become a dominant paradigm for equational program optimization. However, it has never been rigorously compared to another approach to the same problem, even though several exist, the most notable being stochastic search. In this paper, we compare equality saturation to stochastic search over five benchmarks to answer the question: are e-graphs actually good?