Readonly, Immutable, and Frozen Collections in .NET

July 1, 2024 4 minutes read

In modern software development, immutability is a powerful concept. The .NET Base Class Library (BCL) offers readonly, immutable, and frozen collections. This terminology might be confusing, but each term addresses a different scenario where immutability plays a central role:

Readonly: Provides a readonly view of a mutable collection.
Immutable: Allow thread-safe modifications by creating a new instance for each change.
Frozen: Rely on the fact that a set is immutable to offer faster read and search operations.

Index

Readonly, Immutable and Frozen through Example

Let’s illustrate these concepts with this program:

using System.Collections.Frozen;
using System.Collections.Immutable;
using System.Collections.ObjectModel;

List<int> list = new List<int> { 0, 1 };
ReadOnlyCollection<int> readonlyCollection = list.AsReadOnly();
FrozenSet<int> frozenSet = list.ToFrozenSet();
ImmutableList<int> immutableList = list.ToImmutableList();

list.Add(2);

Assert.IsTrue(list.Count == 3);
Assert.IsTrue(readonlyCollection.Count == 3);
Assert.IsFalse(ReferenceEquals(list, readonlyCollection));
Assert.IsTrue(readonlyCollection[2] == 2);
// readonlyCollection.Add()   no such method
list[2] = 10;
Assert.IsTrue(readonlyCollection[2] == 10);


Assert.IsTrue(immutableList.Count == 2);
Assert.IsFalse(ReferenceEquals(list, immutableList));

ImmutableList<int> immutableListWith3Items = immutableList.Add(4);
Assert.IsFalse(ReferenceEquals(immutableList, immutableListWith3Items ));
Assert.IsTrue(immutableList.Count == 2);
Assert.IsTrue(immutableListWith3Items.Count == 3);
Assert.IsTrue(immutableListWith3Items[2] == 4);


Assert.IsTrue(frozenSet.Count == 2);
Assert.IsFalse(ReferenceEquals(list, frozenSet));
// frozenSet.Add()  no such method   
// frozenSet[1]     no such access since it is a set and not a list


static class Assert {
   public static void IsTrue(bool b) { System.Diagnostics.Debug.Assert(b); }
   public static void IsFalse(bool b) { System.Diagnostics.Debug.Assert(!b); }
}

using System.Collections.Frozen;

using System.Collections.Immutable;

using System.Collections.ObjectModel;

List<int> list = new List<int> { 0, 1 };

ReadOnlyCollection<int> readonlyCollection = list.AsReadOnly();

FrozenSet<int> frozenSet = list.ToFrozenSet();

ImmutableList<int> immutableList = list.ToImmutableList();

list.Add(2);

Assert.IsTrue(list.Count == 3);

Assert.IsTrue(readonlyCollection.Count == 3);

Assert.IsFalse(ReferenceEquals(list, readonlyCollection));

Assert.IsTrue(readonlyCollection[2] == 2);

// readonlyCollection.Add() no such method

list[2] = 10;

Assert.IsTrue(readonlyCollection[2] == 10);

Assert.IsTrue(immutableList.Count == 2);

Assert.IsFalse(ReferenceEquals(list, immutableList));

ImmutableList<int> immutableListWith3Items = immutableList.Add(4);

Assert.IsFalse(ReferenceEquals(immutableList, immutableListWith3Items ));

Assert.IsTrue(immutableList.Count == 2);

Assert.IsTrue(immutableListWith3Items.Count == 3);

Assert.IsTrue(immutableListWith3Items[2] == 4);

Assert.IsTrue(frozenSet.Count == 2);

Assert.IsFalse(ReferenceEquals(list, frozenSet));

// frozenSet.Add() no such method

// frozenSet[1] no such access since it is a set and not a list

static class Assert {

public static void IsTrue(bool b) { System.Diagnostics.Debug.Assert(b); }

public static void IsFalse(bool b) { System.Diagnostics.Debug.Assert(!b); }

}

From this program we can infer that:

A ReadOnlyList is a readonly view of the original collection it was created from. Therefore, if you update the original list, the ReadOnlyList reflects those changes. However, given a ReadOnlyList reference we cannot mutate the internal state of the list itself.
Unlike a readonly list, an immutable list is a new collection itself, not just a view of another collection. Once you hold a reference to a ImmutableList<T> you know it won’t change once created. However, this class presents modification methods like Add(), Remove(), Replace(), Clear()… that results in a new collection instance.
A frozen collection cannot be a list since only FrozenSet<T> and FrozenDictionary<TKey,TValue> are available in the namespace System.Collections.Frozen. Let’s see what is so special with frozen sets.

Why Frozen Sets?

