The allocation tax: why correct, O(n) C# can still be slow

You fixed the Big-O. The nested loop is gone, the HashSet is in, the method is a clean O(n). And it's still slower than it should be. The profiler doesn't point at any one line. CPU isn't pegged. But every so often the whole thing pauses, and your p99 latency has a lump in it that no amount of algorithmic cleverness explains.

That's the allocation tax. In a managed runtime, you don't pay for memory when you free it; you pay later, when the garbage collector walks the heap to figure out what's still alive. Every object you allocate is a deferred bill, and a hot path that allocates carelessly runs up a balance the GC eventually collects on, usually at the worst moment. Correct, O(n), idiomatic code can still be slow because of how much garbage it makes per call.

Where the garbage comes from

The frustrating part is that the worst offenders are the prettiest code. Modern C# makes it effortless to allocate without noticing. A few of the usual suspects:

• LINQ chains. Every .Where().Select().ToList() allocates iterator state machines and an intermediate buffer, sometimes several.
• String concatenation in a loop. Strings are immutable, so result += part allocates a brand new string every iteration and throws the old one away.
• Boxing. Pass an int where an object is expected (logging, old APIs, non-generic collections) and the value gets wrapped on the heap.
• Closures. A lambda that captures a local variable allocates a hidden class to hold it.
• params arrays. Every call that passes arguments to a params object[] method allocates an array to carry them.

None of these are bugs. None of them show up in a code review as wrong. They're just spending you don't see, and at scale the spending adds up to GC pauses. What each pause costs depends on where in the generational heap your garbage ends up.

Gen 0

collected constantly · well under 1 ms

Gen 1

survivors wait here

Gen 2

full-heap pause · tens of ms and up

Large object heap

85,000+ bytes · collected only with gen 2

A before that looks completely fine

Here's a method that takes a list of order line items and builds a summary string of the ones over a threshold. It's correct, it's readable, and a reviewer would approve it without comment:

public string Summarize(List<LineItem> items, decimal threshold)
{
    var expensive = items
        .Where(i => i.Price > threshold)
        .Select(i => $"{i.Sku}: {i.Price:C}")
        .ToList();

    var summary = "";
    foreach (var line in expensive)
    {
        summary += line + Environment.NewLine;
    }

    return summary;
}

Count what this allocates on a list of 50,000 items. The Where and Select each allocate iterator objects, the interpolated string allocates a new string per matching item, ToList allocates a backing array, and then the summary += loop allocates a fresh, ever-growing string on every iteration. For 10,000 matches you produce roughly 10,000 throwaway intermediate strings, each larger than the last, before you keep the final one.

The wall-clock time is dominated less by the work and more by the GC churning through the wreckage.

The after: same output, far less garbage

You don't need spans or anything exotic here. Two changes do almost all of it: drop the intermediate list, and stop building the string by concatenation.

public string Summarize(List<LineItem> items, decimal threshold)
{
    var summary = new StringBuilder();

    foreach (var item in items)
    {
        if (item.Price > threshold)
        {
            summary.Append(item.Sku)
                   .Append(": ")
                   .Append(item.Price.ToString("C"))
                   .Append(Environment.NewLine);
        }
    }

    return summary.ToString();
}

The LINQ chain and its iterators are gone, replaced by a single foreach. The intermediate List is gone. The N throwaway strings from += collapse into one StringBuilder that grows its internal buffer a handful of times and produces exactly one final string. Same result, a fraction of the allocations.

The shape of the win on 50,000 items, illustratively:

Version	Allocated (roughly)	Time (illustrative)
LINQ + string +=	~2 GB	~190 ms
foreach + StringBuilder	~1 MB	~1 ms

The CPU was never the bottleneck. The garbage was. And notice the algorithm didn't change at all: both versions are O(n). This is a different axis entirely.

"Make it correct, then make it fast" leaves out a step in .NET. Correct, then not wasteful, then fast. The middle step is where allocation lives, and it's the one most developers skip because nothing tells them they're paying.

You can't fix what you can't see

That last line is the whole problem. Wall-clock time you'll eventually notice. Allocation you almost never will, because the cost is deferred and diffuse: a little extra GC here, a slightly longer pause there, spread across thousands of calls. No single run feels wrong. The bill arrives as a vague "the service got slower" that nobody can pin to a line.

This is exactly why getting good at allocation-aware C# is hard without the right feedback loop. You need something that puts a number on the garbage, per run, right next to the code, so the cost stops being invisible.

That's a deliberate choice in how Katabench grades. Every test reports bytes allocated on the managed heap, not just wall-clock time, so you feel allocation pressure directly. You submit the LINQ-and-+= version, see a couple of gigabytes against a budget, rewrite it to StringBuilder, and watch the number fall through the floor on the same input. The details of what's measured and how are written up in the grading docs, because clean numbers only mean something if you know exactly how they're produced.

That before-and-after, felt as a real allocation figure rather than an abstract "this is wasteful," is how you start writing low-garbage C# by reflex instead of by audit. Reading about boxing and closures teaches you the vocabulary; watching your own megabytes evaporate teaches you the instinct.

All seven tracks, including the full hidden performance suites with allocation reporting, are on Pro. Go make the garbage visible, and then make it disappear.