Comments (10)
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.
Related Issues (20)
- Randomly extract a RecExpr from a EGraph HOT 1
- Feature request: Add a test utility to ensure that none of rules are inferred from the rest of rules HOT 2
- How to extract the solutions several times sorted by astsize HOT 5
- Syntax for passing multiple arguments to condition HOT 1
- Mutable access to the EGraph in `Analysis::make` HOT 3
- How to implement complex rules for expression simplification? HOT 2
- How to define `rewrite` if I have no idea of how many variable in expression HOT 1
- It is possible to build egraph like Directed acyclic graph? HOT 3
- How to pretty-print an egrah HOT 1
- Explanations using `add_internal` and `union_trusted` HOT 2
- Is possible to use egg with my own parser as *input* instead of using text? HOT 4
- How to simplify multiple equations with the same variables? HOT 4
- Division by zero nitpick - docs HOT 1
- Where is the dicussion part HOT 1
- Loss of the discussions tab and its content HOT 2
- Question: Dealing with side effects/assignment HOT 4
- Map from `EGraph<L, _>` to `EGraph<L2, _>` HOT 1
- Avoid recursive rule applying during Runner::run() HOT 2
- Relaxing `'static` lifetime bounds? HOT 5
- How to access external data when making an analysis?
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from egg.