Use separate structs for expression and statement tracking#6351
Use separate structs for expression and statement tracking#6351charliermarsh merged 2 commits intomainfrom
Conversation
2a0c25b to
30c42ef
Compare
PR Check ResultsEcosystem✅ ecosystem check detected no changes. BenchmarkLinuxWindows |
30c42ef to
9b3216b
Compare
|
|
||
| /// An [`Expr`] AST node in a program, along with a pointer to its parent expression (if any). | ||
| #[derive(Debug)] | ||
| struct Expression<'a> { |
There was a problem hiding this comment.
The name here will conflict with Expr if we go ahead and rename it to Expression.
Maybe ExpressionWithParent. The name doesn't seem as important as it is an internal type.
| #[derive(Debug, Default)] | ||
| pub struct Statements<'a> { | ||
| nodes: IndexVec<StatementId, Statement<'a>>, | ||
| node_to_id: FxHashMap<RefEquality<'a, Stmt>, StatementId>, |
There was a problem hiding this comment.
Could we remove RefEquality if we use a TextRange here?
There was a problem hiding this comment.
I think so... I'll do this separately.
| } | ||
|
|
||
| /// Return the parent of the given statement. | ||
| pub fn parent(&self, statement: &'a Stmt) -> Option<&'a Stmt> { |
There was a problem hiding this comment.
Nit: The parent and parent_id methods are asymetric in that one accepts a StatementId and the other Stmt. Are we back to statement_parent 😆 ? Or resolve_parent or require two steps: statement_id(stmt) and then call parent?
There was a problem hiding this comment.
Haha. I will fix this in a follow-up since this API already exists on Nodes (now removed).
| impl<'a> IndexMut<StatementId> for Statements<'a> { | ||
| #[inline] | ||
| fn index_mut(&mut self, index: StatementId) -> &mut Self::Output { | ||
| &mut self.nodes[index].node | ||
| } | ||
| } |
There was a problem hiding this comment.
Do we need the mutability (and indexing)? Same for Expr.
| /// The depth of this node in the tree. | ||
| depth: u32, |
There was a problem hiding this comment.
Is this a frequent operation or could we compute the depth by counting the ancestor chain`?
There was a problem hiding this comment.
I will revisit in a follow-up PR, since this already exists on Nodes (now removed).
## Summary When we iterate over the AST for analysis, we often process nodes in a "deferred" manner. For example, if we're analyzing a function, we push the function body onto a deferred stack, along with a snapshot of the current semantic model state. Later, when we analyze the body, we restore the semantic model state from the snapshot. This ensures that we know the correct scope, hierarchy of statement parents, etc., when we go to analyze the function body. Historically, we _haven't_ included the _expression_ hierarchy in the model snapshot -- so we track the current expression parents in the visitor, but we never save and restore them when processing deferred nodes. This can lead to subtle bugs, in that methods like `expr_parent()` aren't guaranteed to be correct, if you're in a deferred visitor. This PR migrates expression tracking to mirror statement tracking exactly. So we push all expressions onto an `IndexVec`, and include the current expression on the snapshot. This ensures that `expr_parent()` and related methods are "always correct" rather than "sometimes correct". There's a performance cost here, both at runtime and in terms of memory consumption (we now store an additional pointer for every expression). In my hyperfine testing, it's about a 1% performance decrease for all-rules on CPython (up to 533.8ms, from 528.3ms) and a 4% performance decrease for default-rules on CPython (up to 212ms, from 204ms). However... I think this is worth it given the incorrectness of our current approach. In the future, we may want to reconsider how we do these upward traversals (e.g., with something like a red-green tree). (**Note**: in #6351, the slowdown seems to be entirely removed.)
4499d39 to
a960cf5
Compare
c953b52 to
9121d7b
Compare
9121d7b to
d3e3c90
Compare
Discussed in #6351 (comment).
## Summary See discussion in #6351 (comment). We can remove `RefEquality` entirely and instead use a text offset for statement keys, since no two statements can start at the same text offset. ## Test Plan `cargo test`
## Summary When we iterate over the AST for analysis, we often process nodes in a "deferred" manner. For example, if we're analyzing a function, we push the function body onto a deferred stack, along with a snapshot of the current semantic model state. Later, when we analyze the body, we restore the semantic model state from the snapshot. This ensures that we know the correct scope, hierarchy of statement parents, etc., when we go to analyze the function body. Historically, we _haven't_ included the _expression_ hierarchy in the model snapshot -- so we track the current expression parents in the visitor, but we never save and restore them when processing deferred nodes. This can lead to subtle bugs, in that methods like `expr_parent()` aren't guaranteed to be correct, if you're in a deferred visitor. This PR migrates expression tracking to mirror statement tracking exactly. So we push all expressions onto an `IndexVec`, and include the current expression on the snapshot. This ensures that `expr_parent()` and related methods are "always correct" rather than "sometimes correct". There's a performance cost here, both at runtime and in terms of memory consumption (we now store an additional pointer for every expression). In my hyperfine testing, it's about a 1% performance decrease for all-rules on CPython (up to 533.8ms, from 528.3ms) and a 4% performance decrease for default-rules on CPython (up to 212ms, from 204ms). However... I think this is worth it given the incorrectness of our current approach. In the future, we may want to reconsider how we do these upward traversals (e.g., with something like a red-green tree). (**Note**: in astral-sh#6351, the slowdown seems to be entirely removed.)
…#6351) ## Summary This PR fixes the performance degradation introduced in astral-sh#6345. Instead of using the generic `Nodes` structs, we now use separate `Statement` and `Expression` structs. Importantly, we can avoid tracking a bunch of state for expressions that we need for parents: we don't need to track reference-to-ID pointers (we just have no use-case for this -- I'd actually like to remove this from statements too, but we need it for branch detection right now), we don't need to track depth, etc. In my testing, this entirely removes the regression on all-rules, and gets us down to 2ms slower on the default rules (as a crude hyperfine benchmark, so this is within margin of error IMO). No behavioral changes.
Discussed in astral-sh#6351 (comment).
## Summary See discussion in astral-sh#6351 (comment). We can remove `RefEquality` entirely and instead use a text offset for statement keys, since no two statements can start at the same text offset. ## Test Plan `cargo test`
Summary
This PR fixes the performance degradation introduced in #6345. Instead of using the generic
Nodesstructs, we now use separateStatementandExpressionstructs. Importantly, we can avoid tracking a bunch of state for expressions that we need for parents: we don't need to track reference-to-ID pointers (we just have no use-case for this -- I'd actually like to remove this from statements too, but we need it for branch detection right now), we don't need to track depth, etc.In my testing, this entirely removes the regression on all-rules, and gets us down to 2ms slower on the default rules (as a crude hyperfine benchmark, so this is within margin of error IMO).
No behavioral changes.