.NET Benchmark of Frozen, Immutable, and normal Generic Collections

CollectionsBenchmarks.cs

// SPDX-License-Identifier: Unlicense
// Inspired by https://okyrylchuk.dev/blog/when-to-use-frozen-collections-in-dotnet/

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

namespace Benchmark.Conceptual;

[ShortRunJob]
public class CollectionsBenchmarks
{
    [Params(1_000)]
    public int CollectionSize { get; set; }

    [Params(1, 2, 10, 100)]
    public int MissRatio { get; set; }

    public int IterationCount { get; set; } = 100_000;
    
    private List<int> _list = null!;
    private SortedList<int, int> _sortedList = null!;
    private ImmutableList<int> _immutableList = null!;
    private HashSet<int> _hashSet = null!;
    private ImmutableHashSet<int> _immutableSet = null!;
    private ImmutableSortedSet<int> _immutableSortedSet = null!;
    private FrozenSet<int> _frozenSet = null!;

    private Random _random = null!;

    [IterationSetup]
    public void SetUpIteration()
    {
        _random = new(69);
    }

    [GlobalSetup]
    public void SetUp()
    {
        _list = Enumerable.Range(0, CollectionSize).ToList();
        _immutableList = Enumerable.Range(0, CollectionSize).ToImmutableList();
        _sortedList = new();
        foreach (var i in Enumerable.Range(0, CollectionSize))_sortedList.Add(i, i);
        _hashSet = Enumerable.Range(0, CollectionSize).ToHashSet();
        _immutableSet = Enumerable.Range(0, CollectionSize).ToImmutableHashSet();
        _immutableSortedSet = Enumerable.Range(0, CollectionSize).ToImmutableSortedSet();
        _frozenSet = Enumerable.Range(0, CollectionSize).ToFrozenSet();
    }

    [Benchmark(Baseline = true)]
    public bool LookupList()
    {
        var found = false;
        for (var i = 0; i < IterationCount; i++)
            found ^= _list.Contains(_random.Next(CollectionSize * MissRatio));
        return found;
    }

    [Benchmark]
    public bool LookupImmutableList()
    {
        var found = false;
        for (var i = 0; i < IterationCount; i++)
            found ^= _immutableList.Contains(_random.Next(CollectionSize * MissRatio));
        return found;
    }
    
    [Benchmark]
    public bool LookupSortedList()
    {
        var found = false;
        for (var i = 0; i < IterationCount; i++)
            found ^= _sortedList.ContainsKey(_random.Next(CollectionSize * MissRatio));
        return found;
    }

    [Benchmark]
    public bool LookupHashSet()
    {
        var found = false;
        for (var i = 0; i < IterationCount; i++)
            found ^= _hashSet.Contains(_random.Next(CollectionSize * MissRatio));
        return found;
    }

    [Benchmark]
    public bool LookupImmutableSet()
    {
        var found = false;
        for (var i = 0; i < IterationCount; i++)
            found ^= _immutableSet.Contains(_random.Next(CollectionSize * MissRatio));
        return found;
    }
    
    [Benchmark]
    public bool LookupImmutableSortedSet()
    {
        var found = false;
        for (var i = 0; i < IterationCount; i++)
            found ^= _immutableSortedSet.Contains(_random.Next(CollectionSize * MissRatio));
        return found;
    }

    [Benchmark]
    public bool LookupFrozenSet()
    {
        var found = false;
        for (var i = 0; i < IterationCount; i++)
            found ^= _frozenSet.Contains(_random.Next(CollectionSize * MissRatio));
        return found;
    }
}

Method	CollectionSize	MissRatio	Mean	Error	StdDev	Ratio	RatioSD
LookupList	1000	1	7.796 ms	8.4897 ms	0.4654 ms	1.00	0.07
LookupImmutableList	1000	1	187.899 ms	47.3904 ms	2.5976 ms	24.16	1.24
LookupSortedList	1000	1	7.146 ms	1.0473 ms	0.0574 ms	0.92	0.05
LookupHashSet	1000	1	1.327 ms	0.4994 ms	0.0274 ms	0.17	0.01
LookupImmutableSet	1000	1	5.995 ms	0.3760 ms	0.0206 ms	0.77	0.04
LookupImmutableSortedSet	1000	1	10.665 ms	1.4369 ms	0.0788 ms	1.37	0.07
LookupFrozenSet	1000	1	1.067 ms	0.2008 ms	0.0110 ms	0.14	0.01
LookupList	1000	2	9.350 ms	1.1671 ms	0.0640 ms	1.00	0.01
LookupImmutableList	1000	2	296.108 ms	76.6593 ms	4.2020 ms	31.67	0.43
LookupSortedList	1000	2	5.186 ms	0.5252 ms	0.0288 ms	0.55	0.00
LookupHashSet	1000	2	2.234 ms	0.2787 ms	0.0153 ms	0.24	0.00
LookupImmutableSet	1000	2	4.055 ms	0.3990 ms	0.0219 ms	0.43	0.00
LookupImmutableSortedSet	1000	2	9.074 ms	0.3077 ms	0.0169 ms	0.97	0.01
LookupFrozenSet	1000	2	1.970 ms	0.2050 ms	0.0112 ms	0.21	0.00
LookupList	1000	10	12.448 ms	36.4844 ms	1.9998 ms	1.02	0.20
LookupImmutableList	1000	10	372.268 ms	23.4114 ms	1.2833 ms	30.40	4.02
LookupSortedList	1000	10	3.110 ms	2.3266 ms	0.1275 ms	0.25	0.03
LookupHashSet	1000	10	1.584 ms	1.0789 ms	0.0591 ms	0.13	0.02
LookupImmutableSet	1000	10	2.164 ms	0.8137 ms	0.0446 ms	0.18	0.02
LookupImmutableSortedSet	1000	10	7.886 ms	1.2928 ms	0.0709 ms	0.64	0.09
LookupFrozenSet	1000	10	1.233 ms	0.0917 ms	0.0050 ms	0.10	0.01
LookupList	1000	100	11.128 ms	0.5924 ms	0.0325 ms	1.00	0.00
LookupImmutableList	1000	100	392.115 ms	30.9123 ms	1.6944 ms	35.24	0.16
LookupSortedList	1000	100	2.579 ms	0.2940 ms	0.0161 ms	0.23	0.00
LookupHashSet	1000	100	1.360 ms	0.0866 ms	0.0047 ms	0.12	0.00
LookupImmutableSet	1000	100	1.701 ms	1.2868 ms	0.0705 ms	0.15	0.01
LookupImmutableSortedSet	1000	100	7.573 ms	0.9149 ms	0.0501 ms	0.68	0.00
LookupFrozenSet	1000	100	1.068 ms	0.1726 ms	0.0095 ms	0.10	0.00

Yes. You read that right.

There is an upfront cost to creating these sets, of course. And they cannot be mutated.