Very slow performance for huge literals

[sassanh]

Pyright becomes very slow when it's dealing with huge literal types like this.

The gist includes a python file as well as a typescript file, since pyright is written in JS and typescript lsp is written in JS as well, I provided a typescript version as a proof that it can be much faster.

Running pyright on the python file or using pyright's autocompletion on x: Icon = 'a will take more than 20 seconds on M1 pro.
Using tsserver's autocompletion on const x: Icon = 'a immediately lists all possible options.

[erictraut]

Pyright already contains significant optimizations for large unions, but I've never seen a union with more than a few hundred items. The one in your example contains nearly 3500 elements.

Many type operations involving unions are O(n^2), and if those operations are nested within other operations, the cost can grow many times that.

I'll take a look at whether there are additional optimizations that could help here, but I consider this a low priority. I also don't consider this a bug, so I'll change it to an enhancement request.

[sassanh]

Thanks! Just note that even five hundred items make pyright take 3 seconds more to run on my project.
Also I think there must be room for big optimizations as tsserver also written in JS can take care of 3500 items in a matter of tens of milliseconds, so I think its operations are not O(n^2).

[sassanh]

I also don't consider this a bug, so I'll change it to an enhancement request.

The reason I created it as a bug is because this issue makes pyright's autocompletion basically unusable for a project having a single file like this in its codebase. I think having a literal with 3500 items is as legit as having a literal with 35 items, it shouldn't break the tool.

[erictraut]

TS and Python are different languages, and their type systems differ somewhat, so direct comparisons don't necessarily apply.

I recommend against creating such large unions. There are many tools in the Python ecosystem that will not be able to deal with them. I know from experience that pyright already deals with large unions much better than mypy, and both of them deal better with large unions that the other two major type checkers (pyre and pytype). I haven't tested runtime type checkers or libraries that use types at runtime, but I would guess that they would also perform very badly if they encountered such a large union.

I think having a literal with 3500 items is as legit as having a literal with 35 items

I'm going to push back on you there. There will be some limit beyond which performance will be unacceptably slow. You're creating a type here that is far larger (by an order of magnitude!) than what I have seen before in Python code.

[sassanh]

TS and Python are different languages, and their type systems differ somewhat, so direct comparisons don't necessarily apply.

Yes, but I really doubt if pyright needs to do anything in complexity of O(n^2) just cause it is dealing with Python and tsserver doesn't need to do that because it is dealing with TypeScript. I mean doing a prefix search on a huge list of strings shouldn't be much different when it is used for TypeScript autocompletion or Python autocompletion. But you definitely know better.

I'm going to push back on you there. There will be some limit beyond which performance will be unacceptably slow. You're creating a type here that is far larger (by an order of magnitude!) than what I have seen before in Python code.

I understand that it is not a common use-case, but I don't agree it is a reason to conclude it's not a legit use-case. The gist I provided is a good example itself: using literal unions for the list of material icons isn't abusing the Python's annotation api to achieve something it is not designed for.

Maybe it's not common because people try it and see Python tools are not working well with large unions and they don't bother creating issues in their repositories and just give up and go with normal strings. But it's obvious that if we can benefit from annotations here, it will reduce human error and is considered an improvement for this tool and the Python community.

It has happened to myself many times in the past few weeks that I mistakenly wrote an icon name with dashes while it needed underscore or write it plural while it was singular or had a typo.

[Viicos]

Running pyright on the python file or using pyright's autocompletion on x: Icon = 'a will take more than 20 seconds on M1 pro.

I've tried playing with this locally (both in VSCode and by running pyright on the file), and I get decent results. Things are lagging a bit (e.g. when typing x: Ic..., things take around 1 sec to update) but the autocompletion takes less than 1 second in my case. Running pyright on your gist + the x: Icon = "10k" also takes less than one second. But this is of course just with the gist you provided, you might have other things in the same file related to the Icon literal

[erictraut]

As I mentioned, pyright already contains numerous optimizations specifically for unions that contain many literals. I've added special-casing to a few more code paths, which significantly decreases the analysis time in this particular example — at least for some common use cases. These optimizations will be in the next release.

That said, I stand by my earlier statement. I strongly recommend against defining such large unions. There are many situations where a Python type checker must check all combinations of two unions, which results in O(n x m) performance. Take for example:

def func(a: Icon, b: Icon | None):
    return a + b

In Python (unlike in TypeScript), the + operator is overridable, and all combinations of a and b need to be checked pairwise. If a and b are both unions, then the validation cost for the expression a + b is O(an x bn) where an is the size of of the union for a and bn is the size of the union for b. I've intentionally used Icon | None for the type of b to demonstrate that even if the type checker special-cases literal-only unions, it's easy to introduce non-literal types into a union.

If you define unions with thousands of subtypes, you will encounter these "performance cliffs" in a type checker. When you do, I will not be sympathetic.

I've confirmed that mypy's behavior is similar, which is unsurprising.

Please don't abuse the type system!

[sassanh]

Doing a prefix search in even 60,000 items shouldn't take long, if the underlying data-structure is working in O(n^2), it is considered abusing of data structures, if we choose the correct data-structure and algorithms the auto-completions for a union even as big as 60,000 items (an order of magnitude bigger than the one in my gist) should be responsive.

I'm not abusing typing system, Pyright gives up so fast:

It gives up on 256 items:

tsserver, being responsive for 4096 items:
https://github.com/microsoft/pyright/assets/1270688/4836740e-b9ae-4154-b8be-70eee1599efe
tsserver not giving up even for 65536 items:
https://github.com/microsoft/pyright/assets/1270688/45babf7b-eff8-4610-80b6-2a1599e3f16e

I understand there is a lot of work to do and Pyright is mostly a one man show and it is an open source project, so I'm not saying we need to push the limit of the number of items in a literal that makes Pyright unresponsive from 200 to 10K in the next version.
I'm just saying that we should acknowledge it is possible for the autocompletion module to stay responsive even for 10K items and keep this issue open until it is realized (maybe in 5 years).
+ operator is something different than prefix searching, prefix searching is not blocked by validating + operator. Pyright can ignore + operator on literal strings with an x bn greater than 5K and yet perform responsive for prefix searching on literals with 10k items, these limits don't need to be the same.

So I think I'm not abusing the typing system, the typing system and tools like Pyright are being developed and they are not mature enough to handle all the legit use-cases like my legit use-case of creating a literal for names of the icons in an icon font.

[erictraut]

This is addressed in pyright 1.1.349, which I just published.

[sassanh]

Thank you! The autocompletion is tens of times faster (it responds in less than 200ms) and pyright checks the whole codebase in less than 3 seconds (it used to take more than 20 seconds.)
I really appreciate you addressing this issue in less than 24 hours.