FrozenSet<T> and FrozenDictionary<TKey,TValue> were introduced in .NET 8 to provide faster read access to sets and dictionaries. Indeed, ImmutableSet<T> and ImmutableDictionary<TKey,TValue> internally share memory through AVL trees between instances. This avoids memory waste and speeds up modifications (such as with the Add() method). Compared to good old HashSet<T> and Dictionary<TKey,TValue>, this design makes them faster for change operations but slower for read operations.

This is where frozen sets come into play. They are optimized for scenarios where you are creating an immutable collection optimized for reads and may be willing to spend more time creating the collection. This trade-off is worthwhile because creation happens infrequently, ensuring that read operations are as fast as possible. Frozen sets are suitable for create once, use a lot scenarios.

Frozen sets are faster to enumerate and read

Let’s run this benchmark:

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

BenchmarkRunner.Run<Benchmarks>();

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Benchmarks {
   private const int COUNT = 10_000;

   private static readonly Dictionary<int, int> Dictionary = new Dictionary<int, int>(Enumerable.Range(0, COUNT).ToDictionary(x => x, x => x));
   private static readonly ImmutableDictionary<int, int> ImmutableDictionary = ImmutableDictionary.CreateRange(Enumerable.Range(0, COUNT).ToDictionary(x => x, x => x));
   private static readonly FrozenDictionary<int, int> FrozenDictionary = FrozenDictionary.ToFrozenDictionary(Enumerable.Range(0, COUNT).ToDictionary(x => x, x => x));

   [Benchmark]
   public int DictionaryRead() {
      int sum = 0;
      for (int i = 0; i < COUNT; i++) {
         sum += Dictionary[i];
      }
      return sum;
   }

   [Benchmark]
   public int ImmutableDictionaryRead() {
      int sum = 0;
      for (int i = 0; i < COUNT; i++) {
         sum += ImmutableDictionary[i];
      }
      return sum;
   }

   [Benchmark(Baseline = true)]
   public int FrozenDictionaryRead() {
      int sum = 0;
      for (int i = 0; i < COUNT; i++) {
         sum += FrozenDictionary[i];
      }
      return sum;
   }
}

using BenchmarkDotNet.Attributes;

using BenchmarkDotNet.Running;

using System.Collections.Frozen;

using System.Collections.Immutable;

BenchmarkRunner.Run<Benchmarks>();

[HideColumns("Error", "StdDev", "Median", "RatioSD")]

public class Benchmarks {

private const int COUNT = 10_000;

private static readonly Dictionary<int, int> Dictionary = new Dictionary<int, int>(Enumerable.Range(0, COUNT).ToDictionary(x => x, x => x));

private static readonly ImmutableDictionary<int, int> ImmutableDictionary = ImmutableDictionary.CreateRange(Enumerable.Range(0, COUNT).ToDictionary(x => x, x => x));

private static readonly FrozenDictionary<int, int> FrozenDictionary = FrozenDictionary.ToFrozenDictionary(Enumerable.Range(0, COUNT).ToDictionary(x => x, x => x));

[Benchmark]

public int DictionaryRead() {

int sum = 0;

for (int i = 0; i < COUNT; i++) {

sum += Dictionary[i];

}

return sum;

}

[Benchmark]

public int ImmutableDictionaryRead() {

int sum = 0;

for (int i = 0; i < COUNT; i++) {

sum += ImmutableDictionary[i];

}

return sum;

}

[Benchmark(Baseline = true)]

public int FrozenDictionaryRead() {

int sum = 0;

for (int i = 0; i < COUNT; i++) {

sum += FrozenDictionary[i];

}

return sum;

}

Here are the results:

Method	Mean	Ratio
DictionaryRead	46.68 us	1.81
ImmutableDictionaryRead	388.04 us	15.09
FrozenDictionaryRead	25.72 us	1.00

Frozen sets optimization for certain keys

If we examine the source code of the ToFrozenSet() method, we see that it analyzes the input collection to select one of several optimized implementations of a frozen set. For example, when using strings as keys with Ordinal or OrdinalIgnoreCase, specific optimizations are applied:

Length-based Hashing: Hashing is based on string length when appropriate.
Key Analysis on Construction: During construction, keys are analyzed to determine if a substring provides sufficient variance. For instance, keys like Item1, Item2…Item7 are hashed only on the last character, speeding up the process compared to hashing the entire string.
Deterministic Hashing: Faster hashing methods are used where determinism is safe.
ASCII Optimizations: For case-insensitive keys, faster ASCII-based hashing is sometimes used.
Safe Case Sensitivity: In some cases, even a case-insensitive dictionary can use case-sensitive comparisons if deemed safe. For example, a case-insensitive dictionary with keys ["678", "139", ..., "801"] can safely use case-sensitive hashing.

Here is a benchmark on a set with various strings with different lengths:

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

BenchmarkRunner.Run<Benchmarks>();

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Benchmarks {
   private static readonly HashSet<string> HashSet = new(StringComparer.OrdinalIgnoreCase) {
      "BMW",
      "Ford",
      "Honda",
      "Toyota",
      "Hyundai",
      "Mercedes",
      "Chevrolet",
      "Volkswagen",
      "Rolls-Royce",
      "Mitsubishi Motors"
    };
   private static readonly FrozenSet<string> FrozenSet = HashSet.ToFrozenSet(StringComparer.OrdinalIgnoreCase);

   [Benchmark(Baseline = true)]
   public bool HashSet_Contains() => HashSet.Contains("Audi");

   [Benchmark]
   public bool FrozenSet_Contains() => FrozenSet.Contains("Audi");
}

using BenchmarkDotNet.Attributes;

using BenchmarkDotNet.Running;

using System.Collections.Frozen;

BenchmarkRunner.Run<Benchmarks>();

[HideColumns("Error", "StdDev", "Median", "RatioSD")]

public class Benchmarks {

private static readonly HashSet<string> HashSet = new(StringComparer.OrdinalIgnoreCase) {

"BMW",

"Ford",

"Honda",

"Toyota",

"Hyundai",

"Mercedes",

"Chevrolet",

"Volkswagen",

"Rolls-Royce",

"Mitsubishi Motors"

};

private static readonly FrozenSet<string> FrozenSet = HashSet.ToFrozenSet(StringComparer.OrdinalIgnoreCase);

[Benchmark(Baseline = true)]

public bool HashSet_Contains() => HashSet.Contains("Audi");

[Benchmark]

public bool FrozenSet_Contains() => FrozenSet.Contains("Audi");

}

Here are the results:

Method	Mean	Ratio
HashSet_Contains	8.315 ns	1.00
FrozenSet_Contains	6.641 ns	0.80

Immutable set’s thread-safe modifications are faster than on the regular sets

Finally, let’s benchmark that thread-safe modifications on ImmutableSet<T> are indeed faster than recreating a set for each change through the regular HashSet<T> class:

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

BenchmarkRunner.Run<Benchmarks>();

[HideColumns("Error", "StdDev", "Median", "RatioSD")]
public class Benchmarks {
      private const int COUNT = 10_000;

