Repository navigation
Mypy stuck with polynomial using NumPy #14978
Description
Bug Report
The original bug report is optuna/optuna#4404.
I tried to make a minimal reproducible example and found that checking the following code with the latest mypy takes about 1 minute.
To Reproduce
import numpy as np
from typing import Any
x: np.ndarray[Any, np.dtype[np.floating]] = np.asarray([1, 2, 3])
1 + x * (1 + x * (1 / 2 + x * (1 / 6 + x * (1 / 24 + x / 120))))Adding terms as follows seems to increase execution time exponentially.
1 + x * (1 + x * (1 / 2 + x * (1 / 6 + x * (1 / 24 + x * (1 / 120 + x / 720)))))Expected Behavior
The execution takes a few seconds.
Actual Behavior
$ time mypy exp.py Success: no issues found in 1 source file real 1m17.655s user 0m55.657s sys 0m0.892s
Your Environment
- Mypy version used: 1.1.1
- Mypy command-line flags: No flags
- Mypy configuration options from mypy.ini (and other config files): No configs
- Python version used: 3.9.4
Activity
sterliakov commented on Apr 22, 2025
Minimal repro without generics and third-party deps:
This takes 6 s with compiled mypy 1.15.0. Adding one more term increases runtime to 18 s. The dependency (time vs number of terms) is $T \approx 3^N$ after 7-8 terms. For every relevant overload signature (3 out of 5 here), we accept all arguments. When we have 10 such overloads nested, we accept the "leaf" nodes 0 and 1 $3^{10} \approx 60,000$ times.
np.ndarray.__mul__ is an overload with 17 variants, 9 of which match NDArray[np.floating] argument, so it grows even faster.
Use cache for OpExpr (python#19523)