Faster substitute_facts #8200
Merged
Faster substitute_facts #8200
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Deletes a bunch of code and speeds up lowering time of local laplacian with 20 pyramid levels by ~2.5%
It was O(n) for n facts. This makes it O(log(n)) This was particularly bad for pipelines with lots of inputs or outputs, because those pipelines have lots of asserts, which make for lots of facts to substitute in. Speeds up lowering of local laplacian with 20 pyramid levels (which has only one input and one output) by 1.09x Speeds up lowering of the adams 2019 cost model training pipeline (lots of weight inputs and lots outputs due to derivatives) by 1.5x Speeds up resnet50 (tons of weight inputs) lowering by 7.3x!
…o abadams/faster_substitute_facts
…o abadams/faster_substitute_facts
…o abadams/faster_substitute_facts
Member
Author
|
Ready for review |
steven-johnson
approved these changes
Apr 18, 2024
| std::vector<const Variable *> pop_list; | ||
| std::vector<const Variable *> bounds_pop_list; | ||
| std::vector<Expr> truths, falsehoods; | ||
| std::set<Expr, IRDeepCompare> truths, falsehoods; |
Contributor
There was a problem hiding this comment.
Have you considered unordered_set?
Member
Author
There was a problem hiding this comment.
comparing Exprs for < is actually a lot cheaper than hashing them, because you can early out as soon as you find an IRNodeType that differs instead of having to descend to the bottom.
Contributor
There was a problem hiding this comment.
Might be worth putting that in a comment then :-)
Member
Author
There was a problem hiding this comment.
Meh, that was a bit of a guess. Nowhere in the compiler do we use unordered sets or maps with Expr keys, because we don't have a hash function. I'm just doing what we do everywhere else.
Member
Author
|
Failure unrelated (seems to be a performance flake). Ready for review. |
Member
Author
|
Oh oops, you already approved it. |
1 task
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
It was O(n) for n facts. This makes it O(log(n))
This was particularly bad for pipelines with lots of inputs or outputs,
because those pipelines have lots of asserts, which make for lots of
facts to substitute in.
Speeds up lowering of local laplacian with 20 pyramid levels (which has
only one input and one output) by 1.09x
Speeds up lowering of the adams 2019 cost model training pipeline (lots
of weight inputs and lots outputs due to derivatives) by 1.5x
Speeds up resnet50 (tons of weight inputs) lowering by 7.3x!