Optimize comparison methods in immutable collections
- Dominant language
- C#
- Stars
- 18.3k
- Forks
- 5.6k
- PR merge metrics
- PR metrics pending
Description
### 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` or `SortedSet`).
#### The Problem
This intermediate allocation is often **unnecessary**. For example, if both collections are of the same type (e.g., both are `ImmutableSortedSet`) 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:
- [x] `ImmutableHashSet.SetEquals` (#126309)
- [x] `ImmutableSortedSet.SetEquals` (#126549)
- [ ] `ImmutableHashSet.IsProperSubsetOf` (#127368)
- [ ] `ImmutableHashSet.IsSubsetOf` (#131063)
- [ ] `ImmutableSortedSet.IsSubsetOf`
- [ ] `ImmutableSortedSet.IsProperSubsetOf`
Contributor guide
Assessment
This issue has not been assessed yet.