Lock-Based vs. Lock-Free Concurrency: Trade-offs

1. The Problems with Locks

Lock-based programming is the standard, default way to handle concurrency. You identify a shared resource, place a mutex next to it, and ensure every access is guarded by a lock. While conceptually simple, this approach has well-known drawbacks, especially in large, complex systems.

To understand the motivation for even considering lock-free alternatives, let's start with a talk by Herb Sutter, a leading expert in C++.

As Sutter explains, locks are a form of blocking synchronization. If Thread A holds a lock, and Thread B needs it, Thread B must block (stop making progress) until Thread A releases the lock. This can lead to several problems:

• Deadlock: The classic issue where two or more threads are waiting for each other to release locks.
• Priority Inversion: A high-priority thread gets stuck waiting for a low-priority thread that holds a lock, because the OS scheduled an unrelated medium-priority thread instead of the lock-holding thread.
• Convoying: If a thread holding a lock is descheduled by the OS (e.g., its time slice ends, or it takes a page fault), all other threads waiting for that lock form a "convoy" and grind to a halt. The system's overall throughput suffers.
• Overhead: In uncontended cases, locks are fast. But when contention occurs and blocking is necessary, a lock might involve expensive system calls and context switches to put a thread to sleep and wake it up later.

Lock-free programming aims to solve these issues by ensuring that at any point in time, at least one thread in the system is making progress. This is what we call a non-blocking guarantee.

2. The Case Against Lock-Free: Juggling Razor Blades

Given the problems with locks, it's tempting to think lock-free programming is the superior solution. This is a dangerous misconception. Lock-free code is significantly more complex to write correctly and does not automatically guarantee better performance.

Let's start by immediately debunking the "lock-free is always faster" myth with a powerful counterexample.

As you just saw, the lock-based version scaled almost linearly, while the "superior" wait-free version showed no speedup at all and was significantly slower. Why?

Trade-off 1: Algorithm vs. Primitive

The core takeaway from that example is that the algorithm's design dominates the choice of primitive.

• Lock-Free (Bad Algorithm): Every thread hammered on a single atomic variable (atomic_sum += ...). This creates high contention at the hardware level. Even without a software lock, the CPU cores are fighting for exclusive access to the same cache line. This is called true sharing.
• Lock-Based (Good Algorithm): Each thread summed its portion into a local, non-shared variable. Only at the very end did it take a lock to add its local sum to the global total. The lock was held for a tiny fraction of the total time.

The real performance win came from avoiding contention, not from avoiding locks. This principle is universal.

Trade-off 2: New Kinds of Bugs (The ABA Problem)

Lock-free algorithms, which are typically built around a Compare-And-Swap (CAS) loop, introduce subtle correctness bugs that don't exist in lock-based code. The most famous is the ABA problem.

Imagine a lock-free stack implemented with an atomic pointer top. A thread wants to pop an element:

1. Thread 1 reads top, which points to node A. It calculates that the new top should be A->next, which is node B.
2. Before Thread 1 can execute its CAS, the OS deschedules it.
3. Thread 2 runs. It pops A, then pops B. Then, it allocates new memory for a different value, and the memory allocator happens to give it the same address that A used to have. Thread 2 pushes this new node (let's call it A') onto the stack. The stack is now A' -> C.
4. Thread 1 is rescheduled. It proceeds with its original plan: compare_exchange(top, A, B). It reads top, sees A' which has the same address as A, so the comparison succeeds! It incorrectly sets top to B.
5. The stack is now corrupted. The top pointer points to B, which has already been popped and possibly deleted. The node A' has been lost.

This problem is solvable (e.g., by tagging the pointer with a version counter), but it demonstrates the immense complexity and subtlety required. You are no longer just protecting a block of code; you are reasoning about the state of the entire system between individual CPU instructions.

Trade-off 3: Hardware Performance Pitfalls (False Sharing)

Even when your lock-free algorithm is logically correct, you can face performance issues rooted in the hardware architecture. The most common is false sharing.

CPU caches don't operate on single bytes; they manage memory in chunks called cache lines (typically 64 bytes on x86).

• Imagine you have two atomic integers, X and Y, that happen to be located next to each other in memory and fall on the same cache line.
• Thread 1 on Core 1 exclusively modifies X.
• Thread 2 on Core 2 exclusively modifies Y.

Logically, these threads should not interfere. But because X and Y share a cache line, the hardware's cache coherency protocol will cause the line to be bounced back and forth between Core 1 and Core 2. Each time a thread needs to write, it must invalidate the other core's copy and wait to gain exclusive ownership of the line. The threads are contending at the hardware level, even though they aren't sharing data at the software level.

3. A Structured View: The Concurrency Cost Hierarchy

To make sense of these performance trade-offs, it's helpful to have a quantitative framework. The blog post "A Concurrency Cost Hierarchy" by Travis Downs provides an excellent one. It categorizes concurrent operations into levels, where each level is roughly an order of magnitude more expensive than the last.

Let's use this hierarchy to compare our options.

From that reading, you should see two key points:

1. Under high contention, std::mutex performs surprisingly well, even beating a CAS-based atomic approach in some cases. It's not orders of magnitude worse than a contended atomic operation.
2. The huge costs of locking come from Levels 3 and 4, when blocking leads to system calls and, even worse, context switches. A lock-free approach is immune to these specific costs because it is non-blocking.

Now for the punchline. Where do the biggest performance wins come from?

The lesson is clear: the jump from Level 2 (contended) to Level 1 (uncontended) is where the real magic happens. This was achieved not by switching from locks to atomics, but by changing the algorithm to eliminate contention (using multiple counters or thread-local storage). This powerfully reinforces the point from Fedor Pikus's talk.

Summary of Trade-offs

Let's summarize the comparison in a table.

Conclusion

You came into this course wanting to understand how things work "under the hood," and the trade-offs between lock-based and lock-free concurrency are a perfect example of why that matters. A surface-level understanding might lead you to believe "lock-free is faster," but a deep, principled analysis reveals a much more nuanced reality.

Key Takeaways:

• Lock-based concurrency is blocking and can suffer from deadlock, priority inversion, and convoying.
• Lock-free concurrency is non-blocking but introduces extreme complexity and new classes of bugs like the ABA problem.
• Performance is not guaranteed. A naive lock-free algorithm with high contention is often slower than a well-designed lock-based algorithm that minimizes contention.
• The greatest performance gains come from algorithmic changes that reduce or eliminate contention, not from simply swapping a mutex for an atomic.
• Lock-free programming is an expert-level optimization, like "juggling razor blades." For most problems, a well-structured lock-based approach is the correct, safer, and often equally performant choice.

In the next module, we will begin our journey into C++ Design Patterns. We'll start with the foundational creational patterns, beginning with the Singleton. You'll see how to implement it in a thread-safe way, applying the principles of concurrency we've been discussing to a higher-level architectural problem.