skip to content

Immutable and Frozen

ImmutableList<T> and its kin return new versions on change, while FrozenDictionary trades build cost for fast reads. Interviewers ask read-only vs immutable vs frozen.

on this pageshow

explore

questions

6

In .NET, why does building an ImmutableArray<T> with Add in a loop allocate far more than ImmutableList<T>, and how do builders fix it?

level: middleimportance: should knowfreq 38%

answer

  1. what each type stores inside
  2. one array versus a balanced tree
  3. copy everything versus copy one path
  4. mutate privately, then publish once

basics

~20 s

ImmutableArray<T> wraps one array, so every Add copies all elements into a new array; ImmutableList<T> is a balanced tree, so Add copies only one path of nodes. For bulk construction, fill a mutable builder and convert it once with ToImmutable or MoveToImmutable.

solid answer

~40 s

`ImmutableArray<T>` is a `readonly struct` around a single `T[]`. Reads are as fast as an array, but `Add` allocates a new array one element longer and copies everything, so n adds in a loop cost O(n^2) copying: about 200 MB of allocations for 10,000 ints on .NET 10. `ImmutableList<T>` is an AVL tree: `Add` allocates only the O(log n) nodes on one path and shares the rest, but its indexer is O(log n) too. For bulk construction, neither loop is right: use a **builder**. `ImmutableArray.CreateBuilder<T>(capacity)` gives a mutable list; `MoveToImmutable()` hands its internal array over without copying when `Count == Capacity`, and `ToImmutable()` copies. `ImmutableList<T>.ToBuilder()` and `Builder.ToImmutable()` reuse the tree. Choose `ImmutableArray<T>` for data built once and read a lot, `ImmutableList<T>` for data that keeps getting small changes.

code

csharp · 26 lines
csharp
using System.Collections.Immutable;
using System.Globalization;

CultureInfo.CurrentCulture = CultureInfo.InvariantCulture;
const int N = 10_000;

long before = GC.GetAllocatedBytesForCurrentThread();
ImmutableArray<int> looped = ImmutableArray<int>.Empty;
for (int i = 0; i < N; i++) looped = looped.Add(i);      // copies the whole array each time
Report("ImmutableArray<int>.Add in a loop", before);

before = GC.GetAllocatedBytesForCurrentThread();
ImmutableList<int> tree = ImmutableList<int>.Empty;
for (int i = 0; i < N; i++) tree = tree.Add(i);          // new path of tree nodes each time
Report("ImmutableList<int>.Add in a loop ", before);

before = GC.GetAllocatedBytesForCurrentThread();
ImmutableArray<int>.Builder builder = ImmutableArray.CreateBuilder<int>(N);
for (int i = 0; i < N; i++) builder.Add(i);
ImmutableArray<int> built = builder.MoveToImmutable();   // hands over the array: Count == Capacity
Report("ImmutableArray<int>.Builder       ", before);

Console.WriteLine($"{looped.Length} {tree.Count} {built.Length}");

static void Report(string label, long before) =>
    Console.WriteLine($"{label}: {GC.GetAllocatedBytesForCurrentThread() - before:N0} bytes");

go deeper

for a junior

Recall that both types return new collections on Add, and that builders exist for adding many items.

for a middle

Explain the storage: one array copied on every change versus a tree that shares all but one path, and what that does to Add and the indexer.

for a senior

Spot a quadratic build loop from an allocation profile, and pick MoveToImmutable on a pre-sized builder or ToImmutableArray as the fix.

for a principal

Set the guideline: ImmutableArray<T> for read-mostly data built in one go, ImmutableList<T> for long-lived values with small edits, builders for every bulk construction.

