mypy_primer results

No ecosystem changes detected ✅

I'll review tomorrow. Can you add a log how many times we end up reparsing an ast and do a cold run on some project to see if we see any reparses to validate our assumption that this shouldn't happen?

CodSpeed Performance Report

Merging #18482 will degrade performances by 4.43%

_{Comparing ibraheem/ast-node-gc (347934a) with main (76d9009)}

Summary

⚡ 1 improvements
❌ 1 regressions
✅ 32 untouched benchmarks

⚠️ Please fix the performance issues or acknowledge them on CodSpeed.

Benchmarks breakdown

The incremental performance regression is expected. I'm not sure if we want less eager garbage collection for the LSP or if the initial hit is fine, and we instead try to keep recently reparsed ASTs around on subsequent runs?

The cold check performance regression is pretty minor (~3% both on codspeed and locally on mypy_primer runs) even with the extra AST traversal.

Thanks for working on this! I'm going to let @MichaReiser handle review :)

I'm curious about the new NodeIndex bit. Is the entire purpose of that so that we can use it in AstNodeRef, given we can no longer ensure a pointer into the AST will remain valid? Or are there other reasons we need it?

I'm curious about the new NodeIndex bit. Is the entire purpose of that so that we can use it in AstNodeRef, given we can no longer ensure a pointer into the AST will remain valid? Or are there other reasons we need it?

AstNodeRef could still store a pointer to the AST, the difference is that it would have to store a weak pointer to the module (a strong reference would prevent garbage collection) and validate that reference before access. The problem comes when the module is garbage collected — we have to update the pointer to be into the new reparsed module. This has two problems:

• We need a way to mutate the AstNodeRef, which is tricky and probably requires it being a Arc<Mutex<_>> or similar.
• We have to traverse the entire AST to update every node that is accessed.

Creating a flat index of the AST upfront allow us to avoid both of those, and AstNodeRef becomes a simple index into the flat AST, which will remain stable even across garbage collection cycles within the same revision.

The ty-benchmark results match the 3% regression on Codspeed.

black (cold)
Benchmark 1: /home/ibraheem/dev/astral/ruff/target/profiling/ty-new
  Time (mean ± σ):      56.9 ms ±   1.4 ms    [User: 290.4 ms, System: 74.9 ms]
  Range (min … max):    53.1 ms …  59.9 ms    51 runs
 
Benchmark 2: /home/ibraheem/dev/astral/ruff/target/profiling/ty-old
  Time (mean ± σ):      55.8 ms ±   1.4 ms    [User: 281.9 ms, System: 72.1 ms]
  Range (min … max):    52.1 ms …  59.0 ms    52 runs
 
Summary
  /home/ibraheem/dev/astral/ruff/target/profiling/ty-old ran
    1.02 ± 0.04 times faster than /home/ibraheem/dev/astral/ruff/target/profiling/ty-new

jinja (cold)
Benchmark 1: /home/ibraheem/dev/astral/ruff/target/profiling/ty-new
  Time (mean ± σ):      43.6 ms ±   1.6 ms    [User: 266.0 ms, System: 65.8 ms]
  Range (min … max):    40.7 ms …  47.5 ms    65 runs
 
 
Benchmark 2: /home/ibraheem/dev/astral/ruff/target/profiling/ty-old
  Time (mean ± σ):      41.7 ms ±   1.5 ms    [User: 259.7 ms, System: 62.9 ms]
  Range (min … max):    39.0 ms …  45.7 ms    74 runs
 
Summary
  /home/ibraheem/dev/astral/ruff/target/profiling/ty-old ran
    1.05 ± 0.05 times faster than /home/ibraheem/dev/astral/ruff/target/profiling/ty-new

isort (cold)
Benchmark 1: /home/ibraheem/dev/astral/ruff/target/profiling/ty-new
  Time (mean ± σ):      51.1 ms ±   2.5 ms    [User: 201.0 ms, System: 45.3 ms]
  Range (min … max):    46.1 ms …  57.0 ms    56 runs
 
 
Benchmark 2: /home/ibraheem/dev/astral/ruff/target/profiling/ty-old
  Time (mean ± σ):      49.5 ms ±   2.4 ms    [User: 197.4 ms, System: 45.2 ms]
  Range (min … max):    42.9 ms …  56.7 ms    62 runs

