A nightly reconciliation job that cross-checks incoming orders against a list of active SKUs crept from "instant" to "noticeable," and the profiler pointed straight at a line I'd have sworn was free. It was a membership check. One Contains. The kind of thing you write without thinking because it reads like plain English: is this SKU allowed?
var allowed = GetActiveSkus(); // a List<Sku>
foreach (var order in incoming)
if (allowed.Contains(order.Sku))
keep.Add(order);
Reads fine. Does the right thing. And on a list of a few thousand SKUs with a hundred thousand orders flowing through, it was doing an absurd amount of work I never asked for.
The thing I forgot is what List<T>.Contains actually does. It has no index and no shortcut. It starts at the front and compares element by element until it finds a match or runs off the end. For an item that's present that's on average half the list. For an item that isn't present, a SKU that got retired say, it's the whole list, every time, because the list can't say "no" until it has checked all of them.
Making the list tell on itself
I didn't want to argue from a hunch, so I made the comparison count itself. I wrapped the SKU in a little struct whose Equals bumps a counter every time it runs:
readonly struct Sku(int value) : IEquatable<Sku>
{
public readonly int Value = value;
public bool Equals(Sku other)
{
Probe.Comparisons++;
return Value == other.Value;
}
public override int GetHashCode() => Value;
}
Then I ran the same check two ways over the same data, once against the List<Sku> and once against a HashSet<Sku> built from it, and counted. Five thousand allowed SKUs, a hundred thousand orders to check, with about half the incoming SKUs deliberately not in the allowlist so the misses do their worst. Best of seven, JIT warmed first. This is a container, not a lab bench, so I care about the ratios and not the exact millisecond.
// the list way
foreach (var sku in incoming)
if (allowed.Contains(sku)) matches++;
// the set way
var allowedSet = new HashSet<Sku>(allowed);
foreach (var sku in incoming)
if (allowedSet.Contains(sku)) matches++;
Allowlist size: 5,000
Incoming checks: 100,000
Matches agree: True (49,960)
List.Contains comparisons: 375,031,117 best: 808.6 ms
HashSet.Contains comparisons: 49,960 best: 1.1 ms
Comparison ratio: 7507x
Time ratio: 733x
Three hundred and seventy-five million comparisons to answer a hundred thousand yes/no questions. That works out to about 3,750 comparisons per question, which is exactly what you'd expect: a miss walks all 5,000, a hit walks around 2,500, and it's a coin-flip which one you get.
The set did the same work in 49,960 comparisons, which is identical to the match count. That's not luck. HashSet finds the right bucket by hash code and only calls Equals when something is actually sitting in that bucket to confirm it. Every miss got answered by the hash alone, with no comparison at all, so the only Equals calls left are the real hits.
Why the shape matters more than the speed
The 733x is the headline, but it's the wrong thing to fixate on, because it's tied to my specific sizes. Double the allowlist and the list version roughly doubles its work while the set barely moves. That's the actual problem with Contains in a loop: it's O(n×m), and both of those numbers tend to grow in production while nobody is looking. The version that was fine with 500 SKUs in testing is the one that falls over at 5,000 in March.
The fix is boring, which is the best kind. Build the set once, query it in the loop:
var allowedSet = allowed.ToHashSet(); // pay O(n) once
foreach (var order in incoming)
if (allowedSet.Contains(order.Sku)) // O(1) each
keep.Add(order);
When I wouldn't bother
One honest caveat, because "always use a HashSet" is how you end up making the opposite silly mistake. The set isn't free. You pay to build it, and every element has to be hashed. If the collection is tiny, or you only probe it once or twice, that build cost is the whole story and the plain list wins.
So I checked. Same hundred thousand lookups, but against a ten-item allowlist:
10-item allowlist, 100k checks -> List: 1.27 ms HashSet: 1.33 ms
The set is actually a hair slower there. At ten items, walking the list is so cheap that hashing is just ceremony. My rough rule: if the thing you're searching has more than a few dozen elements and you search it more than a couple of times, reach for the set. Below that, a List.Contains is clearer and costs nothing worth measuring.
If I had one opinion to leave you with, it's that this is the bug I personally re-introduce more than any other, because each individual Contains call looks completely innocent in review. Nobody flags "is this allowed?" The cost only exists in the loop wrapped around it, and the loop is usually three files away.
Here's the whole thing if you want to run the numbers yourself. New console project on the .NET 10 SDK, dotnet run -c Release:
using System.Diagnostics;
// A lookup key wrapping an int. The only reason it's a struct and not a
// plain int is so Equals can tell on itself: every comparison bumps a
// counter, which is how we watch List.Contains do O(n) work per call.
readonly struct Sku(int value) : IEquatable<Sku>
{
public readonly int Value = value;
public bool Equals(Sku other)
{
Probe.Comparisons++;
return Value == other.Value;
}
public override bool Equals(object? obj) => obj is Sku s && Equals(s);
public override int GetHashCode() => Value; // identity hash, stable buckets
}
static class Probe
{
public static long Comparisons;
}
static class Program
{
const int AllowedCount = 5_000;
const int IncomingCount = 100_000;
static void Main()
{
// Allowlist: even-numbered skus from 0..9998.
var allowed = new List<Sku>(AllowedCount);
for (int i = 0; i < AllowedCount; i++)
allowed.Add(new Sku(i * 2));
// Incoming skus across 0..9999, so roughly half are present (even)
// and half miss (odd). A miss walks the whole list before saying no.
var incoming = new Sku[IncomingCount];
var rng = new Random(1234);
for (int i = 0; i < IncomingCount; i++)
incoming[i] = new Sku(rng.Next(0, AllowedCount * 2));
var allowedSet = new HashSet<Sku>(allowed);
// Warm the JIT.
_ = CountWithList(allowed, incoming.AsSpan(0, 1000));
_ = CountWithSet(allowedSet, incoming.AsSpan(0, 1000));
var (listMatches, listComparisons, listMs) = BestOf(7, () => CountWithList(allowed, incoming));
var (setMatches, setComparisons, setMs) = BestOf(7, () => CountWithSet(allowedSet, incoming));
Console.WriteLine($"Allowlist size: {AllowedCount:N0}");
Console.WriteLine($"Incoming checks: {IncomingCount:N0}");
Console.WriteLine($"Matches agree: {listMatches == setMatches} ({listMatches:N0})");
Console.WriteLine();
Console.WriteLine($"List.Contains comparisons: {listComparisons,15:N0} best: {listMs,8:F1} ms");
Console.WriteLine($"HashSet.Contains comparisons:{setComparisons,15:N0} best: {setMs,8:F1} ms");
Console.WriteLine();
Console.WriteLine($"Comparison ratio: {(double)listComparisons / setComparisons:F0}x");
Console.WriteLine($"Time ratio: {listMs / setMs:F0}x");
}
static int CountWithList(List<Sku> allowed, ReadOnlySpan<Sku> incoming)
{
int matches = 0;
foreach (var sku in incoming)
if (allowed.Contains(sku)) // walks the list, every single call
matches++;
return matches;
}
static int CountWithSet(HashSet<Sku> allowed, ReadOnlySpan<Sku> incoming)
{
int matches = 0;
foreach (var sku in incoming)
if (allowed.Contains(sku)) // one hash, maybe one compare
matches++;
return matches;
}
static (int matches, long comparisons, double ms) BestOf(int rounds, Func<int> work)
{
double best = double.MaxValue;
int matches = 0;
long comparisons = 0;
for (int r = 0; r < rounds; r++)
{
Probe.Comparisons = 0;
var sw = Stopwatch.StartNew();
matches = work();
sw.Stop();
comparisons = Probe.Comparisons;
best = Math.Min(best, sw.Elapsed.TotalMilliseconds);
}
return (matches, comparisons, best);
}
}
What's the one that keeps biting you, this or something else that hides in a loop?
— still benchmarking things nobody asked me to time
Top comments (0)