Conversation
Your org has enabled the Graphite merge queue for merging into mainAdd the label “merge” to the PR and Graphite will automatically add it to the merge queue when it’s ready to merge. Or use the label “hotfix” to add to the merge queue as a hot fix. You must have a Graphite account and log in to Graphite in order to use the merge queue. Sign up using this link. |
57f6ca1 to
94c3001
Compare
CodSpeed Performance ReportMerging #3238 will not alter performanceComparing Summary
|
94c3001 to
ece1ff3
Compare
4b0951e to
a4f9ee3
Compare
658e5d5 to
ae657bc
Compare
a4f9ee3 to
ba99160
Compare
ae657bc to
857840a
Compare
ba99160 to
842eccc
Compare
6bb0206 to
9bdf934
Compare
504c906 to
1644851
Compare
b54237e to
3b12589
Compare
|
@Boshen Can you read the first comment on this PR? I was wondering how much should I improve the performance to make it acceptable. |
|
@rzvxa Instead of doing the check inside the rule, are you able to mark the statement as unreachable during the cfg building phase inside semantic builder? For example add any of the following: pub struct Semantic<'a> {
pub unreachable: Vec<Span>, // All the unreachable spans
}In the rule you just print out these spans in one go - a rule with only one line of code lol. Or: pub struct SemanticNode<'a> {
pub unreachable: bool
}Think outside of the box, we have the whole compiler pipeline, we can precompute a lot of stuff! |
Doesn't adding this to the semantic mean we have to pay for this cost in places where it isn't necessary? Not to mention the amount of code we have to add to our semantic builder to compute and determine the reachability. I'm sure with this much performance regression even I wouldn't like my current results (and if it was my project I wouldn't allow it to merge) But having it in semantic doesn't feel right to me either. Maybe we can achieve a better performance by rewriting the rule to use For example if we visit an infinite loop we know for sure everything after this loop is unreachable, But in my current implementation we can't remember that information between nodes so we get to do it all over again. |
|
Yes, a |
|
In TypeScript, it marks nodes as unreachable via |
|
Maybe there's a bug somewhere? Or maybe you need to add some cache to the visited nodes? 
|
We already have an unreachable instruction to mark the first unreachable block but it doesn't propagate and we use it to filter out the subgraph when walking through the flow, I assume they are doing all of our checks - if not more - to set these flags correctly. I'll give the typescript approach a read before making any major changes but I have a hunch that whatever approach we use to implement this rule it should get rid of our current redundant revisits either by running once or precomputing the information(which in of itself is another kind of run once happening in the core instead of linter crate). It all brings me to the question I was going to ask before seeing this comment. Considering that this information can be reused but comes at the cost of more memory and overhead for everything using the semantics, Do you think having it there is going to be better overall? |
I know we are revisiting nodes over and over since we can't memorize the information from our run on the previous nodes, That's why I hope we get a great boost after getting rid of them, if I'm correct it would be something like going from around |
|
The sad part is that all of our dfs paths are only 8% of the performance regression the other |
We'll eventually make cfg construction optional at some point. Regarding performance regression, I think we can accept around 10 - 15% given that we are doing a lot of work for cfg. |
Just to be clear do you mean it is acceptable if we keep it in the semantics or are you talking about this rule alone? |
Overall performance regression of 10 to 15%. We can keep the unreachable query in the linter rule if that's what you prefer, I was only suggesting that maybe it's better to precompute in the semantic builder. I'll let you make the decision 😁 |
0569841 to
dac177e
Compare
dac177e to
4548ad5
Compare
03ff002 to
ca3307c
Compare
306c912 to
3397176
Compare
ca3307c to
0478a0b
Compare
5faf0e9 to
0cf1b04
Compare
Merge activity
|
closes #621 [no-unreachable](https://github.com/eslint/eslint/blob/069aa680c78b8516b9a1b568519f1d01e74fb2a2/lib/rules/no-unreachable.js#L196) [oxlint-echosystem-ci result](https://github.com/rzvxa/oxlint-ecosystem-ci/actions/runs/9406195143/job/25909079029) This rule is done but since it is running for every possible statement and does quite a bit of work on them to determine whether it is 100% reachable or not; The performance in my opinion is kind of abysmal. I'll try to work it out, I know Biome does 2 types of checks to simplify the rule for some nodes, However, they have a lot more false negatives than our implementation. ##### Here is one example of those [false negatives](https://biomejs.dev/playground/?code=ZgB1AG4AYwB0AGkAbwBuACAAeAAoACkAIAB7ACAAZABvACAAewAgAGEAKAApADsAIAB9ACAAdwBoAGkAbABlACgAdAByAHUAZQApADsAIABiACgAKQA7ACAAfQA%3D) ------------- ### Update 1: I've benchmarked this rule using only the simplified reachability checks and it was around 5% faster, To be honest, it isn't much improvement especially considering that we can only use this check for a small portion of nodes and even that is accompanied by newly introduced checks which would lessen the amount of performance gain further. Most of the performance regression is because of allocations during our depth first search since we have to store both the visited and finished nodes which results in a bunch of rapid-fire allocations back to back. Currently, At the moment I don't have a great idea of how to improve it, We may have to implement our own graph to use arenas underneath. Given that this rule is the most extensive use case of control flow (It doesn't come with a limited scope similar to property and constructor rules already implemented) this performance drop might be reasonable to some extent. ------------ ### Update 2: I reworked my approach in 2 senses, First I used @Boshen's suggestion inspired by TypeScript and kept some of the reachability information in the basic block structure instead of calculating it on the fly. It is done by propagating the `Unreachable` edge and `Unreachable` instruction throughout subgraphs. This for sure helped with the performance but the next part is what never failed to amaze me, Going from something near `O(n!)` in the worst-case scenario to `O(n^2)` (in the worst-case scenario). By changing the approach instead of checking the reachability of each statement we do it in 3 paths; First, we do a path on the entire CFG and query all reachable but suspicious cases, and then we do another path on each of these suspicions subgraphs to determine the reachability with higher confidence. Finally, we iterate all of the appropriate nodes and check their reachability status according to the information collected in 2 previous paths. With these 2 this rule went from `-24%` to `~-2%`. This performance gain doesn't come for free though; It increases the likelihood of false positives/negatives, But as long as we are passing our `ecosystem-ci` it should be fine. We can always sacrifice some performance to check for edge cases if there are any. [new oxlint-echosystem-ci result](https://github.com/rzvxa/oxlint-ecosystem-ci/actions/runs/9490791181)
closes #621
no-unreachable
oxlint-echosystem-ci result
This rule is done but since it is running for every possible statement and does quite a bit of work on them to determine whether it is 100% reachable or not; The performance in my opinion is kind of abysmal.
I'll try to work it out, I know Biome does 2 types of checks to simplify the rule for some nodes, However, they have a lot more false negatives than our implementation.
Here is one example of those false negatives
Update 1:
I've benchmarked this rule using only the simplified reachability checks and it was around 5% faster, To be honest, it isn't much improvement especially considering that we can only use this check for a small portion of nodes and even that is accompanied by newly introduced checks which would lessen the amount of performance gain further.
Most of the performance regression is because of allocations during our depth first search since we have to store both the visited and finished nodes which results in a bunch of rapid-fire allocations back to back. Currently, At the moment I don't have a great idea of how to improve it, We may have to implement our own graph to use arenas underneath.
Given that this rule is the most extensive use case of control flow (It doesn't come with a limited scope similar to property and constructor rules already implemented) this performance drop might be reasonable to some extent.
Update 2:
I reworked my approach in 2 senses, First I used @Boshen's suggestion inspired by TypeScript and kept some of the reachability information in the basic block structure instead of calculating it on the fly. It is done by propagating the
Unreachableedge andUnreachableinstruction throughout subgraphs.This for sure helped with the performance but the next part is what never failed to amaze me, Going from something near
O(n!)in the worst-case scenario toO(n^2)(in the worst-case scenario). By changing the approach instead of checking the reachability of each statement we do it in 3 paths; First, we do a path on the entire CFG and query all reachable but suspicious cases, and then we do another path on each of these suspicions subgraphs to determine the reachability with higher confidence. Finally, we iterate all of the appropriate nodes and check their reachability status according to the information collected in 2 previous paths.With these 2 this rule went from
-24%to~-2%.This performance gain doesn't come for free though; It increases the likelihood of false positives/negatives, But as long as we are passing our
ecosystem-ciit should be fine. We can always sacrifice some performance to check for edge cases if there are any.new oxlint-echosystem-ci result