René's URL Explorer Experiment


Title: Polynomial time-complexity of typing.overload · Issue #10004 · python/mypy · GitHub

Open Graph Title: Polynomial time-complexity of typing.overload · Issue #10004 · python/mypy

X Title: Polynomial time-complexity of typing.overload · Issue #10004 · python/mypy

Description: Feature The time complexity of dealing with function overloads in mypy appears to be polynomial. Naively, it seems this is not a fundamental limit (I have no experience in static analysis to base this on), below is a log-log graph of num...

Open Graph Description: Feature The time complexity of dealing with function overloads in mypy appears to be polynomial. Naively, it seems this is not a fundamental limit (I have no experience in static analysis to base t...

X Description: Feature The time complexity of dealing with function overloads in mypy appears to be polynomial. Naively, it seems this is not a fundamental limit (I have no experience in static analysis to base t...

Opengraph URL: https://github.com/python/mypy/issues/10004

X: @github

direct link

Domain: github.com


Hey, it has json ld scripts:
{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Polynomial time-complexity of typing.overload","articleBody":"**Feature**\r\n\r\nThe time complexity of dealing with function overloads in mypy appears to be polynomial. Naively, it seems this is not a fundamental limit (I have no experience in static analysis to base this on), below is a log-log graph of number of overloads vs execution time:\r\n\r\n\r\n![Figure_1](https://user-images.githubusercontent.com/810663/106470862-4da36c00-64a1-11eb-85a4-dea04fc5f61b.png)\r\n\r\n\r\n\r\n\u003cdetails>\r\n \u003csummary>The data for the graph was generated with the following code:\u003c/summary>\r\n\r\n```\r\nimport json\r\nimport pathlib\r\nimport tempfile\r\nimport textwrap\r\nimport time\r\n\r\nfrom mypy import api\r\n\r\n\r\ndef generate_n_overloads(n: int, types=('str', 'int', 'float')) -> str:\r\n    result = ['import typing']\r\n\r\n    for name_count in range(n):\r\n        type_name = types[name_count % len(types)]\r\n        name = f'overload_{name_count}_{type_name}'\r\n        annotation = (\r\n            textwrap.dedent(f'''\r\n        @typing.overload\r\n        def get_param(param: typing.Literal['{name}']) -> {type_name}: ...\r\n        ''')\r\n        )\r\n        result.append(annotation)\r\n    return '\\n'.join(result)\r\n\r\n\r\ndef build_test_case(dest_dir: pathlib.Path, n_overloads: int) -> pathlib.Path:\r\n    pkg_dir = dest_dir / 'example_overloads_pkg'\r\n    pkg_dir.mkdir(exist_ok=True)\r\n    stubfile = pkg_dir / '__init__.pyi'\r\n    stubfile.write_text(generate_n_overloads(n_overloads))\r\n\r\n    pkg_file = pkg_dir / '__init__.py'\r\n    pkg_file.write_text('def get_param(param): ...')\r\n\r\n    test_script = dest_dir / 'script.py'\r\n    test_script.write_text(textwrap.dedent('''\r\n        from example_overloads_pkg import get_param\r\n        \r\n        get_param('overload_3_str').upper()  # Good\r\n        get_param('overload_2_float').upper()  # Bad\r\n    '''))\r\n    return test_script\r\n\r\n\r\nif __name__ == '__main__':\r\n    tmpdir = tempfile.TemporaryDirectory()\r\n\r\n    scale_times = {}\r\n    numbers_to_check = [16, 32, 64, 128, 256, 512, 1024]\r\n    # numbers_to_check = [16, 32, 64, 128, 256, 300, 400, 500, 600, 700, 800, 900, 1000, 1500, 2000, 2500, 3000, 4000, 5000, 6000, 8000, 10000]\r\n    for number_of_overloads in numbers_to_check:\r\n        print(f'Overload size: {number_of_overloads}')\r\n        test_script = build_test_case(pathlib.Path(tmpdir.name), number_of_overloads)\r\n        start = time.perf_counter()\r\n        result = api.run([str(test_script)])\r\n        end = time.perf_counter()\r\n        elapsed = end - start\r\n\r\n        print(' Time:', end - start)\r\n        if scale_times:\r\n            last_n = next(reversed(scale_times))\r\n            print(f\" Slowdown: x{elapsed / scale_times[last_n]:.2f}\")\r\n        scale_times[number_of_overloads] = elapsed\r\n\r\n    # Save the times to json for plotting/analysis.\r\n    with open('times.json', 'wt') as fh:\r\n        json.dump(scale_times, fh)\r\n\r\n```\r\n\r\nAnd the plot:\r\n\r\n```\r\nimport json\r\n\r\nimport matplotlib.pyplot as plt\r\nimport numpy as np\r\n\r\n\r\nwith open('times.json', 'rt') as fh:\r\n    times = json.load(fh)\r\n\r\nn_points, times = zip(*times.items())\r\n\r\nn_points = np.array(n_points, dtype=int)\r\ntimes = np.array(times)\r\nfit = np.polyfit(n_points, times, 2)\r\np = np.poly1d(fit)\r\n\r\nplt.title('Number of overloads vs execution time of mypy')\r\n\r\nplt.xscale('log')\r\nplt.yscale('log')\r\n\r\n\r\nplt.scatter(n_points, times)\r\nplt.xlabel('Number of overloads')\r\nplt.ylabel('Time to run mypy / seconds')\r\nplt.show()\r\n\r\n```\r\n\r\nThe full dataset (``times.json``):\r\n\r\n```\r\n{\"16\": 0.11653269396629184, \"32\": 0.13803347101202235, \"64\": 0.1889677940052934, \"128\": 0.42529276601271704, \"256\": 1.4768535409821197, \"300\": 2.165687720000278, \"400\": 3.581374307977967, \"500\": 5.615040614036843, \"600\": 8.182245634961873, \"700\": 10.219899011019152, \"800\": 14.204097100009676, \"900\": 19.01026200200431, \"1000\": 21.914704270020593, \"1500\": 50.26287814299576, \"2000\": 88.03798637498403, \"2500\": 140.229756515997, \"3000\": 206.8722462329897, \"4000\": 373.4201490940177, \"5000\": 596.6820141010103, \"6000\": 831.5039637690061, \"8000\": 1579.1185438489774, \"10000\": 2624.7711193099967}\r\n```\r\n\r\n\u003c/details>\r\n\r\nI have inherited a library which has a very simple DSL to query data from a database and which returns a dictionary of different types depending on the input. Indeed, the language is so simple that I could map these to a collection of literal overloads, with a generic fallback for new/unmapped data. In practice this looks something like:\r\n\r\n\r\n```\r\nimport typing\r\n\r\n@typing.overload\r\ndef get_param(param: typing.Literal['some_float']) -> float: ...\r\n\r\n\r\n@typing.overload\r\ndef get_param(param: typing.Literal['some_other_int']) -> int: ...\r\n\r\n\r\n@typing.overload\r\ndef get_param(param: typing.Literal['further_str']) -> str: ...\r\n\r\n```\r\n\r\nBeing able to do static analysis (and completion) on such an interface would be hugely beneficial to its users for correctness and ease of use. Unfortunately the total number of overloads would need to be in the order of 100,000... clearly from the graph, this number is prohibitive with the current implementation of mypy's overload functionality.\r\n\r\n\r\n**Pitch**\r\n\r\nI'm therefore reaching out to find out if there is a known good reason for this time-complexity, and potentially seeking help/pointers to address the issue in the implementation.\r\n\r\n**Other places this could be useful**\r\n\r\nTruth be told, this is a highly specialised requirement which would apply to a fairly limited set of use cases (some of which are likely anti-patterns in the first place).\r\n\r\nGiven the high number of overloads involved for this time-complexity to become an issue (at around 100 overloads), it is clear that you'd almost *always* want to generate the stubs rather than hand-craft them. Examples of where it could come in handy are other string based lookups - I can imagine for example wanting to generate stubs for all of the [JClasses that exist in JPype](https://jpype.readthedocs.io/en/latest/api.html?highlight=jclass#jpype.JClass) (which can be any Java classes available in the JVM), or perhaps for some interface that allows you to get hold of a CSS property by name and which returns a slightly different type for each of the ~520 valid tags. I could also imagine this being something that could be used for generating the permutations of a multiple-dispatch system.\r\n\r\n","author":{"url":"https://github.com/pelson","@type":"Person","name":"pelson"},"datePublished":"2021-02-01T14:48:38Z","url":"https://github.com/python/mypy/issues/10004"}

react-profiling0
react-import-mapreact,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322
route-pattern/_view_fragments/issues/show/:user_id/:repository/:id/issue_layout(.:format)
route-controllervoltron_issues_fragments
route-actionissue_layout
fetch-noncev2:1e315712-0458-d1b8-932c-0afbcd8ba773
current-catalog-service-hash81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114
request-idEE36:18FDF5:2F1504:3F22A8:6B0025BF
html-safe-nonce431ee41a4dc7c3e2cad1c3d5a74669212e0a24681e88536fe5fb9cbdf1da786f
visitor-payloadeyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJFRTM2OjE4RkRGNToyRjE1MDQ6M0YyMkE4OjZCMDAyNUJGIiwidmlzaXRvcl9pZCI6IjcxOTk2NjY1MTM0NDIyNTIyMjMiLCJyZWdpb25fZWRnZSI6ImlhZCIsInJlZ2lvbl9yZW5kZXIiOiJpYWQifQ==
visitor-hmace7f97b653e32aeab762bca18ce5221eb4ab1d4e4c676fb2ac1623051db136828
hovercard-subject-tagissue:798421331
github-keyboard-shortcutsrepository,issues,copilot
google-site-verificationApib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I
octolytics-urlhttps://collector.github.com/github/collect
analytics-location///voltron/issues_fragments/issue_layout
fb:app_id1401488693436528
apple-itunes-appapp-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/python/mypy/10004/issue_layout
twitter:imagehttps://opengraph.githubassets.com/400578b92ee317df2a10ecfc5671fb51036bc37fc13f7d3da2a2cce994b1785a/python/mypy/issues/10004
twitter:cardsummary_large_image
og:imagehttps://opengraph.githubassets.com/400578b92ee317df2a10ecfc5671fb51036bc37fc13f7d3da2a2cce994b1785a/python/mypy/issues/10004
og:image:altFeature The time complexity of dealing with function overloads in mypy appears to be polynomial. Naively, it seems this is not a fundamental limit (I have no experience in static analysis to base t...
og:image:width1200
og:image:height600
og:site_nameGitHub
og:typeobject
og:author:usernamepelson
hostnamegithub.com
expected-hostnamegithub.com
None4eb4cba0d69f045374ac15de9666d22b0961e1d555cc3824f36b7734c00c78e0
turbo-cache-controlno-preview
go-importgithub.com/python/mypy git https://github.com/python/mypy.git
octolytics-dimension-user_id1525981
octolytics-dimension-user_loginpython
octolytics-dimension-repository_id7053637
octolytics-dimension-repository_nwopython/mypy
octolytics-dimension-repository_publictrue
octolytics-dimension-repository_is_forkfalse
octolytics-dimension-repository_network_root_id7053637
octolytics-dimension-repository_network_root_nwopython/mypy
turbo-body-classeslogged-out env-production page-responsive
disable-turbofalse
browser-stats-urlhttps://api.github.com/_private/browser/stats
browser-errors-urlhttps://api.github.com/_private/browser/errors
release44c658b24abf00491fb7ae5f56d42c9f38cbeab2
ui-targetfull
theme-color#1e2327
color-schemelight dark
react-app-nameissues

Links:

Skip to contenthttps://github.com/python/mypy/issues/10004#start-of-content
https://github.com/
Sign inhttps://github.com/login?return_to=https%3A%2F%2Fgithub.com%2Fpython%2Fmypy%2Fissues%2F10004
GitHubRepository hosting, code review, and collaborationhttps://github.com/platform
CopilotAI coding agent for tasks, projects, and automated workhttps://github.com/features/copilot
ActionsCI/CD and automationhttps://github.com/features/actions
Code QualityQuality analysis, fixes, and enforcementhttps://github.com/features/code-quality
CodespacesCloud development environmentshttps://github.com/features/codespaces
Code SecurityVulnerability detection and remediationhttps://github.com/security/advanced-security/code-security
Secret ProtectionSecret scanning and leak preventionhttps://github.com/security/advanced-security/secret-protection
All Featureshttps://github.com/features
Documentationhttps://docs.github.com/en
Traininghttps://learn.github.com/skills
Certificationshttps://learn.github.com/credentials
Build with Copilothttps://github.com/features/ai
Customize Copilothttps://docs.github.com/en/copilot/how-tos/copilot-on-github/customize-copilot/customize-copilot-overview
Integrationshttps://github.com/marketplace
Trending reposhttps://github.com/trending
GitHub Sponsorshttps://github.com/open-source/sponsors
Developer articleshttps://github.com/resources/articles
ChangelogYour source for the latest features, improvements, and fixes across GitHub products, all in one place.https://github.blog/changelog/
Enterpriseshttps://github.com/enterprise
Teamhttps://github.com/team
Startupshttps://github.com/enterprise/startups
Nonprofitshttps://github.com/solutions/industry/nonprofits
Healthcarehttps://github.com/solutions/industry/healthcare
Financial serviceshttps://github.com/solutions/industry/financial-services
Manufacturinghttps://github.com/solutions/industry/manufacturing
Governmenthttps://github.com/solutions/industry/government
See all industrieshttps://github.com/solutions/industry
Why GitHubhttps://github.com/why-github
Customer Storieshttps://github.com/customer-stories
Business insightshttps://github.com/solutions/executive-insights
Trust Centerhttps://github.com/trust-center
GitHub Advanced SecurityEnterprise-grade code securityhttps://github.com/security/advanced-security
Copilot for businessEnterprise-grade AI featureshttps://github.com/features/copilot/copilot-business
Premium SupportEnterprise-grade 24/7 supporthttps://github.com/enterprise/premium-support
Documentationhttps://docs.github.com/en
Resource centerhttps://github.com/resources
Bloghttps://github.blog/
Events & webinarshttps://github.com/resources/events
Community Forumhttps://github.com/orgs/community/discussions
Customer Storieshttps://github.com/customer-stories
Integrationshttps://github.com/marketplace
Customer supporthttps://help.github.com/
Traininghttps://learn.github.com/skills
GitHub Statushttps://www.githubstatus.com/
Abouthttps://github.com/about
Partnershttps://github.com/partners
Changeloghttps://github.blog/changelog/
GitHub UniverseThe event for developers, by developers — talks, workshops, and what’s next for GitHub.https://githubuniverse.com/
Pricinghttps://github.com/pricing
Sign inhttps://github.com/login?return_to=https%3A%2F%2Fgithub.com%2Fpython%2Fmypy%2Fissues%2F10004
Sign uphttps://github.com/signup?ref_cta=Sign+up&ref_loc=header+logged+out&ref_page=%2F%3Cuser-name%3E%2F%3Crepo-name%3E%2Fvoltron%2Fissues_fragments%2Fissue_layout&source=header-repo&source_repo=python%2Fmypy
Reloadhttps://github.com/python/mypy/issues/10004
Reloadhttps://github.com/python/mypy/issues/10004
Reloadhttps://github.com/python/mypy/issues/10004
pythonhttps://github.com/python
mypyhttps://github.com/python/mypy
Codehttps://github.com/python/mypy
Issues2.7k (2.7k)https://github.com/python/mypy/issues
Pull requests546 (546)https://github.com/python/mypy/pulls
Actionshttps://github.com/python/mypy/actions
Projectshttps://github.com/python/mypy/projects
Wikihttps://github.com/python/mypy/wiki
Security and qualityhttps://github.com/python/mypy/security
Insightshttps://github.com/python/mypy/insights
https://github.com/python/mypy
New issuehttps://github.com/login?return_to=https://github.com/python/mypy/issues/10004
New issuehttps://github.com/login?return_to=https://github.com/python/mypy/issues/10004
#15865https://github.com/python/mypy/pull/15865
#21218https://github.com/python/mypy/pull/21218
Polynomial time-complexity of typing.overloadhttps://github.com/python/mypy/issues/10004#top
#15865https://github.com/python/mypy/pull/15865
#21218https://github.com/python/mypy/pull/21218
performancehttps://github.com/python/mypy/issues?q=state%3Aopen%20label%3A%22performance%22
topic-overloadshttps://github.com/python/mypy/issues?q=state%3Aopen%20label%3A%22topic-overloads%22
https://github.com/pelson
pelsonhttps://github.com/pelson
on Feb 1, 2021https://github.com/python/mypy/issues/10004#issue-798421331
https://user-images.githubusercontent.com/810663/106470862-4da36c00-64a1-11eb-85a4-dea04fc5f61b.png
JClasses that exist in JPypehttps://jpype.readthedocs.io/en/latest/api.html?highlight=jclass#jpype.JClass
pelsonhttps://github.com/pelson
featurehttps://github.com/python/mypy/issues?q=state%3Aopen%20label%3A%22feature%22
on Feb 1, 2021https://github.com/python/mypy/issues/10004#event-4274106905
https://github.com/henribru
henribruhttps://github.com/henribru
on Feb 6, 2021https://github.com/python/mypy/issues/10004#issuecomment-774529312
microsoft/pyright@d9f621ehttps://github.com/microsoft/pyright/commit/d9f621e19cef94675d6fe23e4208c98f9d863d6b
300 overloadshttps://github.com/henribru/google-api-python-client-stubs/blob/master/googleapiclient-stubs/discovery.pyi#L343
anotherhttps://github.com/henribru/google-ads-stubs
https://github.com/henribru
henribruhttps://github.com/henribru
on Mar 4, 2021https://github.com/python/mypy/issues/10004#issuecomment-790772520
https://github.com/python/mypy/blob/master/mypy/checker.py#L486https://github.com/python/mypy/blob/master/mypy/checker.py#L486
https://github.com/hauntsaninja
hauntsaninjahttps://github.com/hauntsaninja
on Aug 4, 2021https://github.com/python/mypy/issues/10004#issuecomment-892421821
#10922https://github.com/python/mypy/pull/10922
AlexWaygoodhttps://github.com/AlexWaygood
topic-overloadshttps://github.com/python/mypy/issues?q=state%3Aopen%20label%3A%22topic-overloads%22
performancehttps://github.com/python/mypy/issues?q=state%3Aopen%20label%3A%22performance%22
featurehttps://github.com/python/mypy/issues?q=state%3Aopen%20label%3A%22feature%22
on Apr 1, 2022https://github.com/python/mypy/issues/10004#event-6349050062
hauntsaninjahttps://github.com/hauntsaninja
on Aug 13, 2023https://github.com/python/mypy/issues/10004#event-10080580486
Skip overlapping overload check at large overload countshttps://github.com/hauntsaninja/mypy/commit/b5a4d7d2ddb8e442676e583ab76fe6b318695c00
https://docs.github.com/articles/closing-issues-via-commit-messages
b5a4d7dhttps://github.com/hauntsaninja/mypy/commit/b5a4d7d2ddb8e442676e583ab76fe6b318695c00
https://github.com/pelson
pelsonhttps://github.com/pelson
on Apr 14, 2026https://github.com/python/mypy/issues/10004#issuecomment-4241618338
#20439 (comment)https://github.com/python/mypy/issues/20439#issuecomment-3677073976
#21218https://github.com/python/mypy/pull/21218
hauntsaninjahttps://github.com/hauntsaninja
completedhttps://github.com/python/mypy/issues?q=is%3Aissue%20state%3Aclosed%20archived%3Afalse%20reason%3Acompleted
#15865https://github.com/python/mypy/pull/15865
on Nov 7, 2026https://github.com/python/mypy/issues/10004#event-35462226664
hauntsaninjahttps://github.com/hauntsaninja
on Nov 7, 2026https://github.com/python/mypy/issues/10004#event-35462236339
Prevent quadratic runtime for overlap check at large overload counts (p…https://github.com/hauntsaninja/mypy/commit/5dc284074f99935d394babd1fc555cf0d6405fb9
p…https://github.com/python/mypy/pull/15865
https://docs.github.com/articles/closing-issues-via-commit-messages
5dc2840https://github.com/hauntsaninja/mypy/commit/5dc284074f99935d394babd1fc555cf0d6405fb9
Sign up for freehttps://github.com/signup?return_to=https://github.com/python/mypy/issues/10004
Sign in to commenthttps://github.com/login?return_to=https://github.com/python/mypy/issues/10004
performancehttps://github.com/python/mypy/issues?q=state%3Aopen%20label%3A%22performance%22
topic-overloadshttps://github.com/python/mypy/issues?q=state%3Aopen%20label%3A%22topic-overloads%22
https://github.com
Termshttps://docs.github.com/site-policy/github-terms/github-terms-of-service
Privacyhttps://docs.github.com/site-policy/privacy-policies/github-privacy-statement
Securityhttps://github.com/security
Statushttps://www.githubstatus.com/
Communityhttps://github.community/
Docshttps://docs.github.com/
Contacthttps://support.github.com?tags=dotcom-footer

Viewport: width=device-width


URLs of crawlers that visited me.