Limiting rewrites? about egg HOT 10 CLOSED

You could indeed write guards on such an associativity rule. But associativity is a known hard problem in this context, and the name of the game is just managing explosion. Saturating something like this is going to be very tricky indeed.

Your best bet for limiting which rules apply is the scheduler API. egg uses the BackoffScheduler by default (which you can customize a fair bit). You can change the scheduler with the with_scheduler method of Runner.

from egg.

That makes sense. Would it make sense for me to add something along those lines to the math.rs test (since it is mentioned as examples of things)?

from egg.

I'm always happy to take patches! It is already using the BackoffScheduler, but if you can come up with something that the current math setup cannot do, it'd be great to have an example and a way to make it work.

from egg.

The tests for math.rs seem to be using a test runner that exits as soon as an equivalence is found. So writing a test there like "(* x 0)" => "0" terminates really quickly (since it is found after the first iteration). But, when I use this attempting to reach saturation it loops forever. Is there a way to write the test and say that it should reach saturation?

I also noticed that the definition of is_const relies on finding an equivalent constant node in the graph. Is there a reason it couldn't use the analysis? It seems like that would avoid the search through all possible substitutions, wouldn't it?

from egg.

re: is_const, yes you could use an analysis! But it only scans the e-nodes in one e-class, which is pretty quick.

You'll have to just write your own test function if you don't want to use the test_fn macro. You can check the stop_reason field on Runner to see if it saturated.

from egg.

Oh. I think I see what I missed. The ConstantFold is pruning the non-leaf (non-constant) nodes. I think this answers many of my questions about the interaction between the ConstantFold pass and the rules like (* x 0) as well as (probably) solves my problem.

That makes sense. I took a stab at it, and it looks like the pruning is actually preventing the blow-up here. Specifically:

After applying associativity to find (* x 0) = 0, the pruning rules kick in and delete the other nodes. Something similar happens with (* x 1) = x which rewrites: (* x 1) => (* (x 1) 1) => (* x (* 1 1)) => (*x 1).

An somewhat related thought -- would it make sense to take advantage of pruning within the implementation of is_const? It seems like instead of using iter.all(...) it could check just the first element of the iterator and then ensure there are no more elements. The pruning should have eliminated the non-constant nodes).

Poking at that looks like it reduces the L2 Accesses in the benchmarks by 20% to 40% in the math cases.

from egg.

Ah that's a nice catch. I'd be a little nervous to rely on it though, since if the behavior changes this would be a tricky one to see.

Also, it's an any, not an all. Is that what you were referring to?

from egg.

Ah yeah, that's the one. My experiment changed it to:

let iter = egraph[subst[var]].nodes.iter();
if let Some(n) = iter.next() {
  matches!(n, Math::Constant(..))
} else {
  false
}

I could try using the analysis data -- it seems like that would be cleaner than relying on the pruning behavior, and should offer a similar reduction in L2 Access since it doesn't need to search through the iterator.

from egg.

Yeah, the analysis should be easier. Not sure why i didn't do that initially. Something like:
egraph[subst[var]].data.is_some()

from egg.

Closing for now, feel free to re-open!

from egg.