Exploring the .NET CoreFX Part 9: Immutable Collections and the Builder Pattern

This is part 9/17 of my Exploring the .NET CoreFX series.

Using the builder pattern to allow for easier construction of immutable objects is well-known.

The .NET Core’s immutable collections assembly, System.Collections.Immutable, also uses the builder pattern, but for a slightly different reason: to improve the performance of making many changes to the collection. This is possible because, unlike the immutable collection itself, the builder pattern does not need to maintain the immutable collection’s invariants after each modification. The builder pattern merely needs to reestablish the invariants of the immutable collection upon the publishing of the results.

Consider this code:

1
2
3
4
5
6


ImmutableArray<int> array = new ImmutableArray<int>();
for (int i = 1; i <= 100; ++i)
{
    array = array.Add(i);
}
// array now contains [1..100]

On each iteration of the loop, array must be a valid ImmutableArray. This will lead to a large number of reallocations and memory copies in order to maintain this requirement.

However, if the above code were replaced with this, it would be far more efficient:

1
2
3
4
5
6
7


ImmutableArray<int>.Builder builder = new ImmutableArray<int>().ToBuilder();
for (int i = 1; i <= 100; ++i)
{
    builder.Add(1);
}
ImmutableArray<int> array = builder.ToImmutable();
// array now contains [1..100]

This is also the pattern used by String and StringBuilder.

The .NET Core also uses a nice trick of separating ImmutableArray.Builder, an inner class with a substantial amount of code, into its own file by using partial classes:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


// ImmutableArray`1.cs
/// <summary>
/// A readonly array with O(1) indexable lookup time.
/// </summary>
/// <typeparam name="T">The type of element stored by the array.</typeparam>
[DebuggerDisplay("{DebuggerDisplay,nq}")]
public partial struct ImmutableArray<T> : IReadOnlyList<T>, IList<T>, IEquatable<ImmutableArray<T>>, IImmutableList<T>, IList, IImmutableArray, IStructuralComparable, IStructuralEquatable
{
    ...
}

// ImmutableArray`1+Builder.cs
public partial struct ImmutableArray<T>
{
    /// <summary>
    /// A writable array accessor that can be converted into an <see cref="ImmutableArray{T}"/>
    /// instance without allocating memory.
    /// </summary>
    [DebuggerDisplay("Count = {Count}")]
    [DebuggerTypeProxy(typeof(ImmutableArrayBuilderDebuggerProxy<>))]
    public sealed class Builder : IList<T>, IReadOnlyList<T>
    {
        ...
    }
}

Recommendations

Immutable objects are often highly valuable. Consider making your objects immutable and implementing the builder pattern.