## Two immutable lists with opposite costs `System.Collections.Immutable` has two indexable list types, and they are built differently on purpose. - **`ImmutableArray<T>`** is a `readonly struct` with one field: a `T[]`. Its indexer and `Length` go straight to that array, so reading is as cheap as reading a plain array. The price is paid on change: `Add`, `Insert` and `Remove` allocate a **new array** and copy every element across, because the old array must stay untouched for anyone still holding it. - **`ImmutableList<T>`** is a class wrapping the root of an **AVL tree** (a self-balancing binary tree). `Add` creates new nodes only along the path from the root to the insertion point and **shares** every other node with the previous version. The price is paid on reads: the indexer walks down the tree, so `list[i]` is O(log n), not O(1). | Operation | `ImmutableArray<T>` | `ImmutableList<T>` | |---|---|---| | Indexer `[i]` | O(1), a plain array read | O(log n), a tree walk | | `Add` / `Insert` | O(n): new array, full copy | O(log n): new nodes on one path | | `foreach` | fast, struct enumerator over the array | fast, walks the tree in order | | Memory | one array, no per-element overhead | one node object per element | | Kind of type | struct (has a `default` value to watch) | class | ## Why the loop is so expensive A loop that does `array = array.Add(i)` 10,000 times copies 1 element, then 2, then 3, up to 9,999: about n²/2 element copies in total, plus 10,000 discarded arrays for the garbage collector. Measured with `GC.GetAllocatedBytesForCurrentThread()` on .NET 10, that loop allocates roughly **200 MB** for 10,000 ints. The same loop on `ImmutableList<int>` allocates about **6.6 MB**, because each `Add` creates only a handful of tree nodes. Both are far more than the data itself, which is about 40 KB. The lesson is not "use `ImmutableList<T>`". It is that **repeated single-item changes are the wrong way to build any immutable collection**. ## Builders: mutable while you build, immutable when you publish Every immutable collection type has a nested **`Builder`** class: a mutable, not thread-safe collection with the same element type. You make all the changes on it, then convert it once. 1. **Create a builder.** `ImmutableArray.CreateBuilder<T>(initialCapacity)` or `ImmutableList.CreateBuilder<T>()` starts empty; `existing.ToBuilder()` starts from an existing immutable collection. 2. **Change it freely.** `builder.Add`, `Remove` and `Sort` really do mutate the builder, like a `List<T>`. 3. **Convert once.** The conversion methods differ: - `ImmutableArray<T>.Builder.MoveToImmutable()` hands its internal array to the new `ImmutableArray<T>` **without copying**, and resets the builder to empty. It throws `InvalidOperationException` unless `Count == Capacity`, so it suits a builder created with the exact final size. - `ImmutableArray<T>.Builder.ToImmutable()` **copies** the contents into a new array and leaves the builder usable. - `ImmutableArray<T>.Builder.DrainToImmutable()` hands over the array when it is exactly full, copies otherwise, and empties the builder either way. - `ImmutableList<T>.Builder.ToImmutable()` wraps the builder's tree and freezes it, so no elements are copied; later builder changes clone only the nodes they touch. With a pre-sized `ImmutableArray<int>.Builder` and `MoveToImmutable`, building the same 10,000 ints allocates about **40 KB**, essentially just the one array. For a literal list, C# 12 collection expressions work too: `ImmutableArray<string> codes = ["EUR", "USD"];` compiles to `ImmutableArray.Create` through the type's `[CollectionBuilder]` attribute. From an existing sequence, `ToImmutableArray()` and `ToImmutableList()` build in one pass. ## Wrapping an array you already have `ToImmutableArray()` on a `List<T>` or an array copies the elements once, which is the safe default. When code has just filled a `T[]` that nothing else will ever see, `ImmutableCollectionsMarshal.AsImmutableArray(array)` wraps it **without copying**. The source warns that the caller must be the sole owner of that array and must never change it afterwards, because every holder of the `ImmutableArray<T>` would see the change. It is a tool for hot paths, not a general replacement for `ToImmutableArray()`. Going the other way, `ImmutableArray<T>.AsSpan()` returns a `ReadOnlySpan<T>` over the wrapped array, so span-based APIs can read it without a copy. ## Choosing between the two - Built once (at startup, per request, per message) and then only read: **`ImmutableArray<T>`**, built through a builder or `ToImmutableArray()`. - A long-lived value that receives a stream of small edits, where each version must stay valid: **`ImmutableList<T>`**, whose structural sharing keeps each edit cheap. - Code that indexes heavily in a `for` loop: avoid `ImmutableList<T>`, whose O(log n) indexer makes the loop O(n log n); prefer `foreach` or an `ImmutableArray<T>`. - Many edits in a row on either type: a **builder**, then one conversion.

  • Why does MoveToImmutable throw when Count is less than Capacity?
    It hands over the builder's internal array as is, and an `ImmutableArray<T>` exposes the whole array as its contents. If the array had unused slots, they would appear as extra default elements. So it insists on an exact fit and throws `InvalidOperationException` otherwise; `ToImmutable` or `DrainToImmutable` copy into a right-sized array instead.
  • Is an ImmutableArray<T>.Builder safe to fill from several threads at once?
    No. `ImmutableArray<T>.Builder` is an ordinary mutable list with no synchronisation in its source, and the `ImmutableList<T>.Builder` docs state outright that its members are not thread-safe. Fill one on a single thread, or give each thread its own and combine the results, then publish the finished immutable collection, which is safe to share.
  • When would ImmutableList<T>'s per-node overhead matter?
    For large collections of small values. Each element lives in its own tree node object with child references, a height and a count, so an `ImmutableList<int>` holds far more memory than an `ImmutableArray<int>` of the same length. For read-mostly data that overhead buys nothing.

  • ImmutableArray<T>.Add is O(1) amortised like List<T>.Add
  • ImmutableList<T> is an array internally, so its indexer is O(1)
  • A builder makes the resulting collection mutable
  • MoveToImmutable always copies the builder's array
  • Calling ToImmutable after every builder Add is as cheap as one final call
