Latest Results
[ty] Bound loop-header analysis for large loops (#24972)
## Summary
The intent of this change is to fix the regression we've seen isort
since the Beta (see: https://github.com/astral-sh/ty/issues/3023):
The loop control-flow work made exact loop-header reachability and type
inference too expensive on very large real-world loops, as in isort’s
`isort/parse.py` and `isort/core.py`. The problematic shape is not super
interesting -- roughly:
```python
def parse(items, opt0, opt1, opt2, ...):
index = 0
state = ""
while index < len(items):
line = items[index]
index += 1
if opt0:
state = line
continue
if opt1:
state = state.strip()
if opt2:
while ...:
state = ...
return state
```
So there's a large graph, with many loop-header places, but caching
doesn't seem to help much because the work is spread across many places.
This PR keeps exact loop-header analysis for smaller loops, but bounds
it for large loop headers. If a loop exceeds the limit, we fall back to
an ambiguous reachability/type result instead of expanding every
loop-back binding/state.
Compared to main, this gets isort back to beta-era performance:
| Project | Beta | charlie/reachability-cache | This branch |
| --- | ---: | ---: | ---: |
| isort | 47.7ms +/- 3.7ms | 405.4ms +/- 10.5ms | 52.9ms +/- 1.8ms |
| PyTorch | 1.183s +/- 0.114s | 1.218s +/- 0.037s | 1.192s +/- 0.034s |
Closes https://github.com/astral-sh/ty/issues/3023. Latest Branches
0%
charlie/reachability-overload 0%
0%
charlie/loop-constraints-test © 2026 CodSpeed Technology