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 theList<T>.Addhere 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 aList<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!
