My Struct Key Boxed Itself Two Million Times

I had a cache keyed on a little struct. Three ints bundled together, nothing to it, the kind of value type you reach for when a plain tuple feels too anonymous. Over a batch of work I'd look things up in a Dictionary keyed by that struct a couple million times, and one day that lookup loop showed up in an allocation profile. Which made no sense to me. A dictionary lookup doesn't allocate. It hashes a key, walks a bucket, compares. Where's the garbage coming from?

The garbage was the key. Every lookup was boxing it, and I'd never typed a new to make that happen.

Who compares your keys

When you put something in a Dictionary<TKey, TValue>, the dictionary needs two things from the key: a hash code, and a way to tell two keys apart. It gets both from EqualityComparer<TKey>.Default, and which comparer that resolves to depends on your type. I'd never once thought about it, so I had the sample print it:

PlainKey -> ObjectEqualityComparer`1
FastKey  -> GenericEqualityComparer`1

Two structs, same three int fields, landing on different comparers. The only thing separating them is that one implements IEquatable<T> and the other doesn't.

GenericEqualityComparer<T> is the one you want. It calls your IEquatable<T>.Equals(T) directly, taking the struct by value. No boxing, no reflection.

ObjectEqualityComparer<T> is the fallback for everything else, and it's where my struct landed. It only knows the two methods every object has: object.GetHashCode() and object.Equals(object). Both live on object, so to call them on a struct the runtime has to box it first. And since I'd never written those methods myself, the ones it ends up calling are ValueType's defaults, which work out your fields by reflection at runtime. So every lookup boxed my key to hash it, then boxed it again to compare it.

The bill

Here's what that cost, next to the same struct with the methods filled in. Two million lookups into a two-hundred-thousand-entry dictionary, keys built up front so only the lookups land on the scorecard, best of five in a cloud container. I care about the ratio more than the millisecond:

PlainKey (default equality)      192,000,040 bytes    695.8 ms
FastKey (IEquatable<T>)                    40 bytes    236.5 ms

A hundred and ninety-two megabytes of boxes, for lookups that should allocate nothing at all. That works out to about ninety-six bytes of garbage per lookup, a few short-lived boxes each time, all of it piling into gen0 for the collector to deal with later. And close to three times slower on the clock, because reflection-based equality isn't cheap even before you count the allocations. The checksums matched, so both versions found the same entries and did the same work. One just made a mess doing it.

The fix is three methods, or one keyword

Spelling it out is mechanical:

struct FastKey(int x, int y, int z) : IEquatable<FastKey>
{
    public readonly int X = x, Y = y, Z = z;
    public bool Equals(FastKey other) => X == other.X && Y == other.Y && Z == other.Z;
    public override bool Equals(object? obj) => obj is FastKey o && Equals(o);
    public override int GetHashCode() => HashCode.Combine(X, Y, Z);
}

The IEquatable<FastKey>.Equals is the line that moves you onto the fast comparer. The object.Equals override keeps the two agreeing with each other, which the analyzer nags you about anyway. And HashCode.Combine saves you from hand-rolling a hash that distributes badly.

Or skip all of it and let the compiler do the typing: record struct FastKey(int X, int Y, int Z) generates IEquatable<T>, both Equals methods, and a GetHashCode for you. That's what I reach for now. If a value type has any chance of becoming a dictionary key, a HashSet member, or the input to a LINQ Distinct or Contains, I make it a record struct from the start and stop thinking about it.

When it doesn't matter

If you never use the struct as a key and never compare two of them, none of this ever fires, and adding the methods is just noise for the next person reading the file. A struct that's pure data moving from here to there doesn't need an equality contract. The trap is the quiet upgrade: a value type that was perfectly fine as a plain bag of fields, right up until someone drops it into a dictionary and the boxing starts without a single compiler warning. Nothing tells you. The code builds, the lookups return the right answers, and the only evidence is a line in an allocation graph you weren't looking at.

