Multithreaded Work Synchronization in C#/.NET

We have already discussed thread-safe adaptations of common collections (check out the Part 1 and the Part 2 of Pawel’s article), so it’s about time we tackled them with immutability in order to solve our concurrency problems using a new approach.

Immutable Collections

The final way to ensure a collection is thread-safe is by making it immutable. This means that whenever you modify the collection (e.g., add or remove elements), the result is a new, exclusive copy of the entire collection with the changes applied. As a result, the collection cannot be modified by other threads, because any other thread attempting to add or remove items would receive its own independent copy of the collection, separate from the original.

You might be thinking that while having a dedicated copy ensures thread safety, it also seems extremely memory-inefficient — and you’re right. However, this approach is implemented in a smart way to mitigate those concerns to some degree!

Immutable Dictionary

The best example to showcase the capabilities of immutable collections is the immutable equivalent of a dictionary. Following the main rule of immutability (where a modification results in a new instance), the code below illustrates what you can expect from an ImmutableDictionary.

var dictionary = new ImmutableDictionary<string, int>();
var updatedDictionary = dictionary.Add("key1", 101);

if (!dictionary.Contains("key1")) // original dictionary was not modified
{
    Console.WriteLine("Dictionary does not contain 'key1'");
}

if (updatedDictionary.Contains("key1")) // new instance contains added key
{
    Console.WriteLine("UpdatedDictionary contains 'key1'");
}

As you can see in the example above, after applying a modification, a new instance of the dictionary is created. But does this mean that all the elements have to be copied, thus increasing memory consumption? Not necessarily!

First, it’s important to understand the underlying data structure of our immutable dictionary: it’s a self-balancing AVL tree. The core principle of an AVL tree is that the depth difference between the left and right subtrees cannot be greater than one. As you may know, a tree consists of interconnected nodes, where each node has references to its potential left and right child nodes.

Now that you know we’re dealing with a tree, let’s consider the mutating operations — adding or removing elements. When modifying an ImmutableDictionary, the internal implementation uses a technique called structural sharing. This means that when adding or removing elements, it only creates new nodes along the path from the root to the modified node. This approach ensures that memory usage remains as efficient as possible, as it avoids duplicating the entire structure.

In the simple example above, when you add a new element, such as the number 6, it causes a new connection to be created from node 5. This implies that node 5 must be mutated, which in turn leads to the mutation of the root. However, nodes 1 and 4 remain unchanged due to structural sharing. If there were more elements on the left, those would be fully reused without duplication.

Let’s see how the addition performs using a benchmark.

Using ImmutableDictionary comes with a significant overhead, not only in terms of execution time but also memory consumption. Despite the optimizations, it still requires a considerable amount of copying to create a new mutated instance when adding elements.

However, there is a tool you can use to improve memory usage: the ImmutableDictionary.Builder class. It allows for more performant mutation operations and should be the preferred approach when you need to apply multiple modifications to an immutable dictionary.

public class Account
{
    private readonly ImmutableDictionary<string, Transaction> _transactions;

    public Account()
    {
        _transactions = ImmutableDictionary<string, Transaction>.Empty;
    }

    private Account(ImmutableDictionary<string, Transaction> transactions)
    {
        _transactions = transactions;
    }

    public Account AddTransactions(IEnumerable<Transaction> transactions)
    {
        var builder = _transactions.ToBuilder();

        foreach (var transaction in transactions)
        {
            builder.Add(transaction.Id, transaction);
        }

        return new Account(builder.ToImmutableDictionary());
    }
}

The principle behind the ImmutableDictionary.Builder is that, instead of creating a new instance for each change, the builder batches them together and applies all the modifications at once. It aims to be as efficient as possible, minimizing the changes required, such as those needed for the AVL tree balancing when operating on a plain ImmutableDictionary.

⚠️ ImmutableDictionary.Builder is not thread-safe so any operations that are performed on it must be executed by a single thread.

Ok, so how does it perform?

There is a significant improvement in both execution time and memory consumption when the builder is used. If you are wondering when it’s beneficial to use the builder, the answer depends on benchmarking, as the effectiveness will vary based on the key layout (how many rebalancing operations key addition will cause) and the number of operations you typically perform.

An improvement for replacing elements within an ImmutableDictionary can be made. Since the goal is only to change the value associated with a specified key, the resulting tree structure will not require additional balancing (as the size of the dictionary remains unchanged). Only the affected nodes along the single path to the key need to be copied.

Instead of combining Remove() and Add() operations on plain ImmutableDictionary we can use ImmutableDictionary.Builder or SetItem(). One additional advantage of the SetItem() method is that it is effectively an upsert operation.

So now, how do those perform?

While there may be no improvement in execution time, using the builder or SetItem() method instead of plain addition operations can reduce memory consumption, especially for a relatively large number of operations involving replacements.

The in-depth discussion of immutable collections shall be limited to the dictionary, as explaining other immutable structures would essentially involve describing different optimization approaches for modifying them.

The whole list of available immutable collections can be found in System.Collections.Immutable namespace listed here:

System.Collections.Immutable Namespace

Contains interfaces and classes that define immutable collections.

learn.microsoft.com

Summary

Regrettably, immutable collections might have a significant performance disadvantage, but in some cases, they can be a reasonable choice. They allow us to write code as if it were single-threaded, since we always have an exclusive copy (like a snapshot) to work with.

In the upcoming, and also the final part, I will explore more advanced synchronization primitives that can be useful for both macro- and micro-optimizations. See you there!