[red-knot] Add a benchmark involving realistic code that creates large unions

[AlexWaygood]

Code that creates large unions (explicitly or implicitly) is known to be hard for type checkers to analyze in a performant way. Both mypy and pyright have had lots of issues regarding performance for these, and both have implemented several optimizations to deal with them. We should add at least one benchmark (probably several) that measures how we do on this.

Common themes that come up in this area are:

• Unions involving Literal types (Literal[1, 2, 3] desugars to Literal[1] | Literal[1] | Literal[3] from the type checker's perspective, so "medium-sized Literal types" quickly end up creating huge unions)

• Enums. A similar issue to Literal types. If you have an enum like this:

  class A(enum.Enum):
      X = 1
      Y = 2
      Z = 3

  Then in some cases, x: A can desugar to x: Literal[A.X] | Literal[A.Y] | Literal[A.Z]

• Pydantic. Pydantic uses some big unions, and features in performance bug reports in both the mypy and pyright issue trackers.

• Unions involving protocols

• Unions involving recursive type aliases

• Unions involving TypedDicts

References

Here are some references that are worth looking at (and from which we might be able to derive benchmarks). The great thing about all of these is that they are performance issues that we know real users encountered when their type checker was checking real code. I've tried to exclude anything specific to recursive type aliases, since that feels somewhat out of scope for this issue:

Mypy

• Regression from 0.750 - Literal types cause significant slowdown python/mypy#9169
  • fixed-ish by:
    • Speed up make_simplified_union for Literal[string]s (issue #9169) python/mypy#9192
    • typeops: extend make_simplified_union fast path to enums python/mypy#9394
• mypy runs forever with colour-science python/mypy#12225
• (enum-related) Significant speed degradation from 0.931 to 0.941 python/mypy#12408
  • fixed-ish by Fix union simplification performance regression python/mypy#12519
• Speed up union simplification python/mypy#12526
  • linked PRs:
    • Further speed up union simplification python/mypy#12541
    • make_simplified_union: add caching and reduce allocations python/mypy#12659
• (enum-related) mypy 0.982 run 15 minutes (previous version needs only one minute) python/mypy#13821
  • fixed by subtypes: fast path for Union/Union subtype check python/mypy#14277
• (pydantic-related) mypy 0.990 is 1000x slow on pydantic codebase vs 0.982 python/mypy#14034
  • fixed by Fix performance in union subtyping python/mypy#15104

Pyright

• Bad performance with TypedDicts and unions microsoft/pyright#7617
  • Fixed by microsoft/pyright@aff916f
• !! Very slow performance for huge literals microsoft/pyright#7143
  • Fixed by Added additional performance enhancements specifically for large unio… microsoft/pyright#7154
• (pydantic-related) Look for performance improvements related to large unions microsoft/pyright#4781
  • Fixed by microsoft/pyright@c7ab804

[dangotbanned]

We recently added a TypedDict-heavy feature in altair.

Not sure if this helps as real-world examples, but sharing as red-knot came up during review

• feat: Adds ThemeConfig (TypedDict) vega/altair#3536 (comment)

mypy performance here has a lot of room for improvement

[hauntsaninja]

Nice! I'll add altair to mypy_primer. You may also be interested in python/mypy#17231 (comment) , I think it makes mypy significantly faster on your workload.