Development C#

Why C# LINQ Except Builds Its Own Set Instead of Calling Contains

I spent part of a code review last week staring at a LINQ pipeline and asking a question that sounded simple. The pipeline builds an ordered list of work items by peeling off buckets with Except, and several of those buckets were materialized with ToArray. The question was whether they should be HashSet instead, since they feed straight into Except calls and the entire point of a set is a fast membership test.

The answer turned out to be no, and the reason is a piece of LINQ behavior that a lot of C# developers carry the wrong mental model of. Except doesn't call Contains on the collection it's handed. It builds its own set every time it runs, no matter what type the caller passes. Once that clicked, the materialization decisions fell out cleanly, and so did a separate point about when to materialize a query at all.

A Pipeline Where Order Matters

Here's the code, stripped down. A source sequence gets sorted into priority order, then buckets are peeled off and excluded from each other so they don't overlap, then everything is concatenated back into one ordered sequence.

// Already in priority order: earlier means higher priority.
var sortedItems = source
    .Where(IsRelevant)
    .OrderBy(x => x.QueueTime)
    .ToArray();

var topPriority = sortedItems.Where(IsUrgent).ToArray();
var everythingElse = sortedItems.Except(topPriority);

var ordering = topPriority.Concat(everythingElse);

Two things are going on at once. The position of an item in the sequence carries meaning, because earlier means it gets scheduled sooner. And Except is doing set subtraction to keep everythingElse from re-including the items already in topPriority. Both of those facts matter for the container question later.

Deferred Execution and the Single-Enumeration Trap

A LINQ query is a recipe, not a result. Where, Select, Except, and friends return lazy iterators that do nothing until something enumerates them. Calling .ToArray() or .ToList() runs the recipe once and keeps the result. Left lazy, the recipe runs again on every enumeration, re-reading the source each time.

The original code left a couple of these queries lazy with a comment along the lines of "not materialized because it is only enumerated once". That reasoning holds right up until someone adds a second consumer and the whole Where and Except chain silently runs a second time. Worse, if the source is a concurrent collection that is being mutated on another thread, the second enumeration can observe a different set of items than the first, and the result is internally inconsistent in a way no single read would ever produce.

My opinion is that materializing a query is usually a correctness decision rather than a performance one. The array is a snapshot. It freezes the source at one moment and removes the "must only ever enumerate this once" rule that the next reader has no way of seeing. That framing matters for the rest of this post, because it's the opposite of the framing the original comments used.

The HashSet Question

So, back to the buckets. They feed Except. Surely the right container is a HashSet. Except needs to test membership, and HashSet.Contains is O(1) while array.Contains is O(n). Materialize the buckets to sets and the subtraction gets faster. That was the intuition, and it's wrong, and the wrong version is reasonable enough to be worth pulling apart slowly.

What Except Actually Does

Here is the iterator, close to how it appears in the .NET source. Older framework versions used an internal Set<T> type, modern .NET uses HashSet<T> directly, but the algorithm is the same.

private static IEnumerable<TSource> ExceptIterator<TSource>(
    IEnumerable<TSource> first,
    IEnumerable<TSource> second,
    IEqualityComparer<TSource>? comparer)
{
    var set = new HashSet<TSource>(comparer);

    foreach (TSource element in second)
    {
        set.Add(element);
    }

    foreach (TSource element in first)
    {
        if (set.Add(element))
        {
            yield return element;
        }
    }
}

Read the first line of the body. It constructs a brand new HashSet and then copies every element of second into it. It never asks second whether it already is a set. Pass it a HashSet and that set gets enumerated, element by element, into a fresh one. The caller now pays for two sets instead of one. The optimization people reach for makes things slightly worse.

Three Reasons for the Fresh Set

This is not laziness in the BCL. There are three concrete reasons Except can't reuse the set it's given, and any one of them is enough.

First, the static type of the argument is IEnumerable<T>. The method has no compile-time knowledge that a set was passed, and it deliberately doesn't do a runtime is HashSet<T> check. Even if it did, the next reason would defeat it.

