Many software tools, including compilers, optimizers and synthesizers, have a common task at their cores — they must transform long and complicated programs into simplified equivalents. These sized-down programs run faster and on a wider range of hardware, but must deliver the same results as their original versions.
Complicating this process is the ad-hoc nature of the problem; each type of program requires a custom approach to achieve these efficiency gains. From shrinking three-dimensional CAD models to optimizing SQL queries so websites load faster, there is no one-size-fits-all solution.
Pavel Panchekha, associate professor in the Kahlert School of Computing, is working to change that. Along with colleagues from the University of Washington, he has developed an open-source toolkit called “egg” that represents a generalized, reusable approach to this problem.
“Traditionally, if you wanted to build compilers, optimizers, synthesizers, it’s a huge undertaking”, Panchekha says. “There are a lot of details you have to get right and a lot of tuning you have to do. This is a whole new way of building where you don’t have to do that; you can get started basically right away, with just a few lines of code.”
It’s also been described as “ridiculously fast.”
Panchekha began work on the toolkit when he was a graduate student in the lab of Zachary Tatlock, professor in the University of Washington’s Allen School of Computer Science and Engineering. Since its release in 2020, egg has helped build an academic community with annual workshops and industry adoption.
Panchekha, Tatlock, along with coauthors Max Willsey, Chandrakana Nandi, Yisu Remy Wang, and Oliver Flatt. have now published a formal paper — egg: Fast and Extensible Equality Saturation — in the journal Communications of the ACM (CACM). There, it was selected as a Research Highlight, which recognizes outstanding research with strong, novel contributions to the field and broad interest to the computing world.
The toolkit uses data structures known as “equality graphs” (e-graphs) to compare the various ways a given computer program can be built to arrive at the same solution. Once the toolkit reaches “equality saturation” — when a critical mass of potential configurations have been found — it can determine which of the configurations provide the greatest efficiency gains.
The concepts of e-graphs and equality saturation have been explored for optimization since 2009 but have yet to deliver on their promise of replacing traditional optimizers and their ilk. Now, egg has been applied broadly and re-implemented across the tech industry. For example, hardware engineers at companies such as Intel have adopted e-graphs to improve their chip design.
Additionally, by integrating egg into his own numerical computing tool, called Herbie, Professor Panchekha was able to make it 3000 times faster while also improving its results.”
“What’s remarkable about the egg project is how quickly it went from a research idea to a wide-ranging toolkit,” said Tatlock. “In just a few years, it’s been adopted across domains from deep learning to hardware design. We’re seeing 50x speedups in neural network optimizations, 63% smaller hardware circuits, and even production compilers being rebuilt around e-graphs. By making equality saturation practical, egg essentially gave everyone a powerful new hammer — and it turns out many nails were waiting.”
Panchekha ascribes egg’s quick adoption to the way it has changed developers’ approach to optimizer design.
“It’s a really flexible system. That means you can experiment more,” Panchekha says. “There’s things egg can’t do yet—in some ongoing work here at Utah on computer graphics, it uses too much memory—but even there you can use egg as a library to test out ideas and figure out what works, which you can then transfer to a traditional approach.”