[ty] Optimize IntersectionType for the common case of a single negated element#22344
[ty] Optimize IntersectionType for the common case of a single negated element#22344AlexWaygood merged 11 commits intomainfrom
IntersectionType for the common case of a single negated element#22344Conversation
Diagnostic diff on typing conformance testsNo changes detected when running ty on typing conformance tests ✅ |
|
CodSpeed Performance ReportMerging #22344 will not alter performanceComparing Summary
Footnotes
|
|
#22353 applies the same optimisation to |
MichaReiser
left a comment
There was a problem hiding this comment.
Nice find.
I would be interested in exploring if we can use a Box<[Type<'db>]> in IntersectionType either by:
- Use a dedicated union with a
Slice(empty or more than one element) andSingle(exactly one element) - Use a
SmallVecinstead
The advantage of using a slice is that it doesn't increase the complexity of the read methods (they can all be abstracted by implementing Deref where the Target is a [T] (use std::slice::from_ref to create a slice from a single element). The ordered set can be converted into a boxed slice using https://docs.rs/ordermap/latest/ordermap/set/struct.OrderSet.html#method.into_boxed_slice (which I believe is as expensive as calling Vec::into_boxed_slice)).
The IntersectionBuilder would keep your existing enum
I think this might degrade the performance of |
I also just noticed that |
right. But I'm trying out your suggestion of a smallvec, just for comparison. |
Doesn't that mean that we need to copy (and create a new allocation) for the many elements case? |
Yes. Which is why I didn't go for that in this PR 😄 |
|
The codspeed report on the smallvec version does actually seem to indicate a similar level of speedup, and it seems to indicate that a broader range of benchmarks benefit? https://codspeed.io/astral-sh/ruff/branches/alex%2Foptimize-intersections-single-neg-slice?utm_source=github&utm_medium=check&utm_content=details |
MichaReiser
left a comment
There was a problem hiding this comment.
This looks good. But I think we have to manually implement PartialEq, Eq and Hash
1dab95e to
e17e2c0
Compare
Co-authored-by: Micha Reiser <[email protected]>
…rsectionElements::recursive_type_normalized_impl`
f929cbc to
a293de8
Compare
2d3ca48 to
e1cbb79
Compare
I rebased #22353 on |
Summary
We call
Type::negate()a lot across the codebase. In most cases, it creates an intersection type with 0 positive elements and a single negative element.Our representation of
IntersectionTypeis currently not very well optimised for this very common case, however: no matter how many negative elements are in the intersection, we always use anFxOrderSetto store these negative elements. I believe that, like most generic Rust collections,OrderSetdoes not allocate if it has 0 elements contained inside it, but performs a heap allocation as soon as a single element is allocated.This PR gets rid of the heap allocation for the common case of a single negative element. This leads to across-the-board speedups of 1-4%, including a 4-5% speedup on colour-science, one of the benchmarks on which we currently do worst.
Test Plan
Existing tests all pass and the primer report is clean (except for the known set of flakes).