Handling associative and commutative operations improves program optimization memory use
Associativity and Commutativity in Equality Saturation
Programming Languages
Summary
Programs can be optimized by finding all ways to simplify or rewrite their parts, but this often creates too many possibilities to handle efficiently. The authors found a better way to manage operations like addition or multiplication, which don't care about order or grouping, by treating their inputs as unordered collections. This approach helps keep the optimization process from using too much memory in certain cases, making it more practical. Their method stores expressions as multisets, which naturally handle these kinds of operations.
What this means in practice
- •For compiler engineers: Use equality saturation with native handling of associative and commutative operators to reduce memory use during optimization.
- •For database query optimizers: Improve query plan optimization by efficiently handling associative and commutative operations in expression rewriting.
Authors
Tarik Rosin, Marcel Ullrich, Sebastian Hack
Abstract
Equality saturation is a promising technique for program optimization which sidesteps the phase ordering problem. However, current e-graph implementations grow exponentially large, even for simple examples. Many practical applications involve associative and commutative (AC) operators. We present an extension of relational e-matching that handles AC operators natively by storing terms as multisets. Preliminary results show that equality saturation modulo AC uses asymptotically less memory in certain cases.