Second, the comparer almost never matches. Except has to answer membership questions using its own equality, either the IEqualityComparer<T> the caller passed or EqualityComparer<T>.Default. The HashSet handed in was built with its own comparer, an independent choice. Pass a case-insensitive HashSet<string> into an Except call that uses ordinal equality and the set's buckets are organized under the wrong hashing, so its Contains would give the wrong answer. The only way Except can guarantee its own comparer is used is to build the lookup itself. That's also why Except has a comparer overload at all.

Third, the single set has to deduplicate the first sequence too. Look again at the second loop. set.Add(element) returns false both for elements that came from second (already excluded) and for elements already emitted from first (already seen). That's what gives Except its distinct-output guarantee. A caller-supplied set couldn't do this job without Except mutating it, adding every yielded element into the caller's collection as a side effect, which would be an unacceptable thing to do to an argument.

The Asymmetry Between Contains and Except

Here is the asymmetry that makes the wrong mental model so easy to hold. Enumerable.Contains really does delegate.

public static bool Contains<TSource>(this IEnumerable<TSource> source, TSource value)
{
    if (source is ICollection<TSource> collection)
    {
        return collection.Contains(value);
    }
    // ... fallback linear scan
}

Contains checks for ICollection<T> and calls the collection's own Contains. Pass a HashSet and the O(1) lookup is genuine. That's exactly the optimization people expect Except to have. But the set operators, Except, Intersect, Union, and Distinct, all roll their own internal set and never delegate. So the intuition is correct for Contains and wrong for Except, and the two methods live a few lines apart in the same Enumerable class. No wonder the model leaks across.

Choosing Arrays Over Sets

Once Except is known to ignore the container type, the choice for those buckets is easy.

For a bucket used only as the second argument to Except, a HashSet buys nothing, because Except rebuilds its own set from it on every enumeration. An array is fine.

For a bucket that is also concatenated into the ordered output, a HashSet is actively wrong. HashSet<T> doesn't guarantee enumeration order. It happens to enumerate in insertion order while no removals occur, but Microsoft documents the order as unspecified and not to be relied on. The whole purpose of the pipeline is the priority ordering, so trading a documented, stable order for an implementation detail would be a real bug. An array preserves order, so an array it is.

There was exactly one spot where a real set would have helped, a Contains call inside a loop over one of the buckets, which on an array is O(n) per iteration and O(n squared) over the loop. But that same bucket had to keep its order for the concatenation, so I would have needed both an ordered array and a parallel set for the lookups. For a bucket holding a handful of items, that's not worth the second container.

The Law of Small Numbers

The original comments justified leaving queries lazy to avoid an allocation, and justified reaching for a set on Except performance. Both of those are performance rationales, and every collection in this pipeline holds a handful of items. At that size the performance difference between an array and a set, or between one allocation and none, is nothing anyone could measure.

The law of small numbers, in the Tversky and Kahneman sense, is about people over-trusting conclusions drawn from tiny samples. I'm borrowing it loosely for code. Micro-optimizing allocations and lookups on tiny collections is reasoning hard about a cost that doesn't exist at this scale, while quietly ignoring the cost that does, which is correctness and the next person to read the method.

So the priority inverts. Materialize to snapshot a mutable source and to delete the unwritten "only enumerate this once" rule, not to save an allocation. Pick the container for correctness, which here means preserving order, not for an Except speedup the framework doesn't actually provide. The saved allocation is meaningless at ten items. The accidental re-enumeration over a concurrent collection is a bug that doesn't care how small the collection is.

Practical Takeaways

Conclusion

The surprising fact is small and specific. Except ignores the concrete type of its argument and builds a fresh set every time, for reasons that are sound once they're clear, and it sits right next to Contains, which does the opposite. The broader point is the one I keep coming back to in reviews. On small collections, the question is almost never "is this fast enough". It's "is this correct, and will the next reader understand why". Materialize for that, and choose the container for that.

All of this can be confirmed in a few minutes with SharpLab, which shows the iterator and the IL, or by reading the source linked below.

References