March 2017

Volume 32 Number 3

[.NET Framework]

Immutable Collections

By Hadi Brais | March 2017

Side effects compromise the understandability and correctness of code. A method that mutates global or static variables has side effects. A method that mutates some of its parameters has side effects. If you want to understand a piece of code, you have to go through the code of all methods that are called and have side effects. Methods with side effects require thread synchronization to execute correctly when there are multiple threads.

What if you write methods that don’t have side effects? What would the code look like and how would it perform? You can find out by making instances immutable so that side effects can’t occur.

Generally, when an instance of a type is described to be immut­able, it means that its value never changes. Immutability, like many things in software engineering, is a design choice. You don’t really have to use it, but in some scenarios, you can benefit from it in terms of code performance or understandability. It’s actually often useful that it’s one of the fundamental principles of the successful functional programming paradigm. Considering that F# is a functional-first language, all instances are immutable unless explicitly specified otherwise. On the other hand, C# is an object-oriented-­first language in which all instances are mutable unless explicitly specified otherwise. In this article, I’ll show you how to leverage immutability in C#. But first, I’ll define immutability in the context of this article.

Defining Immutability

Technically, there are many kinds of immutability. Any type that somewhat restricts changes to its state or the state of its instances can be described as immutable in some sense. The System.String type is an immutable type in the sense that the size of the string, the characters, and their order can’t change. The System.MulticastDelegate type, which is the parent of all delegate types, is immutable just like System.String. Both use an array as an underlying data structure and make a copy of it to satisfy a requested change, no matter how small the change is. For more information on the kinds of immutability, please refer to the article at bit.ly/2kGVx4Z.

The System.Collections.ObjectModel.ReadOnlyCollection<T> is not immutable but it implements an immutable interface for a given mutable IList<T> object. This interface doesn’t let the consumer change the number of items in the collection or their relative order. However, it doesn’t say anything about immutability of the individual items, which depends on the whole type hierarchy of T. Of course, code that has a reference to the underlying list can change it without constraints.

The immutable collections discussed in this article provide yet a different kind of immutability. To motivate the need for them, consider the following example:

A typical text editor provides several features or tools (such as spellcheck or code analysis) that analyze or process text that the user has written. With the prevalence of multicore computers, these tools can be run in the background while the user types. If you’re not careful, you might run into thread-safety issues. The background analyzer reads the buffer containing the text at the same time the user is modifying it. Now, imagine instead of a buffer, the background process would logically get a snapshot of the text.

How can you achieve this correctly and efficiently? Using a type like String correctly solves the problem, but not efficiently. This would let the user change the text concurrently while the tool is running, but with every change, a new copy of the text is made, which can be slow and wasteful of memory for large documents. Another correct solution would be to use a mutable type, such as System.Text.StringBuilder. But this is also inefficient because the tool needs to make a copy of it under an acquired lock and the user wouldn’t be able to make any changes until a copy is made. Using ReadOnlyCollection<T> wouldn’t do any good, either, because the underlying collection is mutable and shared.

You need a different kind of immutability that enables you to make changes safely without using expensive thread synchronization mechanisms, while sharing as much data as possible between threads with no or little copying required. Immutable collections provide exactly this kind of immutability, known as persistence. They’re not only useful in the scenario described earlier, but also in other multi- and single-threaded scenarios, as you’ll see later in this article.

This article provides a detailed discussion of the design, implementation and performance of immutable collections to enable you to effectively use them and even write your own immutable collections and types. These collections can be used on any .NET platform that supports the .NET Standard 1.0 and later (which means you can use them on all Windows platforms, Xamarin and .NET Core). Immutable collections are relatively new and distributed as a NuGet package, so they aren’t used by the .NET Framework itself, even though there are many framework APIs for which immutable collections would’ve been beneficial. Instead, such APIs use the potentially less-ideal ReadOnlyCollection<T> or use a copy of a mutable collection. I’ll use the package version 1.3.0. The source code is available as part of CoreFX.

Note that it’s possible to use unsafe code or Reflection to break almost any immutability guarantees. In general, when a type is described to be immutable, there’s an implicit caveat made that these techniques can circumvent any immutability guarantees. This applies to the immutable collections discussed in this article.

Defining Immutable Collections

Before I discuss the internals of immutable collections, I have to define what they are. An immutable collection is a collection of instances that preserves its structure all the time and disallows element-level assignments, while still offering APIs to perform mutations. By the structure of a collection, I mean the number of elements and their relative order (which is determined by their indices in the case of an array structure and by their links in the case of a linked structure).

