C++: reachableRecursive refactor for performance#1325
Merged
Conversation
Contributor
|
Is it possible to split this into a commit with the relocation followed by a commit with the substantive changes? |
Contributor
Author
|
Yes. I'll do that. |
This change only moves code around -- there are no changes to predicate bodies or signatures. The predicates that go in `ConstantExprs.Cached` after this change were already cached in the same stage or, in the case of the `aborting*` predicates, did not need to be cached. This is a fortunate consequence of how the mutual recursion between the predicates happens to work, and it's not going to be the case after the next commit.
The `reachable` predicate is large and slow to compute. It's part of a
mutual recursion that's non-linear, meaning it has a recursive call on
both sides of an `and`.
This change removes a part of the base case that has no effect on
recursive cases. The removed part is added back after the recursion has
finished.
Before, on Wireshark:
ControlFlowGraph::Cached::reachable#f .......... 20.8s (executed 9800 times)
ConstantExprs::successors_adapted#ff ........... 4.2s (executed 615 times)
ConstantExprs::potentiallyReturningFunction#f .. 3.9s (executed 9799 times)
ConstantExprs::possiblePredecessor#f ........... 2.9s (executed 788 times)
After, on Wireshark:
ConstantExprs::reachableRecursive#f ............ 13.2s (executed 9800 times)
ConstantExprs::successors_adapted#ff ........... 4.2s (executed 615 times)
ConstantExprs::potentiallyReturningFunction#f .. 4.3s (executed 9799 times)
ConstantExprs::possiblePredecessor#f ........... 2.6s (executed 788 times)
I've verified that this change doesn't change what's computed by
checking that the output of the following query is unchanged:
import cpp
import semmle.code.cpp.controlflow.internal.ConstantExprs
select
strictcount(ControlFlowNode n | reachable(n)) as reachable,
strictcount(ControlFlowNode n1, ControlFlowNode n2 | n2 = n1.getASuccessor()) as edges,
strictcount(FunctionCall c | aborting(c)) as abortingCall,
strictcount(Function f | abortingFunction(f)) as abortingFunction
Contributor
Author
|
Done. I also moved |
rdmarsh2
approved these changes
May 16, 2019
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
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
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.
Reviewers, sorry for the long diff. The only code changes are in the three predicates that start with
reachable. See the commit message for all the details.