Choosing the Best Immutable Dictionary for Your C# Projects

Pierre Belin -

In the realm of C# programming, dictionaries are a fundamental data structure that allows developers to store and retrieve data efficiently. A dictionary is essentially a collection of key-value pairs, where each key is unique and maps to a specific value. This unique key serves as an identifier for the corresponding value, making it easy to access and manipulate data.

The primary advantage of using dictionaries is their ability to provide fast lookups. When you have a list of elements where each element has a unique identifier, dictionaries are the go-to data structure. For instance, if you have a list of employees, each with a unique employee ID, a dictionary allows you to quickly find an employee's details using their ID.

In this article, we will focus on dictionaries whose values cannot be modified. Therefore, we won't be discussing ConcurrentDictionary, OrderedDictionary, or SortedDictionary.

Instead, we will delve into three specific types of immutable dictionaries: ReadOnlyDictionary, ImmutableDictionary, and FrozenDictionary.

Performance comparison

To understand the performance characteristics of these dictionaries, we conducted a series of benchmarks. The first step involves creating a dictionary with 1 million values and converting it to the respective type. This allows us to compare the instantiation times of each dictionary.

Benchmark: Dictionary Creation

[Benchmark]
public void Create_ReadOnlyDictionary()
{
    var dictionnary = new Dictionary<string, Goat>();
    for (int i = 0; i < 1000000; i++)
    {
        dictionnary.Add(i.ToString(), new Goat {Name = i.ToString()});
    }
    var result = new ReadOnlyDictionary<string, Goat>(dictionnary);
}

[Benchmark]
public void Create_ImmutableDictionary()
{
    var dictionnary = new Dictionary<string, Goat>();
    for (int i = 0; i < 1000000; i++)
    {
        dictionnary.Add(i.ToString(), new Goat {Name = i.ToString()});
    }
    var result = dictionnary.ToImmutableDictionary();
}

[Benchmark]
public void Create_FrozenDictionary()
{
    var dictionnary = new Dictionary<string, Goat>();
    for (int i = 0; i < 1000000; i++)
    {
        dictionnary.Add(i.ToString(), new Goat {Name = i.ToString()});
    }
    var result = dictionnary.ToFrozenDictionary();
}

This gives the following results:

BenchmarkDotNet v0.13.12, Windows 11 (10.0.22631.3447/23H2/2023Update/SunValley3)
.NET SDK 8.0.300-preview.24127.15
  [Host] : .NET 8.0.4 (8.0.424.16909), X64 RyuJIT AVX2

| Method                          | Mean       | Error    | StdDev   | Gen0       | Gen1       | Gen2      | Allocated |
|-------------------------------- |-----------:|---------:|---------:|-----------:|-----------:|----------:|----------:|
| Create_ReadOnlyDictionary       |   269.8 ms |  5.23 ms |  7.50 ms |  8500.0000 |  8000.0000 |  500.0000 | 169.59 MB |
| Create_ImmutableDictionary      | 1,284.6 ms | 25.48 ms | 53.74 ms | 14000.0000 | 13000.0000 | 1000.0000 | 230.64 MB |
| Create_FrozenDictionary         |   353.2 ms |  6.17 ms |  6.60 ms |  8500.0000 |  8000.0000 |  500.0000 | 265.92 MB |

The results show that ReadOnlyDictionary has the fastest creation time, followed by FrozenDictionary, and then ImmutableDictionary. The difference in performance can be attributed to the underlying implementation and the additional overhead required to ensure immutability.

Next, we benchmark the performance of lookup operations using the TryGetValue method. The dictionaries are created beforehand to avoid impacting the results.

Benchmark: Lookup Operations

[Benchmark]
public void TryGetValue_ReadOnlyDictionary()
{
    for (int i = 0; i < 1000000; i++)
    {
        var index = Random.Shared.Next(0, N);
        _readOnlyDictionary.TryGetValue(index.ToString(), out var value);
    }
}

