Multithreaded Work Synchronization in C#/.NET

Now, continuing the article about synchronization (Part 1) , I will be entering the area of “surely, somebody has already had that problem, and there is a ready-to-use solution”. Since the synchronization topic sounds like a common problem (which it is), there must be some ready-to-go solutions for some common scenarios that you will face, and the good news is, there are! But just like with anything else, those might not be fully optimal solutions for us.

Thread-safe collections

I will now discuss thread-safe alternatives to some of the common collections along with the guidelines for when to use them to achieve the best performance. When I refer to something as thread-safe, what I have in mind is that the target — which in our case is some collection — can safely be a subject of operations by multiple threads concurrently without a need for additional synchronization from the user code (for example wrapping in lock block) — for more detailed explanation refer to this Microsoft blog post.

The collection can achieve thread safety in a few ways that can roughly suit our needs, so let me name a few:

Lock-based — an obvious solution where the collection has an internal locking mechanism that, in most cases, will be fine-grained to achieve the best performance.
Lock-free — collections do not use locks per se but rather implement mechanisms that can be based on loops, and in the case of .NET calls to Interlocked class, which I will discuss later.
Wait-free — the firmest guarantee of synchronization algorithms, meaning that each thread will make progress (without waiting or spinning) regardless of the external factors and execute the operation within bounded number of steps. In .NET this also involves calls to Interlocked but only a subset of methods like Interlocked.Increment or Interlocked.Decrement which are not part of CAS (Compare-And-Swap).
Immutability — rather than ensuring consistency during modification of single collection instance you can allow only reads of the single instance by multiple threads while any writes will require creating new instance representing structure with requested changes.

Concurrent Collections

Collections that are provided within the System.Collections.Concurrent namespace use fine-grained locking encapsulated within implementation details, or lock-free mechanisms to achieve thread safety.

BlockingCollection and ConcurrentBag

I have come across the use of List<T> in a concurrent context a few times, probably because all a developer sees is a list.Add(element) and assumes that there is no place for race conditions. This, of course, is wrong because they only see a method associated with the class that was not designed for thread safety. Internally, while calling the .Add(element) list performs multiple operations like an array reference copy, size check, optional array resizing and element assignment to the last free index. Between each of those operations there can be interference from another thread that also attempted to add a new element to the list and possibly can override element placed by the first thread.

⚠️ Remember even as simple operation as number++ that translates to number = number + 1 is not thread-safe as it requires three operations (read, addition and write) and between each operation the value of the number can be modified by another thread (even without mentioning CPU cache).

So, what are the options if you want List<T> but you also care about thread safety? Firstly, if you need indexing on your collection (so that you are able to access elements like that list[2]), then you have to choose a simple path (that might even be the best path!) and use lock to wrap any code-block that uses your list in any way (so both reads and writes). That is because built-in .NET concurrent collections like BlockingCollection or ConcurrentBag support the Producer-Consumer pattern where the order does not matter, rather than supporting indexing. Not caring about the order makes those collections more optimized in some scenarios.

Both collections implement the IProducerConsumerCollection interface ensuring that TryAdd(T) and TryTake(out T) methods are available for our convenience. What is the difference as both collections look identical at first sight?

First, let’s take a closer look at the ConcurrentBag. It is a collection that is described in documentation as:

a thread-safe bag implementation, optimized for scenarios where the same thread will be both producing and consuming data stored in the bag.

Here you might get a little bit confused as to why the tread-safe collection is best performing in single-thread scenarios. There are many use cases and collections included within standard libraries trying to cover as much of them as possible. It is not unlikely that you might have some code path that will be handled with a single thread 99.9% of the time but in this 00.1% of cases you also need the thread safety to be in place not to corrupt our data. ConcurrentBag is a great choice because it generally outperforms locking or other concurrent collections. While in rare cases (0.01%) it may be slightly slower, this difference is negligible overall.

Now that you understand the reasoning behind the implementation, which favors single-thread use cases, you might wonder how it’s implemented. ConcurrentBag utilizes a technique called Work Stealing, which is also used in ThreadPool if you’re interested in exploring it further.

In general, the name is quite descriptive: there are multiple queues of work which in the case of ConcurrentBag are separate bags of items assigned to each thread. If a thread is both adding items to its own bag and removing them, minimal overhead is involved. However, if a thread finalizes all of the tasks from its personal bag, it will attempt to steal items from another thread’s bag. This stealing process requires acquiring a global lock on the queues and looping to handle potential race conditions during the operation.

BlockingCollection, which I feel is more suitable to be named a Producer-Consumer collection, offers additional methods and functionality that make it ideal for implementing something akin to a channel for transferring the data between threads.

