bottleneck of equality saturation #268
Replies: 2 comments
-
It depends on what "handle" means here. Both extractors take an e-graph and produce an extracted program. The difference between the default extractor and an LP extractor is that, the default extractor is optimal w.r.t. tree size of the extracted program, and the LP extractor is optimal w.r.t. DAG size (i.e., common subterms are counted only once) of the extracted program. In many cases, the tree size of a program is a very good approximation of DAG size. In many use cases of equality saturation, the tree size is what people are actually looking for, thus the relational e-matching paper claimed "e-matching is responsible for 60–90% of the overall run time". However, you are right if you are using a more complex extraction algorithm, it's likely extraction is the bottleneck.
It is much slower, as DAG extraction is an NP-hard problem. Check out https://github.com/egraphs-good/extraction-gym for more detailed comparisons between different extraction algorithms. |
Beta Was this translation helpful? Give feedback.
-
It's also worth noting that the paper cited above (the original eqsat paper) doesn't really do e-matching in a form that similar to the way the egg or modern SMT solvers do it. It instead takes a trigger-based approach that transforms terms as they are inserted. They also bounded the search phase to a size that (if I recall correctly) is orders of magnitude smaller than we explore in egg. So we are spending more (relative) time in e-matching because 1. there is more to e-match and 2. we are using a simpler extraction approach. |
Beta Was this translation helpful? Give feedback.
-
Hi, I was reading on papers about e-graphs and I got a bit confused about the performance of e-graphs. In the paper "Equality Saturation: a New Approach to Optimization" (10.1145/1480881.1480915) the authors used a 0/1 integer programming approach for e-graph extraction, and took 90% of the time according to section 7.1. However, in the paper "Relational E-matching" (10.1145/3498696), the introduction part said that "e-matching is responsible for 60–90% of the overall run time".
It seems to me that the default extractor in egg can only handle trees, as #128 added an LP extractor that can handle DAG. I have two questions:
Beta Was this translation helpful? Give feedback.
All reactions