open as a page

In C#, why does rules.Add("gbp-rounding") leave an ImmutableList<string> unchanged, and how do you fix the code?

level: middleimportance: should knowfreq 45%

basics

~10 s

ImmutableList<T>.Add never changes the list it is called on; it returns a new ImmutableList<T> containing the item. Code that ignores the return value throws the new list away. Assign it: rules = rules.Add("gbp-rounding").

open as a page

In .NET, what does each promise when a pricing service hands out flags as a ReadOnlyCollection<T>, an ImmutableList<T> or a FrozenSet<T>?

level: middleimportance: should knowfreq 48%

basics

~20 s

A ReadOnlyCollection<T> is a read-only view: callers cannot change it, but the owner's list still can. An ImmutableList<T> is a copy nobody can change; changes return new versions. A FrozenSet<T> (.NET 8) is also unchangeable, built once for fast lookups.

open as a page

In C#, why does reading Length on an ImmutableArray<decimal> property that was never assigned throw NullReferenceException, and how do you guard against it?

level: seniorimportance: should knowfreq 30%

basics

~20 s

ImmutableArray<T> is a struct wrapping an array, and its default value wraps null. Length, the indexer, Add and foreach use that null array and throw NullReferenceException. Initialise to ImmutableArray<T>.Empty or [], and test IsDefault at boundaries.

open as a page

In .NET 8 and later, a pricing service freezes its case-insensitive currency table with loaded.ToFrozenDictionary(), and lookups of "usd" now miss; why, and when is freezing worth it?

level: seniorimportance: should knowfreq 40%

basics

~10 s

ToFrozenDictionary uses EqualityComparer<TKey>.Default unless you pass a comparer, so freezing a case-insensitive Dictionary without one rebuilds it case-sensitively. Pass StringComparer.OrdinalIgnoreCase. Freezing pays off for tables built once and read constantly.

open as a page

Should a .NET team standardise on immutable collections for shared state like a pricing service's rules snapshot, and what does that standard cost?

level: principalimportance: should knowfreq 30%

basics

~20 s

Often yes for read-mostly shared state: readers get lock-free snapshots and writers publish new versions with ImmutableInterlocked.Update. The costs are an allocation per change, slower lookups than Dictionary and new bug patterns, so write-heavy and startup-only state need other choices.

open as a page