OrderedSet/OrderedCollection/OrderedMap bulk construction is O(n^2), so OrderedSet.IsSubsetOf/SetEquals/IntersectWith on a 1M-element input take over a minute

[matt-edmondson]

What's wrong

The sorted containers fill their backing List<T> from a sequence one element at a time, using a binary search followed by List.Insert. Each insert shifts the tail of the list, so building from n unsorted or reverse-sorted items costs O(n^2) element moves:

• Containers/OrderedSet.cs:139-177: both OrderedSet(IEnumerable<T>) constructors call Add per item
• Containers/OrderedCollection.cs:149-187: both OrderedCollection(IEnumerable<T>) constructors do the same
• Containers/OrderedMap.cs:181 and :208: both OrderedMap(IDictionary<,>) constructors do the same

The biggest problem is in OrderedSet, where the cost leaks into query methods. ToComparerSet (OrderedSet.cs:316) builds a temporary OrderedSet from the argument through that constructor, and IntersectWith, SymmetricExceptWith, IsSubsetOf, IsProperSubsetOf, IsProperSupersetOf and SetEquals (OrderedSet.cs:355, 397, 435, 462, 476, 503) all call it. A read-only check such as set.IsSubsetOf(someArray) is therefore quadratic in the size of someArray. HashSet<T> and SortedSet<T> do the same work in O(n) or O(n log n).

Reproduction

Console app (net10, Release) referencing Containers/Containers.csproj:

using System.Diagnostics;
using ktsu.Containers;

int n = 1_000_000;
int[] desc = Enumerable.Range(0, n).Reverse().ToArray();
OrderedSet<int> s = new(Enumerable.Range(0, n)); // sorted input, so each Add appends

Stopwatch sw = Stopwatch.StartNew();
bool b = s.IsSubsetOf(desc);
Console.WriteLine($"OrderedSet.IsSubsetOf(descending array): {sw.ElapsedMilliseconds} ms -> {b}");

HashSet<int> hs = new(Enumerable.Range(0, n));
sw.Restart(); hs.IsSubsetOf(desc);
Console.WriteLine($"HashSet.IsSubsetOf: {sw.ElapsedMilliseconds} ms");

Observed:

OrderedSet.IsSubsetOf(descending array): 65118 ms -> True
HashSet.IsSubsetOf: 35 ms

Construction timings from the same machine (random input seeded with Random(42), or reverse-sorted input):

n	OrderedSet ctor (random)	OrderedSet ctor (desc)	OrderedSet.SetEquals(desc)	OrderedCollection ctor (desc)	OrderedMap ctor	SortedSet ctor
50,000	55 ms	94 ms	109 ms	103 ms	229 ms	20 ms
200,000	801 ms	1575 ms	1592 ms	1611 ms	3232 ms	27 ms

Quadrupling n makes each operation about 16 times slower, which is quadratic growth.

Why it matters

These are the library's "high-performance" sorted containers, and the set-comparison methods look like cheap queries. A caller who checks IsSubsetOf or SetEquals against an ordinary array or list with a few hundred thousand items can stall a thread for seconds or minutes. Building an OrderedSet, OrderedCollection or OrderedMap from an existing unsorted collection is also a common operation, and it has the same cost.

Suggested fix / acceptance criteria

• Bulk constructors: copy the input into the list, then run a stable sort with the container's comparer. List.Sort is unstable, so use either a merge sort or a sort keyed on (item, original index). For OrderedSet, dedupe adjacent equal elements and keep the first, which matches what Add does today. For OrderedMap, throw on adjacent equal keys, as Add does. This is O(n log n).
• OrderedSet set operations: stop building a full OrderedSet for the argument. When other is an OrderedSet<T> with the same comparer, walk both sorted lists together (a linear merge). Otherwise use the stable sort-and-dedupe path above, or mark matches with a bool[] indexed through BinarySearch (the approach HashSet.CheckUniqueAndUnfoundElements takes). IsSupersetOf and Overlaps are already O(m log n) and can stay as they are.
• A stable sort also keeps equal elements in their original order, which would resolve the reordering reported in OrderedCollection.Clone() and GetRange() reorder elements that compare equal, so a clone isn't sequence-equal to its source #80 for Clone/GetRange.
• Add tests or benchmarks showing that construction from 1,000,000 reverse-sorted items and IsSubsetOf/SetEquals on a 1,000,000-element array finish in well under a second, with the existing semantics tests still passing: duplicates dropped in OrderedSet, first occurrence wins, custom comparer honoured, and OrderedMap throws on a duplicate key.

[matt-edmondson]

Triage

• Category: Improvement (performance)
• Priority: Medium. Results are correct, but bulk construction and the OrderedSet set-comparison methods are O(n²). A 1M-element IsSubsetOf takes more than a minute, which is a real stall for callers who expect a cheap query.
• Area / suggested assignee: bulk constructors in OrderedSet.cs, OrderedCollection.cs, OrderedMap.cs, plus OrderedSet.ToComparerSet and the set operations that use it. Owner: @matt-edmondson
• Duplicates / in progress: not a duplicate. The stable-sort fix would also resolve OrderedCollection.Clone() and GetRange() reorder elements that compare equal, so a clone isn't sequence-equal to its source #80 (Clone/GetRange reordering equal elements), so the two could be fixed together. No open PR covers either one.
• Next step: stable sort plus dedupe in the bulk constructors, a linear merge for the OrderedSet-vs-OrderedSet set ops, and a 1M-element benchmark or test.

---

Generated by Claude Code