Summary
  /home/ibraheem/dev/astral/ruff/target/profiling/ty-old ran
    1.03 ± 0.07 times faster than /home/ibraheem/dev/astral/ruff/target/profiling/ty-new

Given that the regression is quite minor I'm inclined to get this merged.

I spent some time trying to assign indices in the parser but it turned out to be non-trivial. The parser is recursive-descendant and we want to assign indices in source-order, so we run into problems where the parent node depends on the result of the recursion, so we don't know whether or not to claim an outer index before parsing the inner nodes. I think we would end up having to do mini-traversals to adjust the children indices — it's much easier to do this in a separate pass. If the parser also collected the nodes then it could do a simple pass over those and assign the indices then, but that could also be addressed in a future PR.

I also ran on a number of projects and was unable to trigger a reparse within a revision, I added some logs in case that ever happens.

ruff-ecosystem results

Linter (stable)

✅ ecosystem check detected no linter changes.

Linter (preview)

✅ ecosystem check detected no linter changes.

Formatter (stable)

✅ ecosystem check detected no format changes.

Formatter (preview)

✅ ecosystem check detected no format changes.

The parser is recursive-descendant and we want to assign indices in source-order, so we run into problems where the parent node depends on the result of the recursion, so we don't know whether or not to claim an outer index before parsing the inner nodes

Just trying to understand this better. Can you share a specific instance of this?

The main thing that I find slightly annoying is that NodeId isn't Copy because it's an AtomicU32. This is obviously not the end of the world but it would be nice if it could be avoided.

Just trying to understand this better. Can you share a specific instance of this?

In parse_expression_list for example, we first parse the inner expression (which will increment the index), and then we conditionally wrap it in a ExprTuple node, which should have a lower index. Generally we would claim the parent index before recursing, but the conditional part makes this tricky.

the conditional part makes this tricky

Curious - would there be negative consequences to skipping an index in some scenarios?

Curious - would there be negative consequences to skipping an index in some scenarios?

Right now all indices are set strictly monotonic, so we can use a simple Box<[Node]> for the flat index, where each node's index matches its position in the list. If assigning indices in the parser means we have to switch to using a HashMap, or insert dummy nodes in the list, I'm not sure it's worth it.

Could we update the index when wrapping the node in a tuple (it may require a traversal of the inner node)

We could, but I guess I don't really see the benefit of doing that. Collecting the nodes as part of parsing would have a similar problem I think (we'd have to insert parent nodes into the middle of the list before it's children). The separate pass is much simpler and doesn't seem to impact performance noticeably.

Could we increase the index non-monotonically during parsing and then remove the gaps after the parsing is done? Or, would that be equivalent to visiting the parsed tree at the end to assign the index?

I also ran on a number of projects and was unable to trigger a reparse within a revision, I added some logs in case that ever happens.

Just double checking, did you do this check with a release build?

I explored a number of options here:

• Integrating the AST traversal into the semantic index. Unfortunately this does not work because the flat AST index is directly tied (through pointers) to a given ParsedModuleRef, while SemanticIndex does not hold on to a specific ParsedModuleRef instance. The SemanticIndex is transparent to the current instance of the AST, which is it now uses indices to reference nodes.
• Similarly, the node_index field being on the AST nodes directly is important. Storing a lookup map in SemanticIndex would be tricky for the reasons above — we don't want SemanticIndex to rely on any AST pointers, only indices.
• Removing the atomics from NodeIndex and adding a mutable visitor. This doesn't work because we hold on to immutable references to the nodes while traversing the tree, to form the flat index.

I think the current solution, where the flat index is created and managed directly by the ParsedModule and AST node indices are stored directly on the AST instance, makes the most sense and is easiest to reason about. The only future change I can see is if the node indices and collection are initialized even earlier by the parser, but I'm not sure that complexity is worth it (as I previously mentioned).

Just noticed this had been merged after I made the alpha-10 release. I think a 20-30% peak memory reduction is worth noting for users! So in future I think we could leave off the internal label on such a PR.

This is awesome!