Repository navigation
perf(python): usage extraction climbs every ancestor per identifier, cubic in expression depth #2417
Description
Version
built from source, main @ 2278498 (v0.11.0-186)
Platform
Linux (x64)
Install channel
Built from source
Binary variant
standard
What happened, and what did you expect?
For nearly every Python identifier, handle_usages (internal/cbm/extract_usages.c:2712) and record_lexical_binding (:2239) ask lexical_ancestor_kind (:1883) for a global/nonlocal ancestor, and usage_lexical_scope_id_for_node (:1808) asks python_default_value_reference (:1782) whether the name sits in a parameter default. Each check climbs toward the root with ts_node_parent, which itself descends from the root on every step, so an expression N terms deep costs O(N³). One long arithmetic expression is enough to stall indexing: sympy 1.14's polys/numberfields/resolvent_lookup.py (40 KB) spends about 8.7 s in the definitions pass.
On error-free trees the fix climbs the walk's occurrence cursor instead (O(1) per hop, as #2352 did for ReScript). For global/nonlocal it takes one parent step, since the grammar makes those names direct children of the statement. Trees with errors keep today's climb, and the graph is byte-identical on 8 corpora.
Reproduction
Smallest repro: a one-file repo with x = 1, c0 = 0 … c49 = 49, then r = c0*x + c1*x + … with N terms (term i is c{i % 50}*x).
| Linux x86_64, 32 logical CPUs, GCC 16 | main | fixed |
|---|---|---|
| Definitions pass, generated file, N = 1000 / 2000 | 16.8 s / unfinished at 90 s | 40 / 150 ms |
Definitions pass, sympy resolvent_lookup.py alone |
8.7-8.8 s | 53-54 ms |
parallel_extract median, 823 / 2063 ordinary .py files |
1.54 / 4.75 s | 1.15 / 3.58 s |
Logs
Diagnostics trajectory (memory / performance / leak issues)
Not a memory problem: CPU time in the definitions pass of one index run.
Project scale (if relevant)
No response
Confirmations
- I searched existing issues and this is not a duplicate.
- My reproduction uses shareable code (a dummy snippet or a public OSS repository), not proprietary code.
Activity
DeusData commentedon Oct 19, 2026
Thank you for the generated-depth and real-file measurements, and for reporting graph-equivalence controls. The ancestor-walk cost is clearly scoped in the report. The proposed cursor change still needs review; no verified fix status is added by this triage.
DeusData commentedon Oct 25, 2026
Thank you for your patience. The occurrence-cursor change and graph-equivalence evidence still need maintainer review for the deep Python expression case. Sorry for the delay; I’ll follow up soon.
DeusData commentedon Oct 29, 2026
Fixed on main by #2419 (merge commit d807b1e): Python usage extraction no longer climbs every ancestor per identifier. On a generated file with one 1,500-term expression the definitions pass went from 53 s to 81 ms, the Python 3.14 standard library indexes 41 percent faster, and the graph is byte-identical on django, the standard library and its email package. Thank you, @Fieldnote-Echo, for the report and the fix!