What's wrong
ContiguousSet<T>.IntersectWith (Containers/ContiguousSet.cs ~L359-374) and SymmetricExceptWith (~L403-425) walk the set backwards. For each element to drop, they call the public Remove(item) (~L276-316). Remove then does the following for every element:
- Removes the item from the
HashSet again.
- Scans
items from index 0 with comparer.Equals, an interface call, until it rediscovers the item. The caller was already holding that item at index i.
- Shifts the tail of the array.
Dropping k of n elements therefore costs O(n·k), which is O(n²) when most of the set goes. HashSet<T> does the same operation in O(n).
Measurements
Release build, net10, scratch MSTest:
ContiguousSet.IntersectWith(empty) n=25000: 295 ms n=50000: 576 ms n=100000: 2273 ms
ContiguousSet.SymmetricExceptWith(same) n=25000: 161 ms n=50000: 613 ms n=100000: 2347 ms
HashSet.IntersectWith(empty) n=100000: 0 ms
- In a Debug build, n = 100k takes about 23 s.
- Doubling n makes the operation roughly 4× slower, which confirms quadratic growth.
- The results are correct; only the running time is the problem.
ContiguousSet<int> cs = new(Enumerable.Range(0, n));
cs.IntersectWith([]); // ~2.3 s at n = 100k
cs = new(Enumerable.Range(0, n));
cs.SymmetricExceptWith(Enumerable.Range(0, n)); // ~2.3 s at n = 100k
Why it matters
ContiguousSet is the cache-friendly set in this package, and the reason to pick it is performance. A common bulk operation, such as filtering a set down to a small allow-list, freezes the calling thread for seconds at modest sizes.
Suggested fix
Do each operation in a single compaction pass:
- Keep a write index
w. For each i, either copy items[i] to items[w++] (keep), or call uniquenessSet.Remove(items[i]) (drop).
- Afterwards, clear
items[w..Count) when T may hold references, then set Count = w.
- For
SymmetricExceptWith, then add the items that are only in other.
This is O(n + m) and preserves insertion order.
Secondary: InsertionOrderSet.IntersectWith and SymmetricExceptWith (InsertionOrderSet.cs ~L284-353) call items.RemoveAt(i) once per element. They are quadratic in the memmove: 48 ms at 50k and 189 ms at 100k when keeping the upper half. The same compaction pass fixes them.
Add benchmarks or tests covering n = 100k for both types.
This is not covered by #82, which is about the bulk constructors and set operations of OrderedSet/OrderedCollection/OrderedMap.
What's wrong
ContiguousSet<T>.IntersectWith(Containers/ContiguousSet.cs~L359-374) andSymmetricExceptWith(~L403-425) walk the set backwards. For each element to drop, they call the publicRemove(item)(~L276-316).Removethen does the following for every element:HashSetagain.itemsfrom index 0 withcomparer.Equals, an interface call, until it rediscovers the item. The caller was already holding that item at indexi.Dropping k of n elements therefore costs O(n·k), which is O(n²) when most of the set goes.
HashSet<T>does the same operation in O(n).Measurements
Release build, net10, scratch MSTest:
Why it matters
ContiguousSetis the cache-friendly set in this package, and the reason to pick it is performance. A common bulk operation, such as filtering a set down to a small allow-list, freezes the calling thread for seconds at modest sizes.Suggested fix
Do each operation in a single compaction pass:
w. For eachi, either copyitems[i]toitems[w++](keep), or calluniquenessSet.Remove(items[i])(drop).items[w..Count)whenTmay hold references, then setCount = w.SymmetricExceptWith, then add the items that are only inother.This is O(n + m) and preserves insertion order.
Secondary:
InsertionOrderSet.IntersectWithandSymmetricExceptWith(InsertionOrderSet.cs~L284-353) callitems.RemoveAt(i)once per element. They are quadratic in the memmove: 48 ms at 50k and 189 ms at 100k when keeping the upper half. The same compaction pass fixes them.Add benchmarks or tests covering n = 100k for both types.
This is not covered by #82, which is about the bulk constructors and set operations of
OrderedSet/OrderedCollection/OrderedMap.