For example, if you push an element onto an ImmutableStack<T>, you’ll get two isolated immutable stacks: one with the new element and one without. On the other hand, pushing an element onto a mutable Stack<T> effectively changes the stack and you’ll only have one stack that contains the new element. Note that both immutable and mutable collections do not offer any guarantees regarding the elements themselves. If T was Int32 or String, then the elements would be immutable, as well. But if T was something like StringBuilder, then the elements are very much mutable.

In order to construct any immutable object, it has to be initialized. Therefore, during initialization, the object is mutable. Once a reference to the object has been published (by returning it from a non-private method), the object becomes effectively immutable for the rest of its lifetime.

The immutable collections are designed with two goals in mind. First, to reuse as much memory as possible, to avoid copying, and to reduce pressure on the garbage collector (such implementation is usually called persistent). The second goal is to support the same operations offered by mutable collections with competitive time complexities.

Immutable Stacks

The mutable Stack<T> type is implemented using an array. Arrays, however, aren’t suitable for immutable collections because the only way to preserve the current instance is by copying the whole array and performing the change on that new array. This would make the immutable stack unacceptably slow. Linked lists can be elegantly used to implement it. Each element contains a pointer to the element below it (or null for the bottom element). An immutable stack is represented as a pointer to the top element. This way, you can push and pop elements of a given stack without changing it, while at the same time sharing all of its elements with the resulting stack. This simple design makes the immutable stack the simplest immutable collection. I show the differences between the mutable and immutable stacks further in this article.

Let’s see how to create and use immutable stacks. The Immut­ableStack<T> and all other immutable collections are defined in the System.Collections.Immutable namespace. To maximize sharing of memory, immutable collections don’t offer any public constructors. In order to create an instance of an immutable collection, you have to use one of the CreateXxx<T> methods defined in a static type that corresponds to the immutable collection. For the immut­able stack, this type is called ImmutableStack and it offers the following factory methods:

public static ImmutableStack<T> Create<T>();
public static ImmutableStack<T> Create<T>(T item);
public static ImmutableStack<T> Create<T>(params T[] items);
public static ImmutableStack<T> CreateRange<T>(IEnumerable<T> items);

All the methods have a generic type parameter T that specifies the type of the items stored in the collection. The first method creates an empty immutable stack, which internally simply returns the singleton ImmutableStack<T>.Empty. The second method creates a stack with the specified item pushed onto it, which is equivalent to ImmutableStack<T>.Empty.Push(item). The third and fourth methods create a stack with the specified items pushed onto it in order. The CreateRange<T> method is implemented as follows:

var stack = ImmutableStack<T>.Empty;
foreach (var item in items)
{
  stack = stack.Push(item);
}
return stack;

All the factory methods for all the immut­able collections are provided for convenience. All of them internally start with the empty collection and add the specified items to it. The items are always copied shallowly.

Now consider the following sequence of operations beginning with the empty stack:

ImmutableStack<Int32> s1 = ImmutableStack<Int32>.Empty;
ImmutableStack<Int32> s2 = s1.Push(1);
ImmutableStack<Int32> s3 = s2.Push(2);
ImmutableStack<Int32> s4 = s3.Push(3);
ImmutableStack<Int32> s5 = s4.Push(4);
ImmutableStack<Int32> s6 = s4.Pop();
ImmutableStack<Int32> s7 = s6.Pop();

Notice that the Push and Pop methods return a reference to the resulting immutable stack. In contrast, the Push and Pop methods of the mutable Stack<T> return void and T, respectively. This design reflects the fact that changing an immutable stack conceptually results in a whole different stack, while changing a mutable stack actually changes the stack. If the same sequence of operations is performed on a mutable stack, then you’ll get a different end result, as shown in Figure 1. What makes the immutable stack immutable is that there’s no way to change the pointers and values of nodes.

A Change to an Immutable Stack Results in a Different Stack in Contrast to Mutable Stacks
Figure 1 A Change to an Immutable Stack Results in a Different Stack in Contrast to Mutable Stacks

Note that the empty immutable stack node stores the default value of T, which is 0 for Int32. Also, the mutable stack only sets the values of popped items to the default value rather than shrinking the size of the array. The unoccupied part of the array is called slack space.

To get the item at the top of an immutable stack, you can either use the Peek method or another overload of Push, which has an out parameter through which the item is returned.

Immutable Lists

