Concurrent collections

A Dictionary guarded by a lock works, and it makes every reader wait for every writer. The collections in System.Collections.Concurrent do the same job with atomic operations per entry: no lock of the caller, no window in which two threads see a half-updated map.

ConcurrentDictionary

AddOrUpdate adds a key or transforms its value in one atomic step. A thousand parallel calls to the same key either lose updates or reach exactly a thousand, and there is no third outcome:

using System.Collections.Concurrent; var map = new ConcurrentDictionary<string, int>(); Parallel.For(0, 1000, _ => map.AddOrUpdate("hits", 1, (_, old) => old + 1)); Console.WriteLine($"hits {map["hits"]}"); Console.WriteLine($"misses {map.GetOrAdd("misses", 0)}"); Console.WriteLine($"keys {string.Join(",", map.Keys.Order())}");

dotnet run

hits 1000
misses 0
keys hits,misses

The thousand is exact every run, because the update lambda may run more than once but the write is atomic. GetOrAdd returned the existing value of misses, which was absent and therefore added as 0. The keys are not in insertion order and the program sorts them, as it sorts the files of a directory.

ConcurrentQueue

ConcurrentQueue<T> is the lock-free FIFO. Parallel enqueues are safe, and TryDequeue reports whether there was an element:

using System.Collections.Concurrent; var queue = new ConcurrentQueue<int>(); Parallel.For(1, 5, i => queue.Enqueue(i)); Console.WriteLine($"queued {queue.Count}"); Console.WriteLine($"dequeued {queue.TryDequeue(out var first)}"); Console.WriteLine($"first positive {first > 0}");

dotnet run

queued 4
dequeued True
first positive True

Four values were enqueued from parallel iterations and the count is four. The order of a concurrent queue is the order of the successful enqueues, which parallel iterations do not fix; the program prints only that the dequeued value is one of the four. A program that needs a known order enqueues from one thread, or attaches a sequence number to each item.

BlockingCollection

BlockingCollection<T> wraps another collection with a bound and blocks the producer when it is full. The consumer loops over GetConsumingEnumerable, which ends when the producer calls CompleteAdding:

using System.Collections.Concurrent; using var collection = new BlockingCollection<int>(2); var producer = Task.Run(() => { for (var i = 1; i <= 3; i++) { collection.Add(i); } collection.CompleteAdding(); }); var total = 0; foreach (var item in collection.GetConsumingEnumerable()) { total += item; } producer.Wait(); Console.WriteLine($"total {total}"); Console.WriteLine($"completed {collection.IsCompleted}");

dotnet run

total 6
completed True

The bound of two is why the producer blocks on the third add until the consumer has taken one; that back pressure is the point of the type. The consuming loop ended because CompleteAdding closed the collection, and IsCompleted is true after the last item was taken. The blocking API is for a thread that can wait; the next lesson does the same with channels, which a task can await.

Which collection to use

Exercises

  1. Count a thousand increments of a plain Dictionary without a lock and compare.
  2. Add a second key to the parallel loop and print both totals.
  3. Give the blocking collection a bound of one and watch the producer wait.
  4. Replace the blocking collection with a channel and compare the code.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. Why use ConcurrentDictionary instead of a Dictionary with a lock?

    Answer

    Its operations are atomic per entry without a lock of the caller

    A lock around a dictionary makes every reader wait for every writer.

  2. What does AddOrUpdate do?

    Answer

    Adds a key or transforms its value in one atomic step

    The thousand parallel calls reached exactly 1000 because of it.

  3. What does this program print? using System.Collections.Concurrent; var map = new ConcurrentDictionary<string, int>(); Parallel.For(0, 1000, _ => map.AddOrUpdate("hits", 1, (_, old) => old + 1)); Console.WriteLine(map["hits"]);

    Answer

    1000

    The atomic update cannot lose a call, so the result is exact.

  4. What does GetOrAdd return?

    Answer

    The existing value, or the one it added

    The measured call returned 0 for the key it had just added.

  5. What does this program print? using System.Collections.Concurrent; var q = new ConcurrentQueue<int>(); q.Enqueue(1); q.Enqueue(2); q.Enqueue(3); Console.WriteLine(q.Count);

    Answer

    3

    Three items were enqueued and none was taken.

  6. What does BlockingCollection.Add do when the collection is full?

    Answer

    Waits until the consumer takes an item

    The bound produces back pressure, which is the reason for the type.

  7. What does this program print? using System.Collections.Concurrent; using var c = new BlockingCollection<int>(2); var producer = Task.Run(() => { for (var i = 1; i <= 3; i++) c.Add(i); c.CompleteAdding(); }); var total = 0; foreach (var item in c.GetConsumingEnumerable()) total += item; producer.Wait(); Console.WriteLine(total);

    Answer

    6

    The consumer sums 1, 2 and 3.

  8. What does CompleteAdding allow?

    Answer

    The consuming loop to end after the last item

    The consuming enumerable ends when the collection is complete and empty.

  9. What does this program print? using System.Collections.Concurrent; var map = new ConcurrentDictionary<string, int>(); Console.WriteLine(map.TryAdd("a", 1));

    Answer

    True

    The key was absent, so TryAdd added it and returned true.

  10. Which of these collections is FIFO?

    Answer

    ConcurrentQueue

    A queue is first in, first out; a stack is the opposite.

The code on this page was built with the .NET SDK 10.0.303 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev