Thread-safety patterns

1. The "Lock-free" / Wait-free pattern

You already know that Concurrent collections are thread-safe. But how do they do it without you wrapping your code in lock blocks? The answer lies in advanced algorithms — lock-free and wait-free.

Brief explanation of lock-free and wait-free algorithm concepts

Lock-Free

Essence: Guarantees that at least one thread can always make progress, even if others face delays or interruptions.

Difference from a lock: With a lock, competing threads wait until the lock is released. In lock-free algorithms threads don't wait for each other in the classic sense: on conflict they just retry.

Example: A checkout line: with a lock you stand and wait. In lock-free you approach, see it's busy, and try again shortly — no standing in a shared queue.

Wait-Free

Essence: A stronger guarantee: every thread will make progress in a finite number of its own steps, regardless of others. No one gets stuck spinning forever.

Difference: In lock-free a thread may indefinitely restart an operation due to conflicts; in wait-free that doesn't happen.

Practice: Implementing wait-free is significantly harder, so you usually see lock-free or hybrid approaches.

2. How Concurrent collections achieve thread-safety

The main building block of lock-free algorithms is atomic processor-level operations. In .NET we use them via the System.Threading.Interlocked class.

Interlocked operations

Fast atomic operations on primitives (int, long): e.g. Interlocked.Increment, Interlocked.Decrement, Interlocked.CompareExchange.

Examples: Interlocked.Increment(ref value) — atomic increment; Interlocked.CompareExchange(ref location, value, comparand) — atomically compares and, if equal, updates.

CAS (Compare-And-Swap) — Compare-and-Exchange

CAS is implemented in .NET as Interlocked.CompareExchange. General logic:

1. Read the current value of the variable.
2. Compute the new value based on the read value.
3. Try to write it only if the variable is still equal to the original value. If not — retry.

Example: a simple lock-free counter with Interlocked

using System.Threading;
using System.Threading.Tasks;

class CounterExample
{
    static int regularCounter = 0;
    static int interlockedCounter = 0;

    static void IncrementRegular(int iterations)
    {
        for (int i = 0; i < iterations; i++)
        {
            regularCounter++; // Not thread-safe!
        }
    }

    static void IncrementInterlocked(int iterations)
    {
        for (int i = 0; i < iterations; i++)
        {
            Interlocked.Increment(ref interlockedCounter); // Atomic!
        }
    }
}

//In Main:
Task t1 = Task.Run(() => IncrementRegular(500_000));
Task t2 = Task.Run(() => IncrementRegular(500_000));
Task.WaitAll(t1, t2);
Console.WriteLine($"Regular counter: {regularCounter}"); // will almost always be less than 1_000_000

regularCounter = 0; // Reset for the next test
t1 = Task.Run(() => IncrementInterlocked(500_000));
t2 = Task.Run(() => IncrementInterlocked(500_000));
Task.WaitAll(t1, t2);
Console.WriteLine($"Interlocked counter: {interlockedCounter}"); // Will be exactly 1_000_000

The Interlocked.Increment method guarantees atomicity of the increment: data won't be lost even with many competing threads.

3. Why this matters for scalability and performance

Reduces overhead: classic locks (lock) can cause context switches and kernel-level waits. Lock-free minimizes these costs.

No deadlocks: threads don't wait on each other — there's nothing to form a deadlock.

Better scalability: on multicore systems threads interfere less with each other, there's no single-lock bottleneck.

Higher responsiveness: nobody hangs waiting for long periods.

A very short look at the internals of ConcurrentQueue<T>

Simplified: the queue consists of linked segments. On Enqueue a thread atomically advances the "tail" via CompareExchange; on TryDequeue it atomically advances the "head" only if it hasn't changed. Real implementations are more complex (they handle the ABA problem and GC), but the key is atomic operations instead of heavy locks.

4. Performance of Concurrent collections

Performance comparison with a lock on regular collections

With low contention the difference is small, and sometimes a simple lock on a regular collection can be comparable. But under high contention Concurrent collections are typically significantly faster because there's no waiting on a shared lock.

Example: comparison (idea, not run)

using System.Collections.Generic;
using System.Collections.Concurrent;
using System.Diagnostics; // For Stopwatch
using System.Threading.Tasks;

class PerformanceTest
{
    static List<int> regularList = new List<int>();
    static ConcurrentQueue<int> concurrentQueue = new ConcurrentQueue<int>();
    static object lockObject = new object();

    const int Iterations = 1_000_000;
    const int NumTasks = 4; // Number of parallel tasks

    public static void RunTests()
    {
        Console.WriteLine("Performance test (adding):");

        // Test with regular List and lock
        regularList.Clear();
        Stopwatch sw = Stopwatch.StartNew();
        Parallel.For(0, NumTasks, (i) =>
        {
            for (int j = 0; j < Iterations / NumTasks; j++)
            {
                lock (lockObject)
                {
                    regularList.Add(j);
                }
            }
        });
        sw.Stop();
        Console.WriteLine($"List with lock: {sw.ElapsedMilliseconds} ms. Count: {regularList.Count}");

        // Test with ConcurrentQueue
        concurrentQueue.Clear();
        sw = Stopwatch.StartNew();
        Parallel.For(0, NumTasks, (i) =>
        {
            for (int j = 0; j < Iterations / NumTasks; j++)
            {
                concurrentQueue.Enqueue(j);
            }
        });
        sw.Stop();
        Console.WriteLine($"ConcurrentQueue: {sw.ElapsedMilliseconds} ms. Count: {concurrentQueue.Count}");
        // Expect ConcurrentQueue to be noticeably faster when NumTasks > 1
    }
}

Conclusion: If you see a lock around collections, it's often a sign to switch to Concurrent equivalents.

6. Useful nuances

The impact of contention on performance

Contention — when many threads access the same resource at once. The higher the contention, the more waits and worse performance.

Concurrent collections are designed to reduce contention: for example, ConcurrentBag<T> uses thread-local storage, and ConcurrentDictionary<TKey, TValue> uses striped locking (segmented locks).

The key to performance is reducing contention: if possible partition data across threads or use multiple collections.

Choosing the right collection for a specific scenario

ConcurrentQueue<T>

ConcurrentStack<T>

ConcurrentBag<T>

ConcurrentDictionary<TKey, TValue>

7. Optimization tips

Avoid frequent ToArray() in hot paths

ToArray() creates a new copy of the entire collection — expensive in time and memory. Use it only when you need a "snapshot", and as rarely as possible. For counts use Count (remember it's a snapshot at the moment of the call).

Be careful when iterating over Concurrent collections

Enumerators don't guarantee stability under concurrent modifications: you may skip items or get an inconsistent view. For a stable view make a snapshot first with ToArray().

// Bad: may skip items or see changes during iteration
foreach (var item in myConcurrentQueue) { /* ... */ }

// Good: iterate over a fixed snapshot
var snapshot = myConcurrentQueue.ToArray();
foreach (var item in snapshot) { /* ... */ }

Minimize "traffic" through the collection

Batch tasks/data: fewer Add/Take calls — less potential contention. For example, instead of 1000 separate messages — one "batch" of 1000.

Track sources of contention

If you see degradation, measure where the highest contention is. Maybe you can redesign so threads work with local data or different collections.

2

Task

C# SELF, level 58, lesson 4

Locked

Thread-safe counter using Interlocked

Thread-safe counter using Interlocked

Open

1

Survey/quiz

Concurrent Collections, level 58, lesson 4

Unavailable

Concurrent Collections

Thread-safe collections

Open