Why is the extraction algorithm looping through all e-classes?

[Bastacyclop]

Hi!

Thefind_costs implementation for extraction is looping through all e-classes:

egg/src/extract.rs

Lines 286 to 293 in 18d7f61

	fn find_costs(&mut self) {
	let mut did_something = true;
	while did_something {
	did_something = false;
	for class in self.egraph.classes() {
	let pass = self.make_pass(class);
	match (self.costs.get(&class.id), pass) {

In the POPL 2021 paper, it is mentioned that:

Extraction can be formulated as an e-class analysis when the cost function is local. The analysis
data is a tuple (n, k (n)) where n is the cheapest e-node in that e-class and k (n) its cost. The make(n)
operation calculates the cost k (n) based on the analysis data (which contain the minimum costs) of
n’s children. The merge operation simply takes the tuple with lower cost. The semilattice portion of
the analysis invariant then guarantees that the analysis data will contain the lowest-cost e-node in
each class.

However, the loop updating e-class analyses looks quite different, looping through pending analyses instead of all e-classes:

egg/src/egraph.rs

Lines 705 to 716 in 18d7f61

	while let Some((node, class_id)) = self.analysis_pending.pop() {
	let class_id = self.find_mut(class_id);
	let node_data = N::make(self, &node);
	let class = self.classes.get_mut(&class_id).unwrap();
	let did_merge = self.analysis.merge(&mut class.data, node_data);
	if did_merge.0 {
	self.analysis_pending.extend(class.parents.iter().cloned());
	N::modify(self, class_id);
	}
	}
	}

So, I have two questions:

1. Why is the extraction algorithm looping through all e-classes, and not maintaining pending analyses? Would that not avoid unnecessary work where an e-node cost is re-computed even though its children have not changed?
2. Why is there not an Analyser structure that would offer e-class analysis capabilities outside of the e-graph (when we do not desire to maintain the analysis on the fly)? Would Extractor then not be a trivial user of Analyser?

[mwillsey]

Great question.

1. Extraction pre-dates the concept of Analyses. So it was (and still is) implemented as a manual pass over the e-graph. I hadn't considered that this is less efficient than the Analysis approach. In my experience, extraction has always been "fast enough".
2. We have discussed adding such a feature before. It would be nice to be able to "add" analyses at a later point. It just hasn't been implemented. A PR would be welcome if you are considering adding this feature!

[Bastacyclop]

I am going to implement both features (extraction that only computes when children have changed + analyses that can be added and removed), but it will be in my Scala port. If you want I can post a link to the Scala code once I got it to work.

[skius]

@Bastacyclop please link the Scala code if you get it working!

[Bastacyclop]

Hi @skius,
I have a working prototype, which I did not have time to polish yet.

1. An e-graph may contain multiple analyses that can be dynamically added or removed
2. An analysis may be a semilattice analysis (as in egg), or another type of analysis (e.g. semigroup analysis). An example of semigroup analysis would be counting represented programs up to a given size limit.
3. Instead of immediately making analyses on e-node creation or e-class merge, this is delayed until rebuilding. In retrospect, I am not sure whether this is a good choice or not. It made more sense to me in particular when thinking about semigroup analyses where "eager" make/merge is more costly.
4. Analyses may depend on other analyses. I did not have time to implement this properly since it requires bubbling analysis updates up the dependence paths. But I already have use-cases in mind.
5. The extractor is simply implemented as a smallest cost analysis

cc @mwillsey