Immutable Dictionary and Frozen Dictionary in .NET

#dotnet #dotnetcore

Introduction

In .NET, dictionaries are a crucial part of the data structure landscape. They provide a way to store key-value pairs with efficient lookup. However, when it comes to immutability and performance, traditional dictionaries might not always be the best choice. This is where the Immutable Dictionary and the Frozen Dictionary come into play. In this article, we'll explore these two types of dictionaries, their advantages, and disadvantages, and provide examples of their usage along with performance benchmarks.

Immutable Dictionary

The Immutable Dictionary is part of the System.Collections.Immutable namespace in .NET. This dictionary is created as immutable, meaning that any modification operation on it results in a new dictionary with the required changes, without affecting the original one.

Advantages

Safety from Changes: It provides security against unexpected changes since the dictionary cannot be modified after creation.
Concurrency: Useful in multi-threaded environments as it doesn't require locking for data access.
Ease of Use: Makes the code more maintainable and readable.

Disadvantages

Performance: The cost in terms of performance can be high when frequent modifications are required, as new copies of the dictionary are created each time.

Frozen Dictionary

The Frozen Dictionary is a new type introduced in .NET 8, designed to optimize performance for dictionary lookups. Once frozen, the dictionary's internal structure is optimized for significantly faster lookups.

Advantages

High Performance: Provides high performance in lookup operations after the dictionary is frozen.
Stability: Once the dictionary is frozen, it cannot be modified, ensuring data stability.

Disadvantages

Immutability after Freezing: Once frozen, no modifications can be made.
Specific Use Case: It is only useful in scenarios where no frequent changes are required after the dictionary is created.

Performance Benchmarks

To compare the performance of Immutable Dictionary and Frozen Dictionary, we can use BenchmarkDotNet. Below is a benchmark test that measures the creation and lookup times for various data structures including Immutable Dictionary and Frozen Dictionary.

Benchmark Code

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Collections.Frozen;
using System.Collections.Immutable;
using System.Linq;

public class CreateBenchmark
{
    private const int items = 1_000_000;

    [Benchmark(Baseline = true)]
    public void CreateList()
    {
        List<int> _list = Enumerable.Range(0, items).ToList();
    }

    [Benchmark]
    public void CreateDictionary()
    {
        Dictionary<int, int> _dictionary = Enumerable.Range(0, items).ToDictionary(x => x);
    }

    [Benchmark]
    public void CreateImmutableDictionary()
    {
        ImmutableDictionary<int, int> _immutableDictionary = Enumerable.Range(0, items).ToImmutableDictionary(x => x);
    }

    [Benchmark]
    public void CreateFrozenSet()
    {
        FrozenSet<int> _frozenDictionary = Enumerable.Range(0, items).ToFrozenSet();
    }

    [Benchmark]
    public void CreateFrozenDictionary()
    {
        FrozenDictionary<int, int> _frozenDictionary = Enumerable.Range(0, items).ToFrozenDictionary(x => x);
    }
}

public class LookupBenchmark
{
    private const int items = 1_000_000;
    private const int iterations = 1_000;

    private readonly List<int> list = Enumerable.Range(0, items).ToList();
    private readonly Dictionary<int, int> dictionary = Enumerable.Range(0, items).ToDictionary(x => x);
    private readonly ImmutableDictionary<int, int> immutableDictionary = Enumerable.Range(0, items).ToImmutableDictionary(x => x);

    private readonly FrozenSet<int> frozenSet = Enumerable.Range(0, items).ToFrozenSet();
    private readonly FrozenDictionary<int, int> frozenDictionary = Enumerable.Range(0, items).ToFrozenDictionary(x => x);

    [Benchmark(Baseline = true)]
    public void LookupList()
    {
        for (var i = 0; i < iterations; i++)
            _ = list.Contains(i);
    }

    [Benchmark]
    public void LookupDictionary()
    {
        for (var i = 0; i < iterations; i++)
            _ = dictionary.ContainsKey(i);
    }

    [Benchmark]
    public void LookupImmutableDictionary()
    {
        for (var i = 0; i < iterations; i++)
            _ = immutableDictionary.ContainsKey(i);
    }

    [Benchmark]
    public void LookupFrozenSet()
    {
        for (var i = 0; i < iterations; i++)
            _ = frozenSet.Contains(i);
    }

    [Benchmark]
    public void LookupFrozenDictionary()
    {
        for (var i = 0; i < iterations; i++)
            _ = frozenDictionary.ContainsKey(i);
    }
}

public class Program
{
    public static void Main(string[] args)
    {
        BenchmarkRunner.Run<CreateBenchmark>();
        BenchmarkRunner.Run<LookupBenchmark>();
    }
}

Benchmark Results

The following images show the results of the benchmark tests for creation and lookup times.

Creation Time

Lookup Time

From the benchmark results, we can observe the following:

Creation Time: The ImmutableDictionary takes significantly more time to create compared to FrozenDictionary. This is expected due to the immutability features that involve copying data.
Lookup Time: The FrozenDictionary performs exceptionally well in lookup operations, significantly outperforming ImmutableDictionary and even traditional dictionaries.

Conclusion

Both Immutable Dictionary and Frozen Dictionary provide unique benefits and trade-offs. The Immutable Dictionary is great for ensuring data safety and supporting concurrent operations without locks, at the cost of performance when modifications are frequent. On the other hand, the Frozen Dictionary offers high-performance lookups and data stability after freezing but is only suitable for scenarios where the data doesn't need to change frequently.