As the name suggests (as it ideally should), BlockingCollection blocks the calling thread if you try to take an element when the collection is empty or add an element when it has reached its maximum capacity. In contrast, ConcurrentBag is specifically designed for efficient multi-threaded access without such blocking behaviour.

An interesting fact about BlockingCollection is that it doesn’t implement any collection internally. Instead, it acts as a wrapper around another data structure (by default, a ConcurrentQueue, which I’ll describe shortly), whose semantics dictate the behaviour when adding or taking elements.

Having measurable results is important, so I’ve created a few benchmarks using Benchmark.NET.

A general note: I’m using Queue with lock (rows with Locked Queue collection) as a baseline because producer-consumer collections align most closely with Queue semantics.

Starting with simple cases of adding elements:

And one for taking elements out of the collection:

In the case of addition, you’ll see that ConcurrentBag generally outperforms the locked queue, but it does not look so good for taking elements out. However, those are very simple benchmarks and don’t reflect real-world scenarios.

In the benchmark below, a fixed number of threads adds elements to the collection and other threads are consuming them (which is more suited to producer-consumer scenarios), ConcurrentBag consistently outperforms the simple locked queue. What’s particularly noteworthy is the case with 6 adding threads and 2 consuming threads, where the locked queue is, on average, 2x slower than ConcurrentBag.

ConcurrentDictionary

Another type of concurrent (thread-safe) collection is quite intuitive, as it’s essentially a familiar Dictionary<TKey, TValue> with added improvements to help us write a clean and efficient concurrent code.

What singles out the concurrent version of the dictionary is the inclusion of methods like AddOrUpdate and GetOrAdd, which are designed specifically for scenarios where multiple threads perform the same operation. Take AddOrUpdate, for example: if two (or more) threads try to add something to the dictionary, one must be the first to do so (yes, thanks, Mr. Obvious!). The others cannot simply overwrite data which could be the result of two threads attempting to add the same key to the dictionary, as that would lead to inconsistency and unexpected behavior in the application. This method does what you could have coded manually, very clumsily, as illustrated below:

while (true)
{
    if (dictionary.TryGet(key, out currentValue))
    {
        if (dictionary.TryUpdate(key, currentValue, updateValueFactory))
        {
            // Execution will enter here only if at the moment of update
            // the value under key was the same as currentValue
            break;
        }
    }
    else if (dictionary.TryAdd(key, addValueFactory))
    {
        break;
    }
}

This isn’t the exact implementation of AddOrUpdate, as you might expect (but I encourage you to check the real code as an exercise!). However, at this level, it illustrates the main concept: a lock-free mechanism where threads race to insert data into the dictionary as quickly as possible. Each of the Try* methods essentially checks if the value under the specified key has changed since the operation began, which indicates that another thread has made a modification. This concept is based on CAS (Compare-and-Swap).

One crucial point highlighted by this example, which is also mentioned in the official documentation, is that:

For modifications and write operations to the dictionary, ConcurrentDictionary<TKey,TValue> uses fine-grained locking to ensure thread safety (read operations on the dictionary are performed in a lock-free manner). The addValueFactory and updateValueFactory delegates may be executed multiple times to verify the value was added or updated as expected.

Additionally, it’s important to highlight that reads are lock-free, as no data is being modified. Since reading does not alter the structure, there is no need to lock it during read operations.

At this point, you might also wonder, “Why use ConcurrentDictionary when you could simply do…?”

lock (_lock)
{
    dictionary.Add(key, value);
}

That’s a great question because in some cases a simpler approach might be more efficient. ConcurrentDictionary uses fine-grained locking to minimize lock contention when many threads try to execute operations, but this comes with some overhead. Here are some small benchmarks that show how ConcurrentDictionary and a dictionary with locking perform, depending on the number of concurrent threads executing operations on them.

First, take a look at the benchmark comparing adding elements to a ConcurrentDictionary versus a locked Dictionary.

It might be alarming that a simply locked dictionary outperforms the concurrent version in this benchmark (keep in mind that the gap is more noticeable with a large number of elements; the difference would be less significant with fewer elements). However, reviewing the internal implementation of ConcurrentDictionary explains the overhead it incurs, which includes creating nodes to handle items, obtaining locks, and potentially resizing the lock table.

This also implies that the performed benchmark is not the best measurement of the concurrent dictionary performance because it only adds elements to the dictionary, which is not a very common use case and causes a lot of node creations and lock table resizing. In the scenario when both additions and updates are performed concurrently, the dictionary starts to shine as more threads are involved.

