Quadratic type-checking time for functions with many statement-level calls

[MichaReiser]

ty exhibits quadratic behavior when a function contains many statement-level calls that repeatedly reference the same binding. This affects generated code such as large pyuic6/pyside6-uic setupUi methods.

Reported in #3969 (comment)

Reproducer

from pathlib import Path

N = 6000

Path("one_func.py").write_text(
    "def big() -> None:\n"
    "    s = 'abc'\n"
    + "    s.upper()\n" * N
)

ty check one_func.py --verbose
ty check many_funcs.py --verbose
ty check assignments.py --verbose

ty 0.0.59

Statement-level calls	Check time
500	143 ms
1,000	328 ms
1,500	642 ms
3,000	2.30 s
6,000	9.13 s

We don't observe the same slow-down for calls split across many functions or for calls in assignment expressions:

Case	Check time
One function	9.13 s
Split across functions	159 ms
Assignment RHS	179 ms

Cause

Codex:

The semantic index creates an IsNonTerminalCall predicate for every statement-level call so that calls returning Never can make subsequent code unreachable. Each predicate is also applied as a narrowing constraint to every live place.

Consequently, the binding for s accumulates an increasingly long chain of constraints. Resolving s in each subsequent call repeatedly evaluates and projects that chain, resulting in approximately 1 + 2 + … + N work.
A Callgrind profile of the 1,500-call case on current main confirms the hotspot:

• ~70% in place/binding resolution
• ~68% in narrow_type_by_constraint
• <1% in actual call inference
• ~6.0 billion instructions, compared with ~333 million for the assignment case

Assignment expressions are fast because ty only adds IsNonTerminalCall constraints for statement-level calls, not calls nested in an assignment RHS.

[MichaReiser]

Here a few PRs from when I worked on this myself, that might be worth looking at (@charliermarsh)

• [ty] Cache non-terminal call reachability prefixes ruff#26763
• [ty] Preserve terminal narrowing across branch merges ruff#26759
• [ty] Cache narrowing projections during inference ruff#26760

I also don't consider astral-sh/ruff#26775 on its own as a sufficient fix. It's a case where codex fixes precisely the case from the issue but fails to think ahead. While an optimization like astral-sh/ruff#26775 might be worth to reduce some work and reduce memory usage, a full fix for this issue must also work if the binding has narrowing or reachability constraints.

[charliermarsh]

Yup agreed, I commented the same thing in the revived version of that PR!

[npaolini2634]

Hi, I'm the one that posted the original issue that spawned this - #3969

You might already have all the info you need, but I'm running TY 0.0.59 and I just got another panic. Log's here in case they're useful:
ty Language Server - AFTER EXITTING WITH PANIC.log

[MichaReiser]

@npaolini2634 this sounds very different than this issue. Let's move this discussion to a new issue instead (makes it much easier to track and follow discussions)