Skip to content

Optimise overload consistency checks for large numbers of literal-containing overloads#21218

Open
pelson wants to merge 3 commits intopython:masterfrom
pelson:feature/poly-complexity-for-override-checking
Open

Optimise overload consistency checks for large numbers of literal-containing overloads#21218
pelson wants to merge 3 commits intopython:masterfrom
pelson:feature/poly-complexity-for-override-checking

Conversation

@pelson
Copy link
Copy Markdown

@pelson pelson commented Apr 14, 2026

Fixes #10004

Introduce an optimisation to reduce the number of calls to (the expensive) overload_can_never_match within the inner (O(N^2)) loop of check_overlapping_overloads in the case where the overloads contain literals.

The approach is to track all exclusively literal argument types, and to be able to quickly determine if two signatures can't possibly overlap.

For example, given:

@overload
def get(item: Literal["width"], default: int | None) -> int: ...
@overload
def get(item: Literal["height"], default: int | None) -> int: ...
@overload
def get(item: Literal["name"], default: str | None) -> str: ...
@overload
def get(item: str, default: str | None) -> str: ...
# ... many more

We can know by looking at the literals alone that there are no overlapping overloads, so the expensive pairwise check is skipped except for the last override. When the optimisation doesn't apply, we fall back to the existing (and complete) logic.

Please note that I have used Claude to help me find the key parts to change, and to help with the test validation. That said, this was a significant effort on my part to produce something that was tightly scoped and consistent with the approach I saw in checker.py.

In terms of performance:

n overloads master new
500 13.9s 4.2s
1000 48.7s 4.8s
2000 - 7.0s
4000 - 17.2s
8000 - 56.1s
Script to compute the runtime

Here is the script I used to compute the above runtime (fully Claude generated)

"""Benchmark mypy on N distinct Literal overloads."""
import sys
import os
import tempfile
import time

def generate(n: int, workdir: str) -> tuple[str, str]:
    pkgdir = os.path.join(workdir, f"pkg_{n}")
    os.makedirs(pkgdir, exist_ok=True)
    rt = ["str", "int", "float"]
    lines = ["import typing", "@typing.overload"]
    for i in range(n):
        lines.append(f"def get_param(param: typing.Literal['overload_{i}_{rt[i%3]}']) -> {rt[i%3]}: ...")
        if i < n - 1:
            lines.append("@typing.overload")
    lines.append("def get_param(param: str) -> object: ...")
    with open(os.path.join(pkgdir, "__init__.pyi"), "w") as f:
        f.write("\n".join(lines))
    open(os.path.join(pkgdir, "py.typed"), "w").close()

    script = os.path.join(workdir, f"script_{n}.py")
    with open(script, "w") as f:
        f.write(f"import sys\n")
        f.write(f"sys.path.insert(0, {repr(pkgdir + '/..')})\n")
        f.write(f"from pkg_{n} import get_param\n")
        f.write(f"x = get_param('overload_0_str')\n")
    cache = os.path.join(workdir, f"cache_{n}")
    return script, cache

def bench(n: int, workdir: str) -> float:
    from mypy import api as mypy_api
    script, cache = generate(n, workdir)
    args = [
        script,
        "--no-error-summary",
        f"--cache-dir={cache}",
        "--no-incremental",
        "--python-version=3.11",
    ]
    start = time.perf_counter()
    mypy_api.run(args)
    return time.perf_counter() - start

if __name__ == "__main__":
    sizes = list(map(int, sys.argv[1:])) if len(sys.argv) > 1 else [500, 1000]
    with tempfile.TemporaryDirectory() as workdir:
        for n in sizes:
            t = bench(n, workdir)
            print(f"n={n:6d}: {t:.2f}s")
            sys.stdout.flush()

I had also prototyped an algorithmic simplification to reduce the O(N^2) pairwise search in the case where there are many literals of the same type. This did have a reduction in the runtime, but it was not sufficiently large to justify the additional complexity, and I consider the implementation here to strike a good balance between the two.

…n^2) consistency check. Add a fast-path at the top of the inner loop.
@pelson pelson force-pushed the feature/poly-complexity-for-override-checking branch from bbac93f to 8125e31 Compare April 14, 2026 06:09
@github-actions

This comment has been minimized.

…ents

build_literal_fingerprint included optional arguments (ARG_OPT / ARG_NAMED_OPT) in the fingerprint used to detect disjoint overloads.
When two overloads differed only in an optional Literal arg (e.g. as_index: Literal[True] vs Literal[False]), the fast-path treated them as mutually exclusive and skipped the full overlap check - even though a caller can omit the argument entirely, matching both overloads through their other arguments.

Fix by only fingerprinting required arguments (ARG_POS and ARG_NAMED).
Optional arguments can always be omitted by the caller, so they can never prove two overloads are disjoint.

The real-world symptom was pandas-stubs gaining spurious unused-ignore errors: overloads that master correctly flagged as overlapping were silently skipped by the fast-path, making existing type: ignore redundant.
@pelson
Copy link
Copy Markdown
Author

pelson commented Apr 14, 2026

Diff from mypy_primer, showing the effect of this PR on open source code:

pandas-stubs (https://github.com/pandas-dev/pandas-stubs)
+ pandas-stubs/core/frame.pyi:1277: error: Unused "type: ignore" comment  [unused-ignore]
+ pandas-stubs/core/frame.pyi:1289: error: Unused "type: ignore" comment  [unused-ignore]

This was a genuine issue - there was no existing test coverage of the case where optional arguments overlapped (e.g. def f(x: int, as_string: Literal[True] = ...) -> str and def f(x: int, as_string: Literal[False] = ...) -> int)

Note that the test that I added to cover this is also highlighting a problem with the Flipping the order of overloads will fix this error message, which is clearly wrong in the added test case. This is the behaviour on master, and not introduced by this change (issue to be opened).

@github-actions
Copy link
Copy Markdown
Contributor

According to mypy_primer, this change doesn't affect type check results on a corpus of open source code. ✅

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Polynomial time-complexity of typing.overload

1 participant