One caveat on the fix itself. If you hand-write GetHashCode, keep it away from any field you plan to mutate while the struct is sitting in a hash-based collection. A key whose hash changes after it's stored is a different bug, and a nastier one to find. For keys I keep every field readonly, which the sample does.

Normally I'd link the runnable sample on GitHub, but the sandbox this ran in couldn't push to my samples repo this time, so here's the whole thing. Drop it in a net10.0 console project and dotnet run -c Release:

using System.Diagnostics;

const int Distinct = 200_000;
const int Lookups = 2_000_000;

var plainKeys = new PlainKey[Distinct];
var fastKeys = new FastKey[Distinct];
for (int i = 0; i < Distinct; i++)
{
    plainKeys[i] = new PlainKey(i, i * 3, i * 7);
    fastKeys[i] = new FastKey(i, i * 3, i * 7);
}

var plainMap = new Dictionary<PlainKey, long>(Distinct);
var fastMap = new Dictionary<FastKey, long>(Distinct);
for (int i = 0; i < Distinct; i++)
{
    plainMap[plainKeys[i]] = i;
    fastMap[fastKeys[i]] = i;
}

var rng = new Random(99);
int[] order = new int[Lookups];
for (int i = 0; i < Lookups; i++) order[i] = rng.Next(Distinct);

long LookupPlain()
{
    long hits = 0;
    for (int i = 0; i < Lookups; i++)
        if (plainMap.TryGetValue(plainKeys[order[i]], out long v)) hits += v;
    return hits;
}

long LookupFast()
{
    long hits = 0;
    for (int i = 0; i < Lookups; i++)
        if (fastMap.TryGetValue(fastKeys[order[i]], out long v)) hits += v;
    return hits;
}

(long bytes, double ms, long checksum) Measure(Func<long> run)
{
    long bestBytes = long.MaxValue;
    double bestMs = double.MaxValue;
    long checksum = 0;
    for (int r = 0; r < 5; r++)
    {
        GC.Collect();
        GC.WaitForPendingFinalizers();
        GC.Collect();
        long before = GC.GetAllocatedBytesForCurrentThread();
        var sw = Stopwatch.StartNew();
        checksum = run();
        sw.Stop();
        long bytes = GC.GetAllocatedBytesForCurrentThread() - before;
        if (bytes < bestBytes) bestBytes = bytes;
        if (sw.Elapsed.TotalMilliseconds < bestMs) bestMs = sw.Elapsed.TotalMilliseconds;
    }
    return (bestBytes, bestMs, checksum);
}

Console.WriteLine("Comparer the runtime picks for each key:");
Console.WriteLine($"  PlainKey -> {EqualityComparer<PlainKey>.Default.GetType().Name}");
Console.WriteLine($"  FastKey  -> {EqualityComparer<FastKey>.Default.GetType().Name}");

_ = LookupPlain();
_ = LookupFast();

var plain = Measure(LookupPlain);
var fast = Measure(LookupFast);

Console.WriteLine($"{"PlainKey",-28}{plain.bytes,16:N0} bytes{plain.ms,10:F1} ms");
Console.WriteLine($"{"FastKey",-28}{fast.bytes,16:N0} bytes{fast.ms,10:F1} ms");
Console.WriteLine($"checksums: {plain.checksum} / {fast.checksum}");

struct PlainKey(int x, int y, int z)
{
    public readonly int X = x, Y = y, Z = z;
}

struct FastKey(int x, int y, int z) : IEquatable<FastKey>
{
    public readonly int X = x, Y = y, Z = z;
    public bool Equals(FastKey other) => X == other.X && Y == other.Y && Z == other.Z;
    public override bool Equals(object? obj) => obj is FastKey o && Equals(o);
    public override int GetHashCode() => HashCode.Combine(X, Y, Z);
}

So, do you default your small value types to record struct, or only reach for equality once something starts leaking?

— still out here benchmarking things nobody asked about