Lock-Based vs. Lock-Free Counters

The Ubiquitous Counter: A Concurrency Benchmark

The problem of safely incrementing a shared counter is a classic in concurrent programming. It's simple enough to analyze thoroughly, yet it encapsulates the core performance challenges of shared-memory systems.

As you know, a naive counter++ operation is not atomic. It's a three-step read-modify-write sequence (load the value, increment it, store it back), creating a race condition. The standard solution is to protect the operation with a mutex.

// Lock-based approach
pthread_mutex_t lock;
long counter = 0;

// in thread function...
pthread_mutex_lock(&lock);
counter++;
pthread_mutex_unlock(&lock);

This is correct, but is it fast? A mutex involves system calls and scheduler interactions to handle contention, which carries significant overhead.

An Alternative: C11 Atomic Operations

The C11 standard introduced a more direct way to handle this: atomic types. By declaring a variable with the _Atomic keyword, you instruct the compiler to use special, hardware-supported atomic instructions for operations on that variable.

For a simple increment, this can be a drop-in replacement for the mutex.

The video, and the resource below, suggest that for this simple case, the atomic version is significantly faster than the mutex version. The _Atomic variable allows the increment to be performed with a single, uninterruptible hardware instruction (like lock xadd on x86), avoiding the overhead of the mutex locking functions.

At this point, it seems simple: lock-free atomics are faster. But this is where the story truly begins.

When "Lock-Free" is Slower: The Dominance of Algorithm and Contention

The initial benchmarks are deceptive because they test a specific, and often flawed, algorithm: all threads hammering on a single memory location. Let's challenge the idea that lock-free is always faster.

The key insight is that performance is not just about avoiding locks; it's about avoiding contention. When multiple CPU cores try to write to the same memory location (or more precisely, the same cache line), the hardware's cache coherency protocol creates a massive bottleneck. The cache line containing the counter has to be shuttled back and forth between the cores, a process far more expensive than the atomic instruction itself. This is often called true sharing or cache line bouncing.

The "fast" lock-based algorithm in the video succeeded because it minimized contention. Each thread worked on a local variable (no contention) and only acquired the lock once at the very end to update the global sum.

A Concurrency Cost Hierarchy

To build a robust mental model for performance, it's helpful to think in terms of a cost hierarchy. Travis Downs' article "A Concurrency Cost Hierarchy" provides an excellent framework, using the shared counter as its central example.

He categorizes concurrent operations into levels, where each level is roughly an order of magnitude more expensive than the last. The key to optimization is to try to move your operation to a lower-numbered (faster) level.

As the article shows, both lock-based and naive lock-free counters fall into Level 2: True Sharing, because they both create high contention on a single resource. The goal of high-performance concurrency is to design algorithms that operate at Level 1 or Level 0.

• Level 1: Uncontended Atomics: Use atomic instructions, but on different memory locations to avoid contention.
• Level 0: Vanilla: Use no atomic instructions on the hot path at all.

Advanced Strategy: Escaping Contention

How can we implement a counter that operates at these faster levels? The key is to give each thread its own counter, eliminating the "true sharing" bottleneck.

This multi-counter approach is a powerful pattern. By distributing writes across multiple memory locations, you avoid the cache-line-bouncing penalty, and performance scales beautifully with the number of cores. The cost is a more complex and memory-intensive data structure, and a slower read() operation that must sum up all the sub-counters.

Putting It to the Test: Your Benchmark

Now it's time to see these effects for yourself. You will write a benchmark to compare three different counter implementations.

Here is the skeleton C code. Your task is to implement the three different increment strategies.

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <time.h>
#include <stdatomic.h>

#define NUM_THREADS_MAX 16
#define NUM_INCREMENTS 10000000

// --- Implementations ---

// 1. Mutex-based
pthread_mutex_t mutex_counter_lock = PTHREAD_MUTEX_INITIALIZER;
long long mutex_counter = 0;

void increment_mutex() {
    // TODO 1: Implement a standard mutex-based increment
    pthread_mutex_lock(&mutex_counter_lock);
    mutex_counter++;
    pthread_mutex_unlock(&mutex_counter_lock);
}

