.NET 8 — FrozenDictionary performance

Microsoft’s upcoming release of .NET 8 will introduce a lot of new features that will certainly be welcomed by the developer community, making it an even stronger framework for application development.

One of those features is the namespace System.Collections.Frozen that introduces two new collections: FrozenDictionary and FrozenSet. These new types, as stated by Microsoft, are focused in reducing the time of read operations at the expense of increasing initialization time of immutable collections. This makes them perfect for shared data that only needs to be populated a single time, like application configurations or cached data in-memory.

In this article I’m going to benchmark the performance gains that can be achieved by using a FrozenDictionary instead of a Dictionary or an ImmutableDictionary to store shared data.

I’m going to use the well known C# library BenchmarkDotNet to run the tests and the environment will be the following:

BenchmarkDotNet v0.13.10, Windows 11 (10.0.22621.2428/22H2/2022Update/SunValley2)
AMD Ryzen 7 3700X, 1 CPU, 16 logical and 8 physical cores
.NET SDK 8.0.100-rc.2.23502.2
  [Host]   : .NET 8.0.0 (8.0.23.47906), X64 RyuJIT AVX2
  .NET 8.0 : .NET 8.0.0 (8.0.23.47906), X64 RyuJIT AVX2

For the tests, I’m going to benchmark the method TryGetValue, with one for 100% key hits and another for 100% key misses, which should give the performance for both perfect and worse scenarios. The collections FrozenDictionary, ImmutableDictionary and Dictionary will be used with a parameter setting the size.

---

Scenario 1 — all keys are found

For this scenario I’m going to initialize a collection of unique keys, populate all three dictionaries accordingly and then run the TryGetValue for all keys returning the latest found using the Dictionary test as the baseline.

[SimpleJob(RuntimeMoniker.Net80)]
[MemoryDiagnoser]
public class TryGetValueAllKeysFound
{
    [Params(10, 100, 1000, 10000, 100000)]
    public int Size;

    private int[] _keys;

    private Dictionary<int, int> _dictionary;
    private ImmutableDictionary<int,int> _immutableDictionary;
    private FrozenDictionary<int, int> _frozenDictionary;

    [GlobalSetup]
    public void Setup()
    {
        var random = new Random(123);

        var uniqueKeys = new HashSet<int>(Size);
        for (var i = 0; i < Size; i++)
        {
            int key;
            do
            {
                key = random.Next();
            } while (uniqueKeys.Contains(key));

            uniqueKeys.Add(key);
        }

        _dictionary = uniqueKeys.Select((key, idx) => (key, idx)).ToDictionary(e => e.key, e => e.idx);
        _immutableDictionary = uniqueKeys.Select((key, idx) => (key, idx)).ToImmutableDictionary(e => e.key, e => e.idx);
        _frozenDictionary = uniqueKeys.Select((key, idx) => (key, idx)).ToFrozenDictionary(e => e.key, e => e.idx);

        _keys = uniqueKeys.ToArray();
    }

    [Benchmark(Baseline = true)]
    public int Dictionary()
    {
        var latestValue = -1;

        foreach (var key in _keys)
        {
            if (_dictionary.TryGetValue(key, out var value))
                latestValue = value;
        }

        return latestValue;
    }

    [Benchmark]
    public int ImmutableDictionary()
    {
        var latestValue = -1;

        foreach (var key in _keys)
        {
            if (_immutableDictionary.TryGetValue(key, out var value))
                latestValue = value;
        }

        return latestValue;
    }

    [Benchmark]
    public int FrozenDictionary()
    {
        var latestValue = -1;

        foreach (var key in _keys)
        {
            if (_frozenDictionary.TryGetValue(key, out var value))
                latestValue = value;
        }

        return latestValue;
    }
}

The benchmark results are the following:

| Method              | Size   | Mean             | Error          | StdDev        | Ratio | RatioSD | Allocated | Alloc Ratio |
|-------------------- |------- |-----------------:|---------------:|--------------:|------:|--------:|----------:|------------:|
| Dictionary          | 10     |         46.29 ns |       0.300 ns |      0.251 ns |  1.00 |    0.00 |         - |          NA |
| ImmutableDictionary | 10     |         35.53 ns |       0.320 ns |      0.283 ns |  0.77 |    0.01 |         - |          NA |
| FrozenDictionary    | 10     |         85.47 ns |       1.779 ns |      5.244 ns |  1.86 |    0.13 |         - |          NA |
|                     |        |                  |                |               |       |         |           |             |
| Dictionary          | 100    |        470.00 ns |       2.253 ns |      2.108 ns |  1.00 |    0.00 |         - |          NA |
| ImmutableDictionary | 100    |        736.28 ns |      14.637 ns |     31.820 ns |  1.57 |    0.07 |         - |          NA |
| FrozenDictionary    | 100    |        263.18 ns |       2.898 ns |      2.569 ns |  0.56 |    0.01 |         - |          NA |
|                     |        |                  |                |               |       |         |           |             |
| Dictionary          | 1000   |      4,993.04 ns |      27.440 ns |     22.913 ns |  1.00 |    0.00 |         - |          NA |
| ImmutableDictionary | 1000   |     29,174.27 ns |     493.738 ns |    461.843 ns |  5.85 |    0.10 |         - |          NA |
| FrozenDictionary    | 1000   |      2,841.24 ns |      30.283 ns |     28.326 ns |  0.57 |    0.01 |         - |          NA |
|                     |        |                  |                |               |       |         |           |             |
| Dictionary          | 10000  |     77,394.04 ns |     295.972 ns |    247.150 ns |  1.00 |    0.00 |         - |          NA |
| ImmutableDictionary | 10000  |    630,488.18 ns |   3,040.379 ns |  2,695.216 ns |  8.15 |    0.05 |       1 B |          NA |
| FrozenDictionary    | 10000  |     43,957.48 ns |     274.398 ns |    256.672 ns |  0.57 |    0.00 |         - |          NA |
|                     |        |                  |                |               |       |         |           |             |
| Dictionary          | 100000 |  1,126,207.11 ns |   5,941.069 ns |  5,266.603 ns |  1.00 |    0.00 |       1 B |        1.00 |
| ImmutableDictionary | 100000 | 11,194,516.67 ns | 106,626.230 ns | 99,738.242 ns |  9.94 |    0.12 |      12 B |       12.00 |
| FrozenDictionary    | 100000 |    806,004.77 ns |   5,670.946 ns |  5,304.606 ns |  0.72 |    0.01 |       1 B |        1.00 |

As you can see, except for very small collections, the FrozenDictionary is about 43% faster than using a Dictionary, much faster than an ImmutableDictionary, without allocating more memory.

Scenario 2 — no keys are found

For this scenario I’m going to initialize a collection of unique keys, populate all three dictionaries accordingly, convert all keys to negative numbers to ensure the lookups are all different but will never match, and then run the TryGetValue for all returning the latest found using the Dictionary test as the baseline.

[SimpleJob(RuntimeMoniker.Net80)]
[MemoryDiagnoser]
public class TryGetValueNoKeysFound
{
    [Params(10, 100, 1000, 10000, 100000)]
    public int Size;

    private int[] _keys;

    private Dictionary<int, int> _dictionary;
    private ImmutableDictionary<int,int> _immutableDictionary;
    private FrozenDictionary<int, int> _frozenDictionary;

    [GlobalSetup]
    public void Setup()
    {
        var random = new Random(123);

        var uniqueKeys = new HashSet<int>(Size);
        for (var i = 0; i < Size; i++)
        {
            int key;
            do
            {
                key = random.Next();
            } while (uniqueKeys.Contains(key));

            uniqueKeys.Add(key);
        }

        _dictionary = uniqueKeys.Select((key, idx) => (key, idx)).ToDictionary(e => e.key, e => e.idx);
        _immutableDictionary = uniqueKeys.Select((key, idx) => (key, idx)).ToImmutableDictionary(e => e.key, e => e.idx);
        _frozenDictionary = uniqueKeys.Select((key, idx) => (key, idx)).ToFrozenDictionary(e => e.key, e => e.idx);

        // convert all keys to negative numbers to ensure no matches
        _keys = uniqueKeys.Select(key => -key).ToArray();
    }

