Where C# Spends Its Time

Most .NET performance problems are one of four things: building strings in a loop, allocating in a hot path, the wrong collection, and measuring the JIT's warm-up instead of the code.

using System.Diagnostics;
using System.Text;

const int n = 40_000;
int checksum = 0;                      // used, so neither loop can be removed

var clock = Stopwatch.StartNew();
string concatenated = "";
for (int i = 0; i < n; i++) concatenated += 'x';
long plusEquals = clock.ElapsedMilliseconds;
checksum += concatenated.Length;

clock.Restart();
var builder = new StringBuilder();
for (int i = 0; i < n; i++) builder.Append('x');
string built = builder.ToString();
long stringBuilder = clock.ElapsedMilliseconds;
checksum += built.Length;

Console.WriteLine($"+=            {plusEquals}ms");
Console.WriteLine($"StringBuilder {stringBuilder}ms");
Console.WriteLine($"builder is faster: {stringBuilder < plusEquals}");
Console.WriteLine($"both built {checksum / 2} characters");

A string is immutable, so s += "x" allocates a new one and copies everything so far: the loop is quadratic. StringBuilder writes into one buffer that grows. (A + in a single expression is compiled to string.Concat already - it is only the loop that is the problem.)

Allocation is the thing to watch

The collector is fast, but the cheapest allocation is the one that never happens. Structs, spans and pooled buffers are how you avoid them.

using System.Diagnostics;

const int n = 2_000_000;
var clock = Stopwatch.StartNew();

// Boxing: every int becomes an object on the heap.
long boxedTotal = 0;
for (int i = 0; i < n; i++)
{
    object boxed = i;                   // an allocation, every iteration
    boxedTotal += (int)boxed;
}
long boxedMs = clock.ElapsedMilliseconds;

clock.Restart();
long plainTotal = 0;
for (int i = 0; i < n; i++) plainTotal += i;
long plainMs = clock.ElapsedMilliseconds;

Console.WriteLine($"boxed  {boxedMs}ms -> {boxedTotal}");
Console.WriteLine($"plain  {plainMs}ms -> {plainTotal}");
Console.WriteLine($"same answer: {boxedTotal == plainTotal}");
Console.WriteLine($"gen 0 collections: {GC.CollectionCount(0)}");

The same effect hides in older APIs: a non-generic ArrayList, string.Format with value types, and any interface call on a struct all box. Generic collections do not, which is the main reason List<int> replaced ArrayList.

The collection is the algorithm

using System.Diagnostics;

const int n = 20_000;
List<int> haystack = Enumerable.Range(0, n).ToList();

var clock = Stopwatch.StartNew();
int foundByScan = 0;
for (int i = 0; i < n; i++) if (haystack.Contains(i)) foundByScan++;
long scan = clock.ElapsedMilliseconds;

var set = haystack.ToHashSet();
clock.Restart();
int foundByHash = 0;
for (int i = 0; i < n; i++) if (set.Contains(i)) foundByHash++;
long hash = clock.ElapsedMilliseconds;

Console.WriteLine($"List.Contains    {scan}ms");
Console.WriteLine($"HashSet.Contains {hash}ms");
Console.WriteLine($"same answer: {foundByScan == foundByHash}");

// And if the size is known, say so: a List that grows copies its array each
// time it doubles.
clock.Restart();
var grows = new List<int>();
for (int i = 0; i < 2_000_000; i++) grows.Add(i);
long growing = clock.ElapsedMilliseconds;

clock.Restart();
var sized = new List<int>(2_000_000);
for (int i = 0; i < 2_000_000; i++) sized.Add(i);
Console.WriteLine($"growing {growing}ms, presized {clock.ElapsedMilliseconds}ms");

LINQ costs something, and it is usually worth it

Each LINQ stage is an iterator object and a delegate call per element. For a hot inner loop over millions of items that shows up; for the other 99% of code the readability is worth more than the nanoseconds.

using System.Diagnostics;

int[] source = Enumerable.Range(1, 5_000_000).ToArray();

var clock = Stopwatch.StartNew();
long linq = source.Where(n => n % 2 == 0).Select(n => (long)n * 2).Sum();
long linqMs = clock.ElapsedMilliseconds;

clock.Restart();
long manual = 0;
foreach (int n in source)
{
    if (n % 2 == 0) manual += (long)n * 2;
}

Console.WriteLine($"LINQ  {linqMs}ms -> {linq}");
Console.WriteLine($"loop  {clock.ElapsedMilliseconds}ms -> {manual}");
Console.WriteLine($"same answer: {linq == manual}");
Console.WriteLine("measure before rewriting readable code into a loop");

Why your first measurement is wrong

.NET compiles IL to machine code the first time a method runs, and tiered compilation then recompiles the hot ones with better optimisation. Early iterations measure the JIT, not the code.

using System.Diagnostics;

for (int round = 1; round <= 5; round++)
{
    var clock = Stopwatch.StartNew();
    long total = 0;
    for (int i = 0; i < 5_000_000; i++) total += Work(i);
    Console.WriteLine($"round {round}: {clock.ElapsedMilliseconds}ms ({total})");
}

Console.WriteLine("the same loop five times - and the first is not like the last");

static long Work(int i) => (i % 7) * 3L;

Warm up before timing, run several rounds, keep the result so nothing can be optimised away - or use BenchmarkDotNet, which handles warm-up, statistics and the dead-code problem properly, and is the only thing worth quoting in an argument.

Measure the program, not your guess

Before optimising anything, find where the time goes: dotnet-counters for live metrics, dotnet-trace for a profile, and the GC counters for allocation pressure. Most "slow .NET" turns out to be an N+1 query, a lock everything queues behind, a cache with no eviction, or an algorithm that is quadratic in the input - none of them found by staring at the code.

What to take away

• StringBuilder in a loop; += on strings is quadratic.
• Boxing allocates: generics, structs and spans are how you avoid it.
• HashSet/Dictionary for membership; presize a List<T> when you know the size.
• LINQ costs a delegate call per element - worth it except in a hot inner loop.
• The JIT needs warm-up; use BenchmarkDotNet for anything you will act on.
• Profile first: it is usually a query, a lock, a cache, or the algorithm.