Performance problems when using very large TypedDicts
- Dominant language
- Python
- Stars
- 15.6k
- Forks
- 1.8k
- Avg merge
- 12h 13m
- Merged PRs (30d)
- 52
Description
**Describe the bug**
Very large TypedDicts cause Pyright to be very slow. I've replaced `**kw: object` with `**kw: Unpack[Dicts]` where `Dicts` are various generated TypedDicts (the largest dict has 1442 parameters, but callers never set more than 20) in several parts of our codebase, and the time spent typechecking the project went up by 30%, from 37 to 48 seconds. Even worse, LSP is now hanging for several seconds when editing files that use classes referring to these large TypedDicts.
Deepseek found two performance bottlenecks when running such typechecking:
- The loop at https://github.com/microsoft/pyright/blob/7ddd3b121bf3421fd3e98ec4f3b38209e24c08d0/packages/pyright-internal/src/analyzer/typedDicts.ts#L957 does not have early braking when `isEquivalentToDict = false` is determined. In the case provided, the type outside the loop is `Never`, which means early-braking would happen even on the first iteration, which cuts the time from O(n^2) to O(n).
- The loop at https://github.com/microsoft/pyright/blob/30e847056d8aaf4044412e5fb606e43eb5301a07/packages/pyright-internal/src/analyzer/types.ts#L3915 is also an O(n^2) loop in normal cases, as each type added to the union has to be checked for uniqueness with every other type already inside the union. Pyright special-cases types of the form `Literal["str"]`, `Literal[1]`, and `Literal[Enum.ITEM]`, which means in many cases this is O(n). However, for TypedDicts, Pyright synthesizes the `update(__m: Iterable[tuple[, ]], /)` overload, where the type inside the `Iterable` is actually a union of all the possible `tuple[str, X]` types, which are not affected by this special casing.
**Code or Screenshots**
An example of a file that takes much longer to typecheck without the fixes is attached. On my machine the time to typecheck this went down from 3.3 seconds user time / 2.7 seconds CPU time, to 1.01 seconds / 0.7 seconds CPU time, which is a 70% improvement. This file is highly synthetic, so the gains are lower in most actual environments, but still. A version of this file with 2000 different fields takes **over two minutes** to typecheck, which is quite frankly absurd, and only 2 seconds with the fix.
[hetero_500.py](https://github.com/user-attachments/files/32214907/hetero_500.py)
**VS Code extension or command-line**
VSCode extension / CLI 1.1.412
Contributor guide
Research direction
Start with the loops linked in packages/pyright-internal/src/analyzer/typedDicts.ts around line 957 and types.ts around line 3915, then run type checking on the attached hetero_500.py example. Compare the baseline with large TypedDicts and confirm that type checking and LSP responsiveness no longer exhibit the reported quadratic slowdown, with relevant tests passing.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python, typescript
- Domain
- devtools, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 68/100