    [Benchmark(Baseline = true)]
    public int Dictionary()
    {
        var latestValue = -1;

        foreach (var key in _keys)
        {
            if (_dictionary.TryGetValue(key, out var value))
                latestValue = value;
        }

        return latestValue;
    }

    [Benchmark]
    public int ImmutableDictionary()
    {
        var latestValue = -1;

        foreach (var key in _keys)
        {
            if (_immutableDictionary.TryGetValue(key, out var value))
                latestValue = value;
        }

        return latestValue;
    }

    [Benchmark]
    public int FrozenDictionary()
    {
        var latestValue = -1;

        foreach (var key in _keys)
        {
            if (_frozenDictionary.TryGetValue(key, out var value))
                latestValue = value;
        }

        return latestValue;
    }
}

The benchmark results are the following:

| Method              | Size   | Mean            | Error        | StdDev       | Ratio | RatioSD | Allocated | Alloc Ratio |
|-------------------- |------- |----------------:|-------------:|-------------:|------:|--------:|----------:|------------:|
| Dictionary          | 10     |        37.13 ns |     0.740 ns |     0.823 ns |  1.00 |    0.00 |         - |          NA |
| ImmutableDictionary | 10     |        33.81 ns |     0.629 ns |     0.588 ns |  0.91 |    0.03 |         - |          NA |
| FrozenDictionary    | 10     |        19.16 ns |     0.129 ns |     0.114 ns |  0.51 |    0.01 |         - |          NA |
|                     |        |                 |              |              |       |         |           |             |
| Dictionary          | 100    |       396.11 ns |     2.697 ns |     2.522 ns |  1.00 |    0.00 |         - |          NA |
| ImmutableDictionary | 100    |       488.48 ns |     2.480 ns |     2.198 ns |  1.23 |    0.01 |         - |          NA |
| FrozenDictionary    | 100    |       218.70 ns |     1.530 ns |     1.431 ns |  0.55 |    0.00 |         - |          NA |
|                     |        |                 |              |              |       |         |           |             |
| Dictionary          | 1000   |     4,019.84 ns |    38.187 ns |    35.720 ns |  1.00 |    0.00 |         - |          NA |
| ImmutableDictionary | 1000   |     6,708.41 ns |    14.893 ns |    13.931 ns |  1.67 |    0.02 |         - |          NA |
| FrozenDictionary    | 1000   |     2,372.01 ns |    15.113 ns |    13.398 ns |  0.59 |    0.00 |         - |          NA |
|                     |        |                 |              |              |       |         |           |             |
| Dictionary          | 10000  |    83,803.51 ns |   232.996 ns |   206.545 ns |  1.00 |    0.00 |         - |          NA |
| ImmutableDictionary | 10000  |    88,593.46 ns |   763.681 ns |   714.347 ns |  1.06 |    0.01 |         - |          NA |
| FrozenDictionary    | 10000  |    29,071.40 ns |    85.885 ns |    76.135 ns |  0.35 |    0.00 |         - |          NA |
|                     |        |                 |              |              |       |         |           |             |
| Dictionary          | 100000 | 1,293,765.26 ns | 3,587.916 ns | 3,356.139 ns |  1.00 |    0.00 |       1 B |        1.00 |
| ImmutableDictionary | 100000 | 1,145,366.16 ns | 4,726.433 ns | 4,421.108 ns |  0.89 |    0.00 |       1 B |        1.00 |
| FrozenDictionary    | 100000 |   475,573.09 ns | 2,445.081 ns | 2,167.501 ns |  0.37 |    0.00 |         - |        0.00 |

As you can see, the FrozenDictionary is on average 47% faster than a Dictionary for all sizes and even uses less memory for bigger collections. The ImmutableDictionary, once again, is the worse performer.

Conclusion

Microsoft with the release of .NET 8 is, once again, providing a lot of performance improvements that developers can use in their applications.

For this article in particular, if you are storing key-value reference data that is immutable, populated a single time and can be shared across your application, the FrozenDictionary may be a good option if performance is of concern.

Soon I’ll also do a benchmark for FrozenSet which I expect should demonstrate similar results.