[Benchmark]
public void TryGetValue_ImmutableDictionary()
{
    for (int i = 0; i < 1000000; i++)
    {
        var index = Random.Shared.Next(0, N);
        _immutableDictionary.TryGetValue(index.ToString(), out var value);
    }
}

[Benchmark]
public void TryGetValue_FrozenDictionary()
{
    for (int i = 0; i < 1000000; i++)
    {
        var index = Random.Shared.Next(0, N);
        _frozenDictionary.TryGetValue(index.ToString(), out var value);
    }
}

This gives the following results:

BenchmarkDotNet v0.13.12, Windows 11 (10.0.22631.3447/23H2/2023Update/SunValley3)
.NET SDK 8.0.300-preview.24127.15
  [Host] : .NET 8.0.4 (8.0.424.16909), X64 RyuJIT AVX2

Toolchain=InProcessEmitToolchain  

| Method                          | Mean       | Error    | StdDev   | Gen0       | Gen1       | Gen2      | Allocated |
|-------------------------------- |-----------:|---------:|---------:|-----------:|-----------:|----------:|----------:|
| TryGetValue_ReadOnlyDictionary  |   187.0 ms |  3.69 ms |  6.46 ms |  3000.0000 |          - |         - |  37.38 MB |
| TryGetValue_ImmutableDictionary |   786.6 ms | 15.59 ms | 31.13 ms |  3000.0000 |          - |         - |  37.38 MB |
| TryGetValue_FrozenDictionary    |   167.7 ms |  1.69 ms |  1.58 ms |  3000.0000 |          - |         - |  37.38 MB |

The lookup performance results indicate that FrozenDictionary offers the fastest lookup times, followed by ReadOnlyDictionary, and then ImmutableDictionary. The superior performance of FrozenDictionary can be attributed to its optimization for read-only operations.

Why have several types of dictionary?

Given the above results, you'd think that ImmutableDictionary would be useless, as it's both slower to read and write. The FrozenDictionary doesn't seem to have any added value either, so why create these classes?

The devil is in the detail.

Non-modifiability and immutability

The first part of the answer lies in the definition of immutability.

Immutability and non-modifiability are two different concepts in C# that can lead to confusion. Here's a clarification:

  • Non-modifiability: once the dictionary is created and exposed, no element can be added, deleted or modified through this interface. However, if someone holds a reference to the original dictionary, they can still modify this collection, and these modifications will be reflected in the dictionary.
  • Immutability: once created, it cannot be modified. Any operation that appears to modify the dictionary (such as adding or deleting elements) actually returns a new instance of the dictionary with the modification applied. The original instance remains unchanged. This guarantees total thread safety and prevents any modification, intentional or accidental, without exception.

What we understand here is that the ReadOnlyDictionary can be changed indirectly by modifying the dictionary on which it is based. And this is not trivial. It is therefore possible for it to be modified on the fly. Make sure that the base reference is not modified during creation.

[Fact]
public void ShouldKeyValuePairAddedToReadOnlyDictionaryWhenAddedToReferenceDictionary()
{
    var dictionary = new Dictionary<string, string>
    {
        ["key1"] = "value1",
        ["key2"] = "value2"
    };

    var readOnlyDictionary = dictionary.AsReadOnly();
    readOnlyDictionary.Should().HaveCount(2);
    
    dictionary.Add("key3", "value3");
    readOnlyDictionary.Should().ContainKey("key3", "value3");
}

In the previous example, by adding an element to the dictionary referenced by the read-only dictionary, it is also added to it! This is not the case with an immutable dictionary.

[Fact]
public void ShouldKeyValuePairAddedToImmutableDictionaryWhenAddedToReferenceDictionary()
{
    var dictionary = new Dictionary<string, string>
    {
        ["key1"] = "value1",
        ["key2"] = "value2"
    };

    var immutableDictionary = dictionary.ToImmutableDictionary();
    immutableDictionary.Should().HaveCount(2);
    
    dictionary.Add("key3", "value3");
    // THIS IS RED THERE, IT'S FAILING !
    immutableDictionary.Should().ContainKey("key3", "value3");
}

