Speed up union simplification

[JukkaL]

Union simplification (make_simplified_union) has been causing multiple performance issues (at least #9169, #12408, #12225). It can make proper subtype checks of all union items against all other items, which is O(n**2) -- with certain O(n) fast paths that cover some (but not all) problematic scenarios. Union simplification is fairly performance-critical even when we don't hit worst-case scenarios.

Here are some ideas about what we might do to improve the situation:

1. Somehow implement union simplification of multiple Instance types (at least simple ones) in close to linear time. I suspect that this is possible under some reasonable assumptions.
2. Cache negative results of proper subtype checks. I think that currently we only cache positive results (in mypy.typestate). This might have some drawbacks, such as a possible explosion of cache sizes. I assume there's a reason why we aren't currently doing this. Union simplification tends to perform many proper subtype checks with negative results.
3. Avoid doing full union simplification in some cases, perhaps based on some heuristics. Union simplification should never be semantically necessary.
4. Add fast paths for the most common union simplification operations (e.g. single item, X | None).

[erictraut]

Every large union case that I've observed in real code involves large numbers of literals — either str or int literals. All of the problems cited above appear to follow this pattern.

In pyright, I mitigate this problem by maintaining maps of str and int literal values within a union. I use these two maps to avoid the O(n**2) behavior for union operations that involve literal values. So this combines aspects of your proposal 1 and 4.

[JukkaL]

Every large union case that I've observed in real code involves large numbers of literals — either str or int literals. All of the problems cited above appear to follow this pattern.

The colour-science package also uses medium-sized unions (e.g. ~10 items) without any literals, which are slow enough to cause trouble (#12225). The unions contain protocol types that are particularly slow to process by mypy. Caching negative proper subtype checks involving protocol types could already help quite a bit with colour-science.

In pyright, I mitigate this problem by maintaining maps of str and int literal values within a union.

Mypy does something a bit similar in a few places. However, we decompose the union types into literals vs non-literals separately on every operation. This sounds a bit different from what pyright does, and the pyright approach sounds more efficient. We could consider adopting this approach if smaller optimizations don't seem enough.

[JukkaL]

Here's one more idea:

5. We could cache the results of make_simplified_union operations, since sometimes we repeatedly simplify the exact same types over and over again. We may need to flush items from the cache (e.g. using LRU caching) to avoid using lots of memory in worst case scenarios.