The list data structure is more complex than the stack mainly due to the indexing operation. The list structure offers item retrieval, addition and removal at a specified index. Using an array, as done in the mutable List<T>, would be reasonable, but, as explained earlier, would be inefficient for a general-purpose immutable list. Using a linked list is also not suitable because you have to potentially traverse many elements to reach the item at a specific index. Instead, balanced binary trees let you implement all operations with respectable performance. Most immutable collections are imple­mented using balanced binary trees. The rest use linked lists and only one, namely the immutable array, uses arrays as explained in the next section.

Every node in the tree contains an item of the list and, therefore, has an index. The ImmutableList<T> type organizes the tree such that a depth-first, in-order traversal of the tree corresponds to a traversal of the list in order from the item at index 0 to the last item.

Consider the following program:

ImmutableList<Int32> l1 = ImmutableList.Create<Int32>();
ImmutableList<Int32> l2 = l1.Add(1);
ImmutableList<Int32> l3 = l2.Add(2);
ImmutableList<Int32> l4 = l3.Add(3);
ImmutableList<Int32> l5 = l4.Replace(2, 4);

Figure 2 shows what happens to the underlying binary tree while performing the sequence of operations starting with the empty immutable list. Each box represents a node in the tree. The box that contains the letter E represents the empty tree singleton (the arrows that point nowhere are to be interpreted as pointing to the E box). The boxes and arrows on the right side of the figure are immutable while those on the left are temporarily mutable. This is indicated by an internal Boolean flag called frozen. This flag serves two purposes, as I’ll explain next.

Internal State of Trees (Left) and the Publically Accessible State Resulting After Completing the Mutations (Right)
Figure 2 Internal State of Trees (Left) and the Publicly Accessible State Resulting After Completing the Mutations (Right)

To add the first item to the tree, a new node is created with both of its pointers pointing to the empty node. All newly created nodes start with the frozen flag set to false (temporarily mutable). At this point, nothing more needs to be done and, therefore, the tree is made immutable by setting the frozen flag to true as indicated on the right side of the figure. This makes the tree immutable for the rest of its lifetime.

To add a second item, due to the way the tree is organized, its node has to be the right child of the first node. But because that node is immutable, you can’t change its pointers. The only way to add the second item is to not only create a node for it, but also create another node for the first item. That’s why l2 and l3 will point to totally separate trees.

Similarly, the third item has to be the right child of the second node. The only way to add it is by creating new nodes for both the first and second items. However, this time the resulting tree is imbalanced. This situation occurs when the difference between the height of the left and right subtrees of the root is at least 2. To keep the tree balanced, you have to reorganize it so that it becomes the tree shown in the bottom right of Figure 2. You can do this because the tree is still mutable and no code outside the Immutable­List<T> type can access it or observe any of the mutations. Before a reference to the tree is returned, it’s frozen by setting the frozen flag of each node to true to make it immutable. This demonstrates the first purpose of the frozen flag.

The last line of code calls the Replace function, which finds the specified item and replaces it with another item. In this case, a new node is created to hold the new item and the other nodes of the same tree are reused in the new tree.

Because of the way the tree is organized, any single operation on the list ,whether its addition, insertion, removal or search has a time complexity of O(log N) where N is the number of items currently in the list. In contrast, operations on the mutable list List<T> are either O(1) (where the operation can be performed in place) or O(N) (where the underlying array needs to be copied).

You can quickly perform a single operation on an immutable list. But if you want to perform a large number M of operations consecutively, it will take O(M log N). You can do better by taking advantage of the frozen flag and lumping together all mutations. This optimization is offered by Builders.

Most immutable collections including ImmutableList<T> define types called builders that use the same underlying data structures and offer the same APIs. The difference is that a builder doesn’t set the frozen flag after every operation. It keeps any new nodes that have been created in a mutable state so that you can perform many operations more efficiently. The builder type for the immutable list is ImmutableList<T>.Builder.

To create a builder instance, you need an immutable collection instance. You can start with an empty collection and use the ImmutableList.CreateBuilder<T> static method or use the ToBuilder instance method on a given immutable collection. In the latter case, all existing nodes will remain, as promised, immutable. It’s only those new nodes that will be mutable. Once all operations are performed, you can call the ToImmutable instance method to freeze all nodes, effectively making the collection immutable. ImmutableList<T> provides several instance methods, such as AddRange and RemoveRange, that take a reference to IEnumerable<T> and use a Builder internally to perform the operation on the specified items.