However, immutability comes at a cost.

Already at the creation level, with a factor close to 5.

On the other hand, this cost is only present when transforming a Dictionary into an ImmutableDictionary. Once that's done, it's a breeze to add elements to an array and copy them.

To verify this, let's take a look at the following benchmark:

[Benchmark]
public void Create_ReadOnlyDictionary_AddElementToDictionary()
{
    var dictionnary = new Dictionary<string, Goat>();
    for (int i = 0; i < 10000; i++)
    {
        dictionnary = new Dictionary<string, Goat>(dictionnary) { { i.ToString(), new Goat {Name = i.ToString()} } };
    }
    var result = new ReadOnlyDictionary<string, Goat>(dictionnary);
}

[Benchmark]
public void Create_ImmutableDictionary_AddElementToDictionary()
{
    var dictionnary = ImmutableDictionary.Create<string, Goat>();
    for (int i = 0; i < 10000; i++)
    {
        dictionnary = dictionnary.Add(i.ToString(), new Goat {Name = i.ToString()});
    }
    var result = dictionnary.ToImmutableDictionary();
}

This gives a 100x difference, which is truly significant.

BenchmarkDotNet v0.13.12, Windows 11 (10.0.22631.3447/23H2/2023Update/SunValley3)
.NET SDK 8.0.300-preview.24127.15
  [Host] : .NET 8.0.4 (8.0.424.16909), X64 RyuJIT AVX2

Toolchain=InProcessEmitToolchain  

| Method                                                  | Mean       | Error      | StdDev     | Gen0       | Gen1       | Gen2      | Allocated  |
|-------------------------------------------------------- |-----------:|-----------:|-----------:|-----------:|-----------:|----------:|-----------:|
| Create_ReadOnlyDictionary_AddElementToDictionary        | 772.808 ms | 15.4528 ms | 14.4546 ms | 33000.0000 | 13000.0000 | 4000.0000 | 1464.01 MB |
| Create_ImmutableDictionary_AddElementToDictionary       |   6.079 ms |  0.0481 ms |  0.0402 ms |   765.6250 |   531.2500 |         - |    9.19 MB |

The ImmutableDictionary takes all this strength and puts it to massive use in dictionary creation.

And now it's time to ask what the role of the FrozenDictionary is.

Dictionary optimization

Looking a little closer, we've just seen that the ImmutableDictionary can be optimized for writing, but still not for reading...

And that's where the FrozenDictionary comes in.

The FrozenDictionary is also an immutable dictionary, but designed for high frequency reading. To quote Microsoft documentation: “FrozenDictionary [...]. It has a relatively high cost to create but provides excellent lookup performance.”

Hence the more interesting reading results.

In this way, we retain the best features of the ReadOnlyDictionnary, i.e. rapid reading, and the ImmutableDictionary, i.e. the immutability of the collection.

Conclusion

In conclusion, choosing the right dictionary type in C# depends on your specific needs.

ReadOnlyDictionary is great for providing read-only access to an existing dictionary but can be modified if the underlying dictionary is referenced directly. This makes it suitable for scenarios where you need to expose a dictionary without allowing modifications, as long as the base reference remains unchanged.

ImmutableDictionary ensures true immutability, making it ideal for multi-threaded environments where thread safety is crucial. However, it comes with a significant cost in terms of creation time and memory usage. Despite the initial performance hit, it provides efficient operations once created.

FrozenDictionary offers the immutability of ImmutableDictionary with optimized read performance, making it perfect for scenarios where the dictionary is created once and used extensively for read-only operations. Although it has a higher creation cost, its excellent lookup performance makes it a compelling choice for high-frequency read scenarios.

By understanding the strengths and weaknesses of each dictionary type, you can make an informed decision that best suits your application's needs. Whether you prioritize quick creation, true immutability, or optimized read performance, there is a dictionary type that fits your requirements.

Have a goat day 🐐