I had an array of two million ints and I wanted a List<long> of them, each one doubled. So I wrote the loop you'd write without thinking: new list, one Add per item, done. Then that path started leaving little bumps in the gen0 graph, and I couldn't work out why a plain Add loop would bother the garbage collector at all. It's a loop. It adds things.
The counter has never once flattered me, though, so I went and looked.
The list was rebuilding itself the whole way up
A List<T> doesn't know how big it's going to get, so it starts small and grows by doubling. Every time it fills, it allocates a new, bigger backing array, copies everything over, and lets the old array go. Fine in isolation. But I was going from empty to two million, which means a lot of doublings, and each one leaves behind an array the GC now has to clean up.
I didn't want to guess at how many, so I counted:
var list = new List<long>();
int lastCapacity = list.Capacity;
int grows = 0;
for (int i = 0; i < source.Length; i++)
{
list.Add(source[i]);
if (list.Capacity != lastCapacity)
{
grows++;
lastCapacity = list.Capacity;
}
}
Default list reallocated its backing array 20 times (final capacity 2,097,152).
Twenty times. Twenty arrays allocated and thrown away to build one list, and I already knew from the start that I wanted exactly two million slots.
Putting a number on it
I measured it the way I measure everything: the smallest honest version, best-of-seven, GC.GetAllocatedBytesForCurrentThread() around each run with a checksum so a wrong answer couldn't sneak through. The source array gets built once up front so it never lands on the scorecard.
static long FillNoCapacity(int[] source)
{
var list = new List<long>();
for (int i = 0; i < source.Length; i++)
list.Add((long)source[i] * 2);
return list.Count;
}
static long FillWithCapacity(int[] source)
{
var list = new List<long>(source.Length); // we know the count
for (int i = 0; i < source.Length; i++)
list.Add((long)source[i] * 2);
return list.Count;
}
new List<long>() + Add loop 33,554,952 bytes 11.2 ms
new List<long>(count) + Add loop 16,000,096 bytes 8.2 ms
EnsureCapacity(count) + Add loop 16,000,096 bytes 8.2 ms
The finished list is 16 MB either way, because two million longs is 16 MB of data and there's no getting around that. The extra 17-and-a-half megabytes in the first row is pure waste: it's the nineteen smaller arrays the list allocated, copied out of, and discarded on its way up to the right size. I was paying to build the list twice over and hand the second copy straight to the collector.
The fix is one argument. new List<long>(count) sizes the backing array once and never grows again. EnsureCapacity(count) does the same thing if you've already got the list in hand. Both drop you to a single 16 MB allocation.
The framework already does this for you (sometimes)
Here's the part that actually changed how I write this stuff. I went hunting for other places I'd been filling lists blind, and found that some of them were already fine.
// pre-sizes for you
var list = source.Select(x => (long)x * 2).ToList();
// does not
var list = new List<long>();
list.AddRange(source.Where(x => true).Select(x => (long)x * 2));
Select(...).ToList() 16,000,144 bytes 8.2 ms
AddRange(lazy Where/Select) 33,555,056 bytes 14.1 ms
ToList() over a Select on an array lands at 16 MB. It can see through the projection to the array underneath, ask it how many elements there are, and size the result in one go. But the moment I put a Where in the chain and fed it to AddRange, it jumped right back to 33 MB. A Where can't promise how many items will survive the predicate, so there's no count to pre-size from, and the list is back to doubling its way up. Same destination, same twenty reallocations I started with.
So "use LINQ and don't worry about it" isn't quite the rule. It depends on whether the thing you're materializing can still be counted by the time the list asks.
When I actually bother
My honest take is that this is a narrow optimization and I keep it narrow. I pre-size when I already hold the count: an array's Length, an ICollection's Count, a row count I just read off a query. That's free information and it's silly to throw it away.
What I don't do is pre-size on a guess. If you don't really know the count and you size to some generous upper bound, you can over-allocate and waste more than the reallocations ever would. A list sized for a million that only ever gets a thousand items is sitting on 8 MB of empty backing array for no reason. The doublings are only expensive because they pile up at scale, too; fill a list of twenty and it reallocates maybe four times and the whole thing is a rounding error nobody should lose sleep over.
And notice the timing was the quieter win. Pre-sizing shaved the wall clock from around eleven milliseconds to eight, which is real but modest. This isn't a lab, it's a cloud container with workstation GC, so I trust the allocation ratio a lot more than the exact milliseconds. The allocation number is where you feel this one, usually as collection pressure somewhere downstream of the code that looked innocent.
Here's the whole thing if you want to run it yourself:
using System.Diagnostics;
const int Count = 2_000_000;
int[] source = new int[Count];
for (int i = 0; i < Count; i++)
source[i] = i;
Console.WriteLine($".NET {Environment.Version}, workstation GC, filling a list of {Count:N0} longs\n");
CountReallocations(source);
Console.WriteLine();
Measure("new List<long>() + Add loop", () => FillNoCapacity(source));
Measure("new List<long>(count) + Add loop", () => FillWithCapacity(source));
Measure("EnsureCapacity(count) + Add loop", () => FillEnsureCapacity(source));
Measure("Select(...).ToList() ", () => FillToListOverSelect(source));
Measure("AddRange(lazy Where/Select) ", () => FillAddRangeLazy(source));
static void CountReallocations(int[] source)
{
var list = new List<long>();
int lastCapacity = list.Capacity, grows = 0;
for (int i = 0; i < source.Length; i++)
{
list.Add(source[i]);
if (list.Capacity != lastCapacity) { grows++; lastCapacity = list.Capacity; }
}
Console.WriteLine($"Default list reallocated its backing array {grows} times (final capacity {list.Capacity:N0}).");
}
static long FillNoCapacity(int[] source)
{
var list = new List<long>();
for (int i = 0; i < source.Length; i++) list.Add((long)source[i] * 2);
return list.Count;
}
static long FillWithCapacity(int[] source)
{
var list = new List<long>(source.Length);
for (int i = 0; i < source.Length; i++) list.Add((long)source[i] * 2);
return list.Count;
}
static long FillEnsureCapacity(int[] source)
{
var list = new List<long>();
list.EnsureCapacity(source.Length);
for (int i = 0; i < source.Length; i++) list.Add((long)source[i] * 2);
return list.Count;
}
static long FillToListOverSelect(int[] source) =>
source.Select(x => (long)x * 2).ToList().Count;
static long FillAddRangeLazy(int[] source)
{
var list = new List<long>();
list.AddRange(source.Where(x => true).Select(x => (long)x * 2));
return list.Count;
}
static void Measure(string label, Func<long> action)
{
long checksum = action();
long bestBytes = long.MaxValue;
double bestMs = double.MaxValue;
for (int run = 0; run < 7; run++)
{
GC.Collect();
GC.WaitForPendingFinalizers();
GC.Collect();
long before = GC.GetAllocatedBytesForCurrentThread();
var sw = Stopwatch.StartNew();
long result = action();
sw.Stop();
long after = GC.GetAllocatedBytesForCurrentThread();
if (result != checksum) throw new Exception($"checksum mismatch on {label}");
bestBytes = Math.Min(bestBytes, after - before);
bestMs = Math.Min(bestMs, sw.Elapsed.TotalMilliseconds);
}
Console.WriteLine($"{label} {bestBytes,14:N0} bytes {bestMs,7:F1} ms");
}
(It's a single-file console app targeting net10.0; dotnet run -c Release and you're off.)
Anyone got a favorite spot where a known count was sitting right there and you still let the list guess? I keep finding them in my own code months after the fact.
— still benchmarking the stuff nobody asked me to
Top comments (0)