What a lock costs when nobody else wants it, and what it costs when two or four cores do. Three ways to protect a counter increment: std::mutex glibc's futex-based mutex spinlock (TTAS) test-and-test-and-set with `pause`, no kernel atomic add no lock at all: the increment IS the atomic 10M critical sections split across 1, 2 or 4 threads on separate P-cores.
$ git clone https://github.com/adit4443ya/debug_labs.git && cd debug_labs
$ cd concurrency && ./build.sh
$ ./bin/04_mutex_spin
lock 1 thread 2 threads 4 threads (ns per critical section, 10000000 total)
std::mutex 25.2 79.1 100.6
spinlock(TTAS) 13.5 43.7 79.8
atomic add 11.8 24.3 27.9$ strace -f -c -e trace=futex ./bin/04_mutex_spin std::mutex
std::mutex 29.0 66.6 74.9
% time seconds usecs/call calls errors syscall
100.00 1.593456 12 127650 35711 futex
127,650 futex calls for 30M critical sections in total (the 1-thread run
makes none): about 0.6% of the contended acquisitions went to the
kernel. The rest were resolved by glibc's short adaptive spin before
sleeping. 35,711 "errors" are EAGAIN: the waiter found the lock already
released when it tried to sleep. (strace itself slows syscalls ~100x,
lab systems/02, so the timings under strace are not comparable.)- Uncontended std::mutex: 25 ns for lock+increment+unlock. That is two atomic RMWs (a CAS to lock, an exchange to unlock) on a line that stays in this core's L1, and NO syscall. "Mutexes are slow because they call the kernel" is false for the uncontended case. - Uncontended spinlock: 13.5 ns: one exchange (acquire) and one plain store (release). About half the mutex; the mutex's extra cost is its second RMW and the bookkeeping for waiters. - atomic add uncontended: 11.8 ns: a single lock xadd. - Contended, 2 threads: everything jumps 2-3x because the LINE holding the lock (or the counter) now bounces between cores (cache lab 04); 4 threads: 4-7x. The atomic add scales best because it holds the line for one instruction; the spinlock next; the mutex worst, because a waiter that spins for a while and then sleeps pays a futex syscall and a wake-up (microseconds) whenever it loses the spin. - Note the mutex's 4-thread number (100 ns) is only 25% worse than its 2-thread number: the queueing is dominated by the line transfer, and the adaptive spin keeps most acquisitions out of the kernel. The disaster case (thousands of ns) needs oversubscription: more runnable threads than cores, so a lock HOLDER gets preempted while holding.
std::mutex default. Correct under oversubscription (sleeping waiters free the core), ~25 ns uncontended, adaptive spinning built in. spinlock only when: critical sections are tens of ns, threads are pinned to dedicated cores (never preempted while holding), and you have measured the mutex's spin-then-sleep as a problem. Always with `pause` and a test-before-test-and-set. atomic when the critical section IS one RMW. Otherwise consider not sharing at all: per-thread state combined later, or an SPSC queue (lab 02) to hand work to one owner.
K1. Uncontended locks are ~10-30 ns and syscall-free. Contention costs come from the cache line, then from sleeping. Measure with 1, 2, 4 threads before believing any claim. K2. Count futex calls with `strace -f -c -e trace=futex` to see how often you actually sleep. If it is often, the critical section is too long or the lock is too hot: shard it. K3. Spinlocks require pinned, non-preempted threads; without that guarantee a preempted holder makes every waiter burn a core for a scheduler quantum.
1. Run the 4-thread mutex case with `taskset -c 2,3` (two SMT threads for four threads: oversubscribed): watch ns/section explode and futex calls climb. 2. Remove `_mm_pause()` from Spin::lock: the spinning thread hammers the line and slows the HOLDER down; measure the 2-thread case. 3. Make the critical section 1 us long (spin on rdtsc): now the mutex's sleeping waiters are the right choice and the spinlock burns cores. ============================================================
#include "../tools/bench.h"
#include <atomic>
#include <mutex>
#include <thread>
#include <vector>
#include <cstring>
#include <immintrin.h>
struct Spin { /* test-and-test-and-set with pause */
std::atomic<bool> locked{false};
void lock() { for (;;) { if (!locked.exchange(true, std::memory_order_acquire)) return; while (locked.load(std::memory_order_relaxed)) _mm_pause(); } }
void unlock() { locked.store(false, std::memory_order_release); }
};
static std::mutex mu; static Spin sp; static std::atomic<long> at{0}; static long counter = 0;
static const long ITERS = 10000000;
static void work_mutex(long n) { for (long i = 0; i < n; i++) { std::lock_guard<std::mutex> g(mu); counter++; } }
static void work_spin(long n) { for (long i = 0; i < n; i++) { sp.lock(); counter++; sp.unlock(); } }
static void work_atomic(long n){ for (long i = 0; i < n; i++) at.fetch_add(1, std::memory_order_relaxed); }
static double run(void (*fn)(long), int nthreads) {
const int cpus[4] = {2, 4, 6, 0};
counter = 0; at = 0;
uint64_t t0 = bench_ns();
std::vector<std::thread> th;
for (int t = 0; t < nthreads; t++) th.emplace_back([=] { bench_pin(cpus[t]); fn(ITERS / nthreads); });
for (auto &t : th) t.join();
return (double)(bench_ns() - t0) / (double)ITERS; /* ns per critical section, total */
}
int main(int argc, char **argv) {
const char *only = argc > 1 ? argv[1] : "all";
struct { const char *name; void (*fn)(long); } kinds[] = { {"std::mutex", work_mutex}, {"spinlock(TTAS)", work_spin}, {"atomic add", work_atomic} };
printf("%-16s %12s %12s %12s (ns per critical section, %ld total)\n", "lock", "1 thread", "2 threads", "4 threads", ITERS);
for (auto &k : kinds) {
if (strcmp(only, "all") && strcmp(only, k.name)) continue;
printf("%-16s %12.1f %12.1f %12.1f\n", k.name, run(k.fn, 1), run(k.fn, 2), run(k.fn, 4));
}
return 0;
}A lab is done when you can say what it showed on your machine — not when you have read it.
It decides which problems come first, which drills open, which labs you see and how the Learn surface is organised. Change it any time from the switch in the top bar, or press Escape to look around first.