Severe performance degradation with lots of constrained type variables in a generic class

[bzoracler]

Bug Report, To Reproduce, and Actual Behaviour

Mypy runs noticeably slower when analysing a class created from @dataclass or @dataclass_transform(), if the class is parameterised by constrained type variables. The increase in analysis time itself increases the more constrained type variables are added.

Upper-bounded type variables don't suffer this problem.

See mypy Playground, which fails with exit code 500. It isn't necessary to add fields on the class body, although it hits the performance problem with less type variables if you do. The snippet is roughly:

from typing_extensions import TypeVar, Generic
from dataclasses import dataclass

# Constrained
T1 = TypeVar("T1", int, None)
T2 = TypeVar("T2", int, None)
...
T20 = TypeVar("T20", int, None)

@dataclass
class A(Generic[T1, T2, ..., T20]):
    pass

Expected Behavior

Is it sensible to expect performance to be similar to upper-bounded type variables?

Your Environment

• Mypy version used: 1.17.1
• Python version used: 3.11, 3.12

[sterliakov]

We check function bodies once for every combination of constraints (cross product) of distinct variables in its signature, so current algorithm will be exponentially slower than bound type variables. Not sure what's going on with dataclasses, though.

20 constrained type variables is something extremely uncommon, and 10 variables are checked quite quickly, so I think this isn't something of high priority. Do you have a real use case?

[sterliakov]

Ah, okay, nothing dataclassy, just one method is enough for similar performance degradation:

class A(Generic[
    T1, T2, T3, T4, T5, 
    T6, T7, T8, T9, T10,
    T11, T12, T13, T14, T15,
    # T16, T17, T18, T19, T20
]):
    def foo(
        self,
        t1: T1,
        t2: T2,
        t3: T3,
        t4: T4,
        t5: T5,
        t6: T6,
        t7: T7,
        t8: T8,
        t9: T9,
        t10: T10,
        t11: T11,
        t12: T12,
        t13: T13,
        t14: T14,
        t15: T15,
        # t16: T16,
        # t17: T17,
        # t18: T18,
        # t19: T19,
        # t20: T20,
    ) -> None:
        pass

[bzoracler]

Do you have a real use case?

Yes, this is for writing stubs for a code base which tends to pass a lot of values around in an attribute holder (think something like the parsed result of mypy's command-line options). I wanted to use constrained (not bound) type variables to model the values, because broadly speaking,

class AttributesHolder[T1: (Literal["value"] | SomeValueType, None) = None]:
    var1: T1
    def __init__(self, var1: T1 = ...) -> None: ...

instance variables on instances of AttributesHolder may be mutated back-and-forth between non-None types, but never from None to non-None or vice-versa (therefore a bound to a union with None doesn't really work).

cross product

Ah, that explains it - thank you! I'll leave this issue open in case other similar use cases pop up in the future.

[A5rocks]

Unfortunately I don't think it's possible to improve this algorithm. Other type checkers may have better performance because they convert constraints to a bound of unions, but that's not a valid transformation.

[JelleZijlstra]

If this happens for dataclasses, that likely means we're running the check on the generated methods (__init__ and __replace__, I assume). So maybe we can just not run this exponential type check on those generated methods?

[sterliakov]

We need to check superclass compatibility anyway (yes, it matters for generated methods), and we do that on expanded signatures. A lot of time (>40% in my print(time.time())-grade bench on interpreted mypy) is actually spent generating the signatures (creating a bunch of copies of types and nodes), and we still need that step.

Sorry, my bad. It is indeed a later step, we might be able to skip check_func_def altogether for plugin-generated methods!

[sterliakov]

We could optimize for some narrow cases, though, like "if the containing info only inherits from object and the method name doesn't start with __" - that might make general case a little bit slower, but offer a huge win for trivial cases like this.