Repository navigation
Speed up union simplification #12526
Description
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:
- Somehow implement union simplification of multiple
Instancetypes (at least simple ones) in close to linear time. I suspect that this is possible under some reasonable assumptions. - 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. - Avoid doing full union simplification in some cases, perhaps based on some heuristics. Union simplification should never be semantically necessary.
- Add fast paths for the most common union simplification operations (e.g. single item,
X | None).
Activity
erictraut commentedon Apr 5, 2022
Every large union case that I've observed in real code involves large numbers of literals — either
strorintliterals. All of the problems cited above appear to follow this pattern.In pyright, I mitigate this problem by maintaining maps of
strandintliteral 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 commentedon Apr 6, 2022
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.
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 commentedon Apr 6, 2022
Here's one more idea:
make_simplified_unionoperations, 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.Minor proper subtype check optimization
Minor proper subtype check optimization
Speed up Instance.__hash__
Speed up Instance.__hash__ (#12538)
Speed up LiteralType.__hash__
Further speed up union simplification
Speed up caching of subtype checks (#12539)
Further speed up union simplification (#12541)
Minor proper subtype check optimization (#12536)
make_simplified_union: add caching and reduce allocations
huguesb commentedon Apr 23, 2022
I have a PR doing just that. I'm not too worried about the cache growing too large. I added some logging of calls to
make_simplified_union(and their inputs) while running over a large codebase (>20k files) and usedsort/uniq -cto get a sense of the potential caching benefits. I saw ~70k calls tomake_simplified_unionbut only ~7k distinct inputs/outputs, which seems like a pretty reasonable size for a cache. We could keep that cache even smaller by special-casing inputs with only one or two items.Overall performance improvement seems to be around 10-20% for this particular codebase. Fwiw, the bulk of the slowness comes from inputs with ~10
Type[]make_simplified_union: add caching and reduce allocations
JukkaL commentedon Apr 25, 2022
It seems like it would be trivial to just clear the cache if we happen to hit an unexpected scenario where the cache grows too large. Normally we wouldn't need this, but if we do, the cost of occasionally clearing the cache is probably still fairly minor.
This is a great result! I did some profiling and I believe that non-trivial performance improvements should be fairly common (at least in the 1-10% range), and in some cases the impact could be even higher than 20%.
However, I also noticed that our current
Typehashing implementation doesn't seem to work quite right for the caching (see #12659 (comment)). The deviations that might happen will probably be very rare, but if they happen, they could be extremely confusing, so I think it's important to address the correctness of hashing first.From the above comment, these are main issues I've found:
Typesubclasses seem to have incorrect/missing/incomplete__eq__and/or__hash__methods. This should be pretty easy to fix and are just bugs. It would be good to also have some unit tests for these.lineandcolumnattributes ofTypeare not using in type equality/hashing, but they might plausibly affect type checking results in edge cases (e.g. locations of errors).can_be_trueandcan_be_falseattributes are ignored in equality/hashing, but they might plausibly affect type checking.(1) should be easy to fix. Somebody just needs to review all
__eq__and__hash__methods and ensure that they exist for all concrete subclasses ofTypeand they cover all the important attributes.(2) Is more tricky. One option might be to remove the uses of
lineandcolumnattributes during type checking, i.e. they'd only be used during semantic analysis, when we shouldn't perform any union simplification. Another option would be removelineandcolumnattributes from mostTypesubclasses, except the "syntactic" ones such asUnboundTypewhere they are required for error reporting. I'm not sure how feasible this would be. We'd need to track the line numbers separately where they are needed.(3) This could be fixed by just including
can_be_trueandcan_be_falsein all__eq__and__hash__methods. A better fix might to move these away from type objects altogether and store them in some other way, but this may be quite difficult to achieve, and potentially not worth the effort.huguesb commentedon Apr 30, 2022
As mentioned in #12659
Definitely needs fixing. Do you have more details on which classes are affected?
Can easily be addressed, I think, by removing the line/column parameters of
make_simplified_union. Most callers ofmake_simplified_uniondo not supply them, and updating those that do to omit those parameters results in a green CI run (including mypy_primer): see EXPERIMENT remove line/column param to make_simplified_union #12698If the callers of
make_simplified_uniondo not care about line/column then neither should the cache...I'm not quite sure what to make of that right now. The semantics of those attributes are confusing me and I will need to take a closer look at them.