Description
While working on PR #126309 for Issue #90986, I noticed that the current implementation of several comparison methods in the System.Collections.Immutable library always creates a new intermediate collection (like HashSet<T> or SortedSet<T>).
The Problem
This intermediate allocation is often unnecessary. For example, if both collections are of the same type (e.g., both are ImmutableSortedSet<T>) and share the same comparer, we can perform the comparison directly without allocating any new memory on the heap.
The Solution
I propose adding a "Fast Path" to detect these cases and perform the check directly. This will:
- Eliminate unnecessary allocations when types/comparers are compatible.
- Improve performance by moving from building a fully new collection to a direct linear comparison of existing elements wherever applicable.
Targeted Methods & Progress
I am taking ownership of this optimization and will be submitting focused PRs for each:
Next Steps: I plan to apply the same pattern to:
ImmutableHashSet<T>: IsSubsetOf.ImmutableSortedSet<T>: IsSubsetOf, IsProperSubsetOf.- Any other applicable locations within the immutable collections where this "Fast Path" pattern can be leveraged to avoid redundant allocations.
Description
While working on PR #126309 for Issue #90986, I noticed that the current implementation of several comparison methods in the
System.Collections.Immutablelibrary always creates a new intermediate collection (likeHashSet<T>orSortedSet<T>).The Problem
This intermediate allocation is often unnecessary. For example, if both collections are of the same type (e.g., both are
ImmutableSortedSet<T>) and share the same comparer, we can perform the comparison directly without allocating any new memory on the heap.The Solution
I propose adding a "Fast Path" to detect these cases and perform the check directly. This will:
Targeted Methods & Progress
I am taking ownership of this optimization and will be submitting focused PRs for each:
ImmutableHashSet<T>.SetEquals: Optimization already submitted in PR Optimize ImmutableHashSet<T>.SetEquals to avoid unnecessary allocations #126309.ImmutableSortedSet<T>.SetEquals: Optimization already submitted in PR Optimize ImmutableSortedSet<T>.SetEquals to avoid unnecessary allocations #126549.ImmutableHashSet<T>.IsProperSubsetOf: Optimization already submitted in PR Optimize ImmutableHashSet<T>.IsProperSubsetOf to avoid unnecessary allocations #127368.Next Steps: I plan to apply the same pattern to:
ImmutableHashSet<T>:IsSubsetOf.ImmutableSortedSet<T>:IsSubsetOf,IsProperSubsetOf.