Performance (ReadOnly)List vs Immutable collection types

A bit back on LinkedIn, there was a discussion about read-only collection and immutability where this is not the point I want to discuss now, as I already covered that here: "ReadOnlyCollection is not an immutable collection".

This post is just about the performance of those types compared to our baseline, the good old List<T>. It also explains why we see the results we see.

Keep in mind that even though performance analysis is fun and makes a good blog post, you have to check for you specific scenario if it makes sense! So always measure first and act second. This blog post will "just" give you an explanation why certain things behave like they behave.

The types we compare

We will have the following types:

  • List<T> - this will be our baseline. We can easily add elements and iterate over it.
  • ReadOnlyCollection<T> - a read-only wrapper around a list.
  • ImmutableArray<T> - A wrapper around an array.
  • ImmutableList<T>- Basically a tree that represents an immutable list.

First let's check how fast we can iterate over each:

private readonly List<int> _numbers = Enumerable.Range(0, 1_000).ToList();
private readonly ReadOnlyCollection<int> _readOnlyNumbers = Enumerable.Range(0, 1_000).ToList().AsReadOnly();
private readonly ImmutableArray<int> _immutableArray = Enumerable.Range(0, 1_000).ToImmutableArray();
private readonly ImmutableList<int> _immutableList = Enumerable.Range(0, 1_000).ToImmutableList();

[Benchmark(Baseline = true)]
public int IterateList()
{
    var sum = 0;
    for (var i = 0; i < _numbers.Count; i++)
    {
        sum += _numbers[i];
    }

    return sum;
}

[Benchmark]
public int IterateReadOnlyList()
{
    var sum = 0;
    for (var i = 0; i < _readOnlyNumbers.Count; i++)
    {
        sum += _readOnlyNumbers[i];
    }

    return sum;
}

[Benchmark]
public int IterateImmutableArray()
{
    var sum = 0;
    for (var i = 0; i < _immutableArray.Length; i++)
    {
        sum += _immutableArray[i];
    }

    return sum;
}

[Benchmark]
public int IterateImmutableList()
{
    var sum = 0;
    for (var i = 0; i < _immutableList.Count; i++)
    {
        sum += _immutableList[i];
    }

    return sum;
}

Results:

|                    Method |        Mean |     Error |    StdDev | Ratio | RatioSD |
|-------------------------- |------------:|----------:|----------:|------:|--------:|
|               IterateList |    553.4 ns |   1.59 ns |   1.41 ns |  1.00 |    0.00 |
| IterateReadOnlyCollection |  2,187.3 ns |   2.98 ns |   2.49 ns |  3.95 |    0.01 |
|     IterateImmutableArray |    437.5 ns |   4.48 ns |   4.19 ns |  0.79 |    0.01 |
|      IterateImmutableList | 16,914.6 ns | 335.40 ns | 810.04 ns | 30.55 |    1.39 |

Now a few things that might not be obvious, so let's go through them. Why is the ReadOnlyCollection slower? Didn't I say it is just a wrapper around the List<T>? Well, yes, it is and with that certain costs come into play - keep in mind we are talking about nanoseconds here. Nothing significant for 99% of use cases! Anyway, accessing via indirection has to cost something - also _readOnlyNumbers.Length is a computed property instead of a "simple property". So we also have to "pay" the cost of a function call to the underlying list.

We can see the opposite effect with the ImmutableArray. It is super quick to access the underlying array. List and ImmutableList are almost the same as they both "wrap" an array.

The last one ImmutableList is designed as a tree, so instead of O(1) to access an element we have O(log(n)) (worst-case).

Inserting an element

Now you might think: How can we add an element to a ReadOnlyCollection and an ImmutableList?

  • ReadOnlyCollection: We can't directly. If we want we have to transform it into a list and add the element and return the new list.
  • ImmutableList / ImmutableCollection: Of course, we can not add direct elements. But those data structures offer a way to add elements and return a new immutable collection. The cool thing is, that because they are immutable, they can share for example the whole base array. We will not add the List<T>.Add here as this isn't a pure function and it would not be a fair comparison against the other methods. Keep in mind, that BenchmarkDotNet, the library I am using here, executes your benchmark functions a lot of times. With a List<T> that would mean it would grow and grow and grow (and get resized a lot). Therefore statistically it would be garbage what we are doing.
[MemoryDiagnoser]
public class AddBenchmark
{
    private readonly ReadOnlyCollection<int> _readOnlyNumbers = Enumerable.Range(0, 1_000).ToList().AsReadOnly();
    private readonly ImmutableArray<int> _immutableArray = Enumerable.Range(0, 1_000).ToImmutableArray();
    private readonly ImmutableList<int> _immutableList = Enumerable.Range(0, 1_000).ToImmutableList();

    private readonly int[] numbersToAdd = { 1, 2, 3, 4, 5, 6, 7, 8 };

    [Benchmark]
    public IReadOnlyList<int> AddElementReadOnlyCollection()
    {
        var l = _readOnlyNumbers.ToList();
        l.AddRange(numbersToAdd);
        return l;
    }

    [Benchmark]
    public ImmutableArray<int> AddElementImmutableArray() 
        => _immutableArray.AddRange(numbersToAdd);

    [Benchmark]
    public ImmutableList<int> AddElementImmutableList() 
        => _immutableList.AddRange(numbersToAdd);
}

Results:

|                       Method |     Mean |   Error |  StdDev |   Gen0 |   Gen1 | Allocated |
|----------------------------- |---------:|--------:|--------:|-------:|-------:|----------:|
| AddElementReadOnlyCollection | 544.9 ns | 1.84 ns | 1.63 ns | 1.9255 | 0.0210 |   12080 B |
|     AddElementImmutableArray | 189.7 ns | 1.38 ns | 1.29 ns | 0.6464 |      - |    4056 B |
|      AddElementImmutableList | 304.8 ns | 2.14 ns | 1.90 ns | 0.1526 |      - |     960 B |

We are adding 8 elements to our original collection. With the ImmutableArray we have a nice trade-off. It is the fastest but also uses a bit more memory. The ImmutableList is not as fast but can share a lot of memory with its origin. On the contrary, the ReadOnlyCollection has to create the whole collection plus the 8 elements on top!

Conclusion

I hope I could show you some metrics and some insights into how those types work!

Resources

  • Source code to this blog post: here
  • All my sample code is hosted in this repository: here

How does a List know that you changed it while enumerating it?

Everyone falls for that and tries to change a list while enumerating it greeted by the System.InvalidOperationException: Collection was modified; enumeration operation may not execute. message. But how does the List know that you changed it? Let's find out.

ReadOnlyCollection is not an immutable collection

In this blog post we discover how we can mutate a ReadOnlyCollection to have more or less entries than its original state. Readonly does not mean it is immutable. Also we will check out the ImmutableArray.

Array, List, Collection, Set, ReadOnlyList - what? A comprehensive and exhaustive list of collection-like types

.NET knows a big list of collection-like types like: IEnumerable, IQueryable, IList, ICollection, Array, ISet, ImmutableArray, ReadOnlyCollection, ReadOnlyList, and many more.

This blog post will give you an exhaustive list of types in .NET and when to use what.

An error has occurred. This application may no longer respond until reloaded. Reload x