Benchmarking the process of obtaining elements from the dictionary might also bring a smile to your face.

As mentioned earlier, reads on ConcurrentDictionary are performed in a lock-free manner, which makes them highly performant. If you search a bit on the internet, you’ll find a comment from Stephen Toub that sums it up nicely:

It is optimized for lock-free reads, while trying to remain scalable for writes. Adds require both allocating and locking, so an extra cost is expected.

ConcurrentQueue and ConcurrentStack

Another pair of self-explanatory collections is ConcurrentQueue and ConcurrentStack. ConcurrentQueue has already been mentioned alongside BlockingCollection, as it can serve as the underlying store for it. The same applies to ConcurrentStack, since both of these collections implement the IProducerConsumerCollection<> interface.

ConcurrentStack has a relatively simpler internal implementation, as its core relies on a looped CAS (Compare-and-Swap) lock-free mechanism structured as a linked list. It works as follows:

private void PushCore(Node head, Node tail)
{
    SpinWait spin = default;

    // Keep trying to CAS the existing head with the new node until we succeed.
    do
    {
        spin.SpinOnce(sleep1Threshold: -1);
        tail._next = _head; // Re-read the head and link our new node.
    }
    while (Interlocked.CompareExchange(ref _head, head, tail._next) != tail._next);
}

I haven’t covered SpinWait or Interlocked yet, but you’ll get to those concepts soon. For now, just keep in mind that SpinWait allows us to wait briefly (similar to Thread.Sleep or Task.Wait, but for a much shorter period). Interlocked.CompareExchange is used to safely swap a value under a reference, ensuring that nothing interrupts the operation between the comparison and assignment.

Keeping all of that in mind, you can see that the code above simply races against other threads, all attempting to push values onto the stack. It will continue looping until it succeeds. This is key because it demonstrates optimistic concurrency — if there aren’t many threads pushing or popping, in most cases it will be completed in a single iteration while being quite fast. However, it’s worth remembering that there is a small chance (though unlikely) of encountering a livelock situation or a lack of fairness where one thread, despite being theoretically first, will constantly be outpaced by others.

Livelock is a situation where two (or more) threads constantly affect each other due to a changing state effectively making no progress.

As a performance tip, if you’re using ConcurrentStack in a producer-consumer scenario, you might consider using TryPopRange instead of TryPop to increase throughput. Essentially, instead of repeatedly engaging the stack’s lock-free mechanism to retrieve a single element, you can grab a larger chunk of items at once, which can be more efficient.

ConcurrentQueue is a bit more complex, as it is built from ConcurrentQueueSegment objects, which act as buckets for the enqueued items. To explain this, imagine a queue containing two segments: while one thread is writing new elements to the queue, those elements are appended to the tail segment. This happens without interference from the reading thread, which peeks elements from the head segment.

When you create a new ConcurrentQueue<> instance, it is initially allocated with a segment of size 32. Once the segment reaches its capacity limit new one is created, and each subsequent segment has a capacity of Math.Min(tail.Capacity * 2, MaxSegmentLength). This means each segment is twice as large as the previous one, but it won’t exceed the MaxSegmentLength, which is set to 1024 * 1024 elements (1 million).

As you might have already guessed from the example above, by using multiple segments, you can avoid concatenation between reads and writes. However, there are operations where an entire queue must be explicitly locked (a cross-segment lock), such as when:

The current tail segment capacity has been exceeded, and a new one must be created and assigned as the new tail.
The current head segment is empty (due to popping all the elements) head._next element is assigned as the current queue head.
queue.Count is called when there is more than one segment in order to get an accurate element count within the queue.
queue.GetEnumerator() is called (so while using queue within foreach statements) to create a queue state snapshot for enumeration.
queue.Clear() is called in order to remove all elements within the collection.

Operations like appending to the tail and removing from the head are unavoidable, the algorithm of exponentially growing segments is specifically designed to efficiently support both small and large queues, keeping performance optimal for most scenarios. However, in rare cases, you might consider adjusting this behaviour with a custom implementation tailored to your specific use case. That said, in most situations, the implementation provided should work just fine.

Due to the complexity of creating a straightforward benchmark, I haven’t included one here. However, given the properties discussed, I recommend experimenting on your own to assess whether ConcurrentQueue might perform better than a locked queue in your specific application. A useful approach would be to estimate the number of concurrent read and write threads, as this can help determine if the segmentintteag behaviour of ConcurrentQueue would provide a performance benefit.

Summary

I hope you’ve managed to read through the entire article and gained a deeper understanding of the collections available to help resolve concurrency issues!

There are also some official guidelines explaining when the use of a concurrent collection should be considered. Check them out!