      [Benchmark(Baseline = true)]
      public HashSet<int> HashSetAdds() {
         HashSet<int> h = new();
         for (int i = 0; i < COUNT; i++) {
            var newH = new HashSet<int>(h);
            newH.Add(i);
            h = newH;
         }
         return h;
      }

      [Benchmark]
      public ImmutableHashSet<int> ImmutableHashSetAdds() {
         ImmutableHashSet<int> ih = ImmutableHashSet<int>.Empty;
         for (int i = 0; i < COUNT; i++) {
            ih = ih.Add(i);
         }
         return ih;
      }
   }

using BenchmarkDotNet.Attributes;

using BenchmarkDotNet.Running;

using System.Collections.Immutable;

BenchmarkRunner.Run<Benchmarks>();

[HideColumns("Error", "StdDev", "Median", "RatioSD")]

public class Benchmarks {

private const int COUNT = 10_000;

[Benchmark(Baseline = true)]

public HashSet<int> HashSetAdds() {

HashSet<int> h = new();

for (int i = 0; i < COUNT; i++) {

var newH = new HashSet<int>(h);

newH.Add(i);

h = newH;

}

return h;

}

[Benchmark]

public ImmutableHashSet<int> ImmutableHashSetAdds() {

ImmutableHashSet<int> ih = ImmutableHashSet<int>.Empty;

for (int i = 0; i < COUNT; i++) {

ih = ih.Add(i);

}

return ih;

}

Here are the results:

Method	Mean	Ratio
HashSetAdds	94.080 ms	1.00
ImmutableHashSetAdds	4.067 ms	0.04

Conclusion

Readonly, immutable, and frozen collections in .NET harness immutability to handle various scenarios.

Readonly collections provide an immutable view of a mutable collection. This is useful for example, to ensure that a method won’t modify the collection passed to it.
Immutable collections are unmodifiable but allow new instances upon changes. This is similar to string.Replace(x, y), where changes create a new string returned by this method. They are useful for thread-safe modifications.
Frozen sets are optimized for create once – use often scenarios. They are usually faster than HashSet<T> and Dictionary<TKey,TValue> in these situations.

Readonly, Immutable and Frozen through Example

Why Frozen Sets?

Frozen sets are faster to enumerate and read

Frozen sets optimization for certain keys

Immutable set’s thread-safe modifications are faster than on the regular sets

Conclusion

Share this:

Make your .NET code beautiful with NDepend