Some operations don’t benefit from Builders and they’re inherently expensive. The Reverse instance method has to copy all non-leaf nodes in the tree to reverse the order of the items. The Sort instance method is implemented by copying all items to an array, sorting the array and then creating the immutable list from the sorted array.

The mutable List<T> uses an array internally. Inserting or removing items from the middle of the array requires creating a new array and copying all other items. Also allocating extremely large arrays may not be possible in a fragmented address space. The mutable LinkedList<T> solves both of these problems. ImmutableList<T> offers the advantages of both, but makes other operations less efficient. ImmutableList<T> is the immutable collection that corresponds to both List<T> and LinkedList<T>. Note that StringBuilder is essentially List<Char>.

Immutable Arrays

The ImmutableArray<T> type, like ImmutableList<T>, implements an immutable list, but in a different way. ImmutableArray<T> is just a thin wrapper around an array of type T[ ]. It’s “thin” because it’s a value type that contains a single reference-type field. The array itself is allocated from the managed heap. To perform any mutating operation, a copy is made of the whole array and the operation is performed on it. From this point of view, ImmutableArray<T> is a generalization of String, as it can represent strings of items of any type, not just Char.

All mutating operations take O(N) time using Immutable­Array<T>, but O(log N) time using ImmutableList<T>. However, ImmutableArray<T> is superior in three ways. First, it takes O(1) time to access an item given its index using ImmutableArray<T>, while O(log N) time using ImmutableList<T>. Second, while both implementations offer linear-time iteration, ImmutableArray<T> is cache-friendly because all items are stored consecutively. Iterating over an ImmutableArray<T> can be many times faster than iterating over an ImmutableList<T>. Third, Immutable­Array<T> consumes less memory because it doesn’t use pointers. In general, you might need to measure to determine which one to use in a particular situation. Both types implement the IImmutableList<T> interface. You can use this interface across your code to easily switch between the types.

As always, you can improve performance and reduce garbage collection (GC) pressure by performing bulk operations and pooling the Builder objects. You can either use the bulk operations methods XxxRange or ImmutableArray<T>.Builder, which is implemented similarly to List<T>.

Note that because the standard design of LINQ operators works on IEnumerable<T> references, applying them on the value type ImmutableArray<T> requires boxing. The immutable collections NuGet package includes an implementation of some LINQ operators designed specifically for ImmutableArray<T> to avoid boxing. It can be found in System.Linq.ImmutableArrayExtensions.

Immutable Dictionaries

The ImmutableDictionary<TKey, TValue> type uses a balanced binary tree to represent the dictionary. Each node in the tree contains an ImmutableList<KeyValuePair<TKey, TValue>> (which is also a balanced binary tree) that holds all the items that hash to the same value. On the other hand, the mutable Dictionary<TKey, TValue> uses an array of key-value pairs with open addressing for collision resolution. Overall, ImmutableDictionary<TKey, TValue> is many times slower and consumes much more mem­ory than Dictionary<TKey, TValue>. Using the dictionary builder only helps a little because the underlying structure is still a tree of trees. You should definitely measure performance when using ImmutableDictionary<TKey, TValue> to determine whether it’s acceptable or not. If it’s not, you might need to write your own customized immutable dictionary.

Performance and Memory Consumption of Immutable Collections

Now, even if using an immutable collection is principally ideal, it might not result in acceptable performance. That’s why it’s important to understand how they’re implemented and their impact on performance.

Let’s compare the performance of the immutable list against that of the mutable counterpart. You can find the time complexities of common operations on immutable collections at bit.ly/2ko07HS. This stuff doesn’t say much and it’s better to get a little more practical. I’ve written three programs that simply append or prepend 10 million 8-byte integers to a mutable list, an immutable list and an immutable list builder, respectively. Figure 3 shows the results. (The numbers shown are approximate. Time is in seconds. Memory is in megabytes. JIT optimizations are enabled. The default constructor is used to create the mutable list.)

Figure 3 Amount of Time and Memory Used by Mutable Lists, Immutable Lists and Immutable Arrays

  Mutable ImmutableList ILBuilder ImmutableArray IABuilder
Append 0.2 12 8 Horrible! 0.2
Prepend Horrible! 13.3 7.4 Horrible! Horrible!
32-bit size 128 320 320 128 128
64-bit size 128 480 480 128 128