// 2. Naive atomic
_Atomic long long atomic_counter = 0;

void increment_atomic_naive() {
    // TODO 2: Implement a naive atomic increment on the single global variable
    // This will cause high contention.
    atomic_fetch_add(&atomic_counter, 1);
}

// 3. Local accumulation (low contention)
_Atomic long long local_atomic_counter = 0;

void increment_atomic_local(long long* local_sum) {
    // This function is called inside the thread's main loop.
    // It should increment a thread-local sum, not the global atomic.
    (*local_sum)++;
}

// --- Thread Functions ---

typedef void (*increment_func_t)();

void* thread_func_contended(void* arg) {
    increment_func_t func = (increment_func_t)arg;
    for (int i = 0; i < NUM_INCREMENTS; ++i) {
        func();
    }
    return NULL;
}

void* thread_func_local_accum(void* arg) {
    (void)arg; // Unused
    long long local_sum = 0;
    for (int i = 0; i < NUM_INCREMENTS; ++i) {
        // TODO 3: Use the local increment function
        increment_atomic_local(&local_sum);
    }
    // TODO 4: Atomically add the final local sum to the global counter
    atomic_fetch_add(&local_atomic_counter, local_sum);
    return NULL;
}

// --- Benchmark Runner ---

void run_benchmark(const char* name, int num_threads, void* (*thread_func)(void*), void* thread_arg) {
    pthread_t threads[NUM_THREADS_MAX];
    
    // Reset counters
    mutex_counter = 0;
    atomic_counter = 0;
    local_atomic_counter = 0;

    struct timespec start, end;
    clock_gettime(CLOCK_MONOTONIC, &start);

    for (int i = 0; i < num_threads; ++i) {
        pthread_create(&threads[i], NULL, thread_func, thread_arg);
    }

    for (int i = 0; i < num_threads; ++i) {
        pthread_join(threads[i], NULL);
    }

    clock_gettime(CLOCK_MONOTONIC, &end);
    double time_taken = (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1e9;

    printf("%-20s | %d Threads | Time: %.4f s\n", name, num_threads, time_taken);
}

int main() {
    for (int i = 1; i <= NUM_THREADS_MAX; i *= 2) {
        run_benchmark("Mutex", i, thread_func_contended, increment_mutex);
        run_benchmark("Atomic (Naive)", i, thread_func_contended, increment_atomic_naive);
        run_benchmark("Atomic (Local)", i, thread_func_local_accum, NULL);
        printf("--------------------------------------------------\n");
    }

    return 0;
}

Your Task:

1. Complete the four // TODO sections in the code.
2. Compile the program: gcc -Wall -Wextra -O2 -pthread your_file.c -o counter_bench
3. Run it: ./counter_bench
4. Analyze your results. How does the performance of each strategy change as the number of threads increases? Do your results match the concepts of contention and cache line bouncing?

Conclusion

You have now seen firsthand that "lock-free" does not automatically mean "faster." Performance in concurrent systems is a nuanced topic governed by hardware realities like cache coherency.

Key Takeaways:

• Contention is the Enemy: The primary goal of high-performance concurrent code is often to minimize or eliminate contention on shared resources.
• Algorithm over Primitive: A better algorithm (like local accumulation) with a "slower" primitive (a mutex) can vastly outperform a naive algorithm with a "faster" primitive (an atomic).
• Cost of Atomics: Atomic operations are not free. They are much cheaper than a contended mutex, but they are more expensive than a simple instruction and, more importantly, they serialize access to a cache line, which is extremely costly under high contention.
• Design for Your Access Pattern: The most performant solutions, like the multi-counter, are specifically designed to minimize contention by distributing data. Always analyze your data access patterns to choose or design the right structure.

Preview of the Next Lesson:
In this lesson, we saw an advanced pattern where each thread gets its own counter. The tls add implementation from the article used thread_local storage to achieve this. This is the ultimate optimization for a counter, achieving Level 0 performance. In our next module, "Advanced Threading Concepts and Patterns," we will formally learn how to use thread-local storage (TLS) via pthread_key_create to manage per-thread data, giving you the tools to implement these highly-optimized, contention-free patterns yourself.