[red-knot] Reuse alist cells when possible#16408
Conversation
dcreager
added
internal
| #[derive(Debug, Eq, Ord, PartialEq, PartialOrd)] | ||
| pub struct List<K, V = ()> { |
There was a problem hiding this comment.
This is a major part of this PR, and I'm not sure whether I like all of the ramifications.
The gist is that we want to track whether a particular list cell is aliased (used more than once). To do that, we need to wrap the IndexVec IDs in this type that is not Clone or Copy. You must invoke the clone_list method below to make a copy of a list. It's still cheap — copying a u32 and setting a bool — but this lets us update the mutator methods below to take in owned List handles in cases where we want to try to reuse unaliased cells.
I like that this gives us type safety for tracking aliasing information that enables this optimization. I don't love that it has knock-on effects through the rest of the code...
| /// A snapshot of the definitions and constraints state at a particular point in control flow. | ||
| #[derive(Clone, Debug)] | ||
| #[derive(Debug)] | ||
| pub(super) struct FlowSnapshot { |
There was a problem hiding this comment.
...like here, where FlowSnapshot is no longer Clone...
| } | ||
|
|
||
| impl FlowSnapshot { | ||
| pub(super) fn clone(&self, narrowing_constraints: &mut NarrowingConstraintsBuilder) -> Self { |
There was a problem hiding this comment.
...at least not without threading extra state all of over the place!
* main: [red-knot] unify LoopState and saved_break_states (#16406) [`pylint`] Also reports `case np.nan`/`case math.nan` (`PLW0177`) (#16378) [FURB156] Do not consider docstring(s) (#16391) Use `is_none_or` in `stdlib-module-shadowing` (#16402) [red-knot] Upgrade salsa to include `AtomicPtr` perf improvement (#16398) [red-knot] Fix file watching for new non-project files (#16395) document MSRV policy (#16384) [red-knot] fix non-callable reporting for unions (#16387) bump MSRV to 1.83 (#16294) Avoid unnecessary info at non-trace server log level (#16389) Expand `ruff.configuration` to allow inline config (#16296) Start detecting version-related syntax errors in the parser (#16090)
|
Regardless of whether #16408 and #16311 pan out, this part is worth pulling out as a separate PR. Before, you had to define a new `IndexVec` index type for each type of association list you wanted to create. Now there's a single index type that's internal to the alist implementation, and you use `List<K, V>` to store a handle to a particular list. This also adds some property tests for the alist implementation.
|
I've tried a few variations of this, but the overhead of tracking when a cell is aliased is too high compared to the savings from being able to reuse cells, at least for the use case in #16311 |
1 participant
This is in support of #16311, and adds some additional tracking to the alist implementation so that we can tell when a cell is only used once. This lets us reuse and modify those cells in place when doing certain updates.
This also adds some property tests for alists, since I wasn't convinced that my small set of hand-coded examples were exercising all of the code paths.
I'm leaving this as draft for now, but want to get some CI and Codspeed feedback on it.