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
Domain: github.com
{"@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\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-profiling | 0 |
| react-import-map | react,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-controller | voltron_issues_fragments |
| route-action | issue_layout |
| fetch-nonce | v2:1e315712-0458-d1b8-932c-0afbcd8ba773 |
| current-catalog-service-hash | 81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114 |
| request-id | EE36:18FDF5:2F1504:3F22A8:6B0025BF |
| html-safe-nonce | 431ee41a4dc7c3e2cad1c3d5a74669212e0a24681e88536fe5fb9cbdf1da786f |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJFRTM2OjE4RkRGNToyRjE1MDQ6M0YyMkE4OjZCMDAyNUJGIiwidmlzaXRvcl9pZCI6IjcxOTk2NjY1MTM0NDIyNTIyMjMiLCJyZWdpb25fZWRnZSI6ImlhZCIsInJlZ2lvbl9yZW5kZXIiOiJpYWQifQ== |
| visitor-hmac | e7f97b653e32aeab762bca18ce5221eb4ab1d4e4c676fb2ac1623051db136828 |
| hovercard-subject-tag | issue:798421331 |
| github-keyboard-shortcuts | repository,issues,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/python/mypy/10004/issue_layout |
| twitter:image | https://opengraph.githubassets.com/400578b92ee317df2a10ecfc5671fb51036bc37fc13f7d3da2a2cce994b1785a/python/mypy/issues/10004 |
| twitter:card | summary_large_image |
| og:image | https://opengraph.githubassets.com/400578b92ee317df2a10ecfc5671fb51036bc37fc13f7d3da2a2cce994b1785a/python/mypy/issues/10004 |
| og:image:alt | 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... |
| og:image:width | 1200 |
| og:image:height | 600 |
| og:site_name | GitHub |
| og:type | object |
| og:author:username | pelson |
| hostname | github.com |
| expected-hostname | github.com |
| None | 4eb4cba0d69f045374ac15de9666d22b0961e1d555cc3824f36b7734c00c78e0 |
| turbo-cache-control | no-preview |
| go-import | github.com/python/mypy git https://github.com/python/mypy.git |
| octolytics-dimension-user_id | 1525981 |
| octolytics-dimension-user_login | python |
| octolytics-dimension-repository_id | 7053637 |
| octolytics-dimension-repository_nwo | python/mypy |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 7053637 |
| octolytics-dimension-repository_network_root_nwo | python/mypy |
| turbo-body-classes | logged-out env-production page-responsive |
| disable-turbo | false |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 44c658b24abf00491fb7ae5f56d42c9f38cbeab2 |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
| react-app-name | issues |
Links:
Viewport: width=device-width