Appending to a mutable list is cheap because it’s based on an array. The array is doubled in size occasionally, and after that, adding an item is a fast operation. On the other hand, adding an item to an immutable list is far more expensive because it’s based on a tree. Even when using the builder, it’s still about 40 times slower. That’s a huge difference. However, this isn’t  exactly a fair comparison. A fair comparison would be between the immutable list and a mutable list that uses thread synchronization to provide similar snapshot semantics. Still, this makes immutable collections much less attractive in single-­threading scenarios. Even though the time complexity is only O(log N), the hidden constant factor is quite large. I’ll explain why shortly.

It’s a whole different story for the prepend operation. It would take List<T> many hours to finish because it has to allocate and copy 10 million short-lived arrays of increasingly larger sizes. The immutable list and its builder maintained more or less the same performance.

Figure 4 shows part of the managed memory allocation graph generated using the Diagnostic Tools of Visual Studio 2015 while appending items to an immutable list. Markers at the top of the graph indicate recorded GCs of any generation. The graph shows that GCs happen frequently, about every several dozen milliseconds. I used PerfView to determine the total amount of time spent doing all those little GCs. Without using the builder, the GC time is about 4 seconds. This is the difference between using the immutable list directly and using the builder. To determine whether this difference is indeed due to GCs or whether it’s just a coincidence, I also used PerfView on the program that uses the builder. It turns out that this is indeed the case. This can be easily explained by looking at how each works. The immutable list creates many short-lived and medium-lived objects, while the builder mutates the pointers of existing objects. Using the immutable list directly triggered more than 100 GCs while using the builder and the mutable list triggered less than 10.

The GC Runs Much More Often When Appending Items to the Immutable List
Figure 4 The GC Runs Much More Often When Appending Items to the Immutable List

The builder is so much slower than the mutable list. There are four interlinked reasons for this. First, it uses a linked structure that incurs many cache misses. Second, after appending any two items, the tree becomes imbalanced and requires a rotation to rebalance it. Third, appending an item requires traversing (log N) nodes. Fourth, every time an item is added, it triggers a separate memory allocation for the hosting node.

This doesn’t mean that the GC is part of the problem. On the contrary, automatic memory management actually makes it a lot easier to write and use immutable collections. It automatically cleans up all those immutable objects that nobody is using.

Let’s compare also the immutable stack with the mutable stack. Such comparison lets you quantify the cost of object allocations and their associated cache misses (which are only a small part of the total cache misses that may occur later) resulting from using linked-data structures. The immutable stack is GC-friendly because it only allocates objects that will be part of the resulting stack. It’s so efficient that it doesn’t even have a Builder. Pushing 10 million 8-byte integers onto a mutable stack takes about 0.17 seconds, while pushing the same onto an immutable stack takes about 1 second. That’s about a 6x slowdown, which isn’t bad. Iterating over a large immutable stack or any linked structure can be many times slower compared to iterating over the corresponding mutable collection primarily because of cache misses and page faults (and transfers across NUMA nodes on NUMA architectures because of sharing).

That said, the array-based mutable collections suffer from the slack space wastage. If you remove most items from a large collection, the underlying array will not shrink and continue to unnecessarily occupy memory. Linked-based immutable collections always maintain one object per item. However, this is hardly an advantage for linked collections, considering typical use cases.

When to Use Immutable Collections

The fundamental benefit of immutability is that it makes it significantly easier to reason about how the code works, enabling you to quickly write correct and elegant code. Consider a single-threaded program. At a given line of code, you may be wondering about the state of an immutable collection. You can easily determine that by locating those locations in code where the collection was created. There’s usually only one or few such locations. By continuing this process, you’ll get to either a mutable source or the empty collection. It doesn’t matter if the immutable collection has been passed to methods because its structure is guaranteed to be preserved, so you don’t have to consider what happens in those methods. If the items were of an immutable type, as well, you’ll be able to reason about the full state of the collection. It’s equally easy in multi-threaded programs, but becomes far more difficult when using shared mutable collections. Therefore, immutability can be a general design principle as it is in functional programming.

Now, consider the following method signature:

void Foo<T>(Stack<T> s);

This method has a mutable stack parameter, so the stack could be modified by the method. This could, indeed, be the purpose of the method. But when it does modify the stack, the old state is lost unless the caller made a copy of it. Note that the method doesn’t have to return anything even if it modified the stack. One more thing that this signature conveys is that it doesn’t offer any thread-safety guarantees.

This is fine if thread safety isn’t a concern and if the method is expected to modify the stack and you’re interested in these modifications. If the purpose of the method is to only read or inspect the stack (or it might modify it, but the caller never cares about its modifications), then this signature might be more suitable:

void Foo<T>(ReadOnlyCollection<T> s);

There are two issues with this. First, ReadOnlyCollection<T> requires a List<T> to be constructed, so the caller has to copy the stack to a list. Making the parameter to be of the interface type IReadOnly­Collection<T> avoids this issue because Stack<T> implements it, but then the method could convert it back to Stack<T> just as easily. Second, if the method usually makes changes to the stack, it has to first copy it to a mutable collection. This signature also doesn’t offer any thread-safety guarantees. It’s only convenient when the original mutable collection is List<T> and the method doesn’t change it.

In scenarios where there are potentially multiple threads accessing the collection, this signature might be more suitable:

void Foo<T>(ConcurrentStack<T> s);

The concurrent stack is mutable, so all threads will see all the changes. This is only suitable when at least one of the following two conditions occur: Either the method is expected to consider changes potentially made by other threads as soon as they’re made, or other threads want to see the changes made by the method as soon as they’re made. Note that any thread can see any specific change separately. Otherwise, if some threads should only see a batch of changes or none of the changes, they have to acquire a global lock and make a private copy of the stack. These two situations are called snapshot semantics.

Notice how in various scenarios, different collection types need to be used. Also a good documentation would be desirable to explain how the method works or how it should be used. Immutable collections simplify all of this. The following two signatures satisfy most scenarios:

void Foo1<T>(ImmutableStack<T> s);
ImmutableStack<T> Foo2<T>(ImmutableStack<T> s);

Look how beautiful these APIs are. The first signature is used when no one cares about the changes made by the method. Otherwise, the second signature can be used. There are only two situations in which immutable collections are unsuitable: throughput (the rate at which items are processed) and producer-consumer semantics. As demonstrated earlier, the general-purpose immutable collections have inferior throughput, particularly in single-threaded scenarios. In producer-consumer semantics, concurrent mutable collections are more elegant and result in better performance. The difference between producer-consumer semantics and snapshot semantics is in how the reading or consuming agents behave. In the former, elements get consumed (removed permanently) while in the latter, elements get processed and would only be removed by the writing or producing agents. I would like to refer to snapshot semantics as changer-processor semantics because there are changing agents and processing agents. Processing agents can make changes as long as these changes are kept in a separate copy that’s needed along with other copies. If these changes were to be made global, you would be in the realm of producer-consumer semantics.

Convenient Interfaces and APIs

There are many ToXxx extension methods that convert from mutable collections or collections-related interfaces to immutable collections. These methods copy the mutable collection rather than reuse it to maintain immutability. Many immutable collections offer convenient methods, such as those for sorting and searching, similar to those offered by the mutable ones. This helps mixing code that uses both kinds of collections.

To make immutable collections more usable in existing code bases, some of them implement suitable common interfaces such as IEnumerable<T>, IList<T> and ICollection<T>. Some of the methods declared such as IList<T>.Insert are intended to mutate the collection. These are implemented by throwing a NotSupported­Exception. Immutable collections also implement the corresponding immutable interfaces that are defined in the NuGet package.

The System.Collections.Immutable.ImmutableInterlocked type offers a number of methods that implement interlocked exchange mechanisms to correctly update items in or references to immutable collections. For example, the following method takes a reference to an item and updates it according to the specified transformer:

public static bool Update<T>(ref T location, Func<T, T> transformer) where T : class;

While the effects of such operations are observable by all threads, it guarantees that the same item will always be observed by all of them.

Wrapping Up

This article discussed the benefits of immutable collections and provided a detailed discussion of the design and implementation of immutable stacks, lists, arrays and dictionaries. There are numerous other immutable collections shipped with the NuGet package. Almost every mutable collection has a corresponding immutable one, which you can find there. I hope that you can effectively use these types in your code. If you like the immutability pattern and would like to write your own immutable types, Andrew Arnott has written a Roslyn-based tool that makes writing immutable types as easy as writing mutable types. You can find more about it at bit.ly/2ko2s5O.


Hadi Brais is a doctorate scholar at the Indian Institute of Technology Delhi, researching compiler optimizations for the next-generation memory systems. He spends most of his time writing code in C/C++/C# and digging deep into runtimes, compiler frameworks and computer architectures. He blogs on hadibrais.wordpress.com and can be contacted at hadi.b@live.com.


Thanks to the following technical experts for reviewing this article: Andrew Arnott and Immo Landwerth



Discuss this article in the MSDN Magazine forum