# Exercise 05 — The aggregator that got slower when we added workers **Failure mode:** lock convoy — contention on one hot critical section **Language:** C, pthreads · **Runtime:** about 25 seconds · **Difficulty:** the one with a number attached --- ## The prompt > A metrics aggregator digests events. Each event is scored and folded into a running > total behind one mutex. The team's response to "the aggregator is too slow" was to raise > the worker count from 4 to 16. **It got slower.** > > Measure it properly, explain the shape of the curve, and fix it. Your fix must produce > the identical total — I will check. Answer before you run anything: **if you double the threads and halve the work per thread, what should happen to wall time?** --- ## What you are given | Path | What it is | | --- | --- | | `broken/aggregate.c` | The starting point. One mutex, taken once per event. | | `fixed/aggregate.c` | One correct repair. | | `solution.patch` | The diff between the two, applies with `patch -p1`. | | `check.sh` | Proves the broken curve and the fixed one. | Both programs do a **fixed total amount of work** — one million scored events, whatever the thread count — split across 1, 2, 4, 8 and 16 threads. Perfect scaling would keep wall time **flat**, because the work per thread falls by exactly as much as the thread count rises. Each cell is the **median of five runs**; a single timing on a loaded machine is noise. --- ## Reproduce the measurement ```bash cd exercises/05-lock-convoy clang -O2 -g -Wall -Wextra broken/aggregate.c -o /tmp/aggregate_broken clang -O2 -g -Wall -Wextra fixed/aggregate.c -o /tmp/aggregate_fixed /tmp/aggregate_broken /tmp/aggregate_fixed ``` Expected (Apple M4 Pro, 10P + 4E cores, macOS 26.3): ``` EX05 build=broken totalOps=1000000 threads 1 2 4 8 16 (milliseconds) wall ms 77 113 294 191 179 vs 1 thread 1.00x 1.47x 3.80x 2.47x 2.32x EX05 build=broken ... checksum=127435700 acquisitions=1000000 slowdown=2.32 worstSlowdown=3.80 worstAtThreads=4 EX05 build=fixed totalOps=1000000 threads 1 2 4 8 16 (milliseconds) wall ms 75 42 21 11 11 vs 1 thread 1.00x 0.55x 0.28x 0.14x 0.14x EX05 build=fixed ... checksum=127435700 acquisitions=15626 slowdown=0.14 worstSlowdown=1.00 ``` **Timeout and safety.** No blocking primitives beyond the mutex itself, a fixed op count, and a 600-second watchdog. Nothing here can wait indefinitely. Both builds exit 0. --- ## The evidence to collect Three numbers, and the relationship between them is the answer: 1. **`acquisitions`** — one million in the broken build. One lock acquisition per event. 2. **The curve** — the worst point is not at 16 threads, it is at **4**. Read that again: the program is worst at roughly the core count of a performance cluster, then partially *recovers* as threads are added. That non-monotonic shape is the signature of a convoy plus adaptive lock behaviour, and it is the reason "we added threads and it got a bit better again" can coexist with "it is 4× slower than one thread". 3. **`checksum`** — identical in both builds. A speed-up that changes the answer is not a speed-up. If you have Instruments available, the System Trace **Thread State** view shows the same story as a picture: threads spending most of their time in a blocked state with short runnable bursts, handing the lock to each other. That is what "convoy" names — the threads queue up and move at the speed of the queue, not the speed of the work. --- ## Success criteria - [ ] The broken build still degrades — you have not edited it. - [ ] Your fixed build's 16-thread time is **lower** than its 1-thread time (ratio ≤ 0.60, generously bounded so a 4-core machine still passes). - [ ] Your fixed build's `checksum` equals the broken build's `checksum`, exactly. - [ ] `acquisitions` falls by at least 32×. - [ ] Both bounds hold on two consecutive runs. - [ ] You can name which of your three changes did the most, and how you would tell. Run `./check.sh` to have all of that checked for you. --- ## Hints
Hint 1 — look at what is inside the lock Read `worker()` and ask, for each line inside the critical section: **does this line touch shared state?** `score_event()` reads nothing shared and writes nothing shared. It is inside the lock only because somebody put it there.
Hint 2 — count the acquisitions, not just the hold time Even with a one-instruction critical section, taking a contended lock a million times costs a million uncontended-to-contended transitions. Addition is associative: you do not have to publish every partial result the moment you compute it.
Hint 3 — divide the shared surface, and mind the cache line One hot total can become N independent totals summed at the end. If you do that, pad each one to its own cache line — otherwise the shards share a line, every update invalidates every other shard, and you will measure false sharing and conclude sharding does not help. Ask yourself what property of this workload makes sharding legitimate. It is not true of every workload.
--- ## Solution
Reveal the solution ### The repair — three changes, one goal ```c /* 1. score OUTSIDE the lock 2. accumulate locally 3. fold into a padded shard */ static void *worker(void *arg) { work_t *w = (work_t *)arg; unsigned long local = 0; for (unsigned long i = 0; i < w->count; i++) { unsigned long s = score_event(w->first + i); /* OUTSIDE the lock */ local += s & 0xFFUL; if ((i % BATCH) == BATCH - 1) fold(w->id, &local); } fold(w->id, &local); } typedef struct { pthread_mutex_t m; unsigned long total, acquisitions; char pad[128 - sizeof(pthread_mutex_t) - 2 * sizeof(unsigned long)]; } shard_t; static shard_t shards[SHARDS]; ``` Measured effect: 16-thread wall time **179 ms → 11 ms**, acquisitions **1,000,000 → 15,626**, checksum unchanged. ### Which change did the most, and how you would tell The right answer is "I would measure them separately", and you can: - Move the scoring out of the lock **only**. The critical section becomes one addition, so the convoy narrows but the acquisition count stays at a million. You get a large improvement and a curve that is still not flat. - Add batching **only**. The acquisition count drops by 64×, which is the biggest single lever here, because the cost being paid a million times is the *transition*, not the hold. - Add sharding **only**. Contention is divided by the shard count, not removed. An interviewer who asks "which one mattered?" is usually checking whether you would guess or measure. Say you would measure, and say what you would measure. ### Why sharding is legitimate *here* Each worker owns a shard, and the only invariant is a **sum**, which is associative and commutative. That is why partial results can sit in different shards and be combined at the end. Sharding buys you nothing when the invariant spans shards. If the rule were "the total must never exceed a cap", you would have to hold every shard's lock to check it, and you would be back where you started with more code. Say this out loud; it is the difference between knowing a technique and knowing when it applies. ### The cache-line padding Without `pad[]`, several shards share one 128-byte line. Every fold into shard 3 invalidates the line holding shards 0–7 in every other core's cache. You would measure false sharing, see little improvement, and conclude — wrongly — that sharding does not work. The padding is not a micro-optimisation; it is what makes the measurement mean what you think it means. ### The lock was not the problem Note what the repair did **not** do: it did not swap `pthread_mutex` for `os_unfair_lock`, and it did not go lock-free. Reaching for a cheaper lock is the reflex answer and it is usually the wrong first move, because it addresses the cost per acquisition rather than the number of acquisitions or the width of the critical section. Fix the shape first; change the primitive only if the measurement still says to. ### What the interviewer is listening for - That you fixed a **fixed amount of total work** and compared wall time, rather than measuring throughput at different workloads. - That you used a **median**, and said why. - That you checked the answer did not change. - That you noticed the worst point was at 4 threads, not 16, and were curious about it rather than ignoring it. - That "add more threads" is now something you would want evidence for.
--- ## Limitations - **Timings are ratios, not thresholds.** Every absolute figure here is one machine under one load. The bundled check asserts loose ratios (broken worst ≥ 1.8×, fixed ≤ 0.60×) precisely so the exercise still validates on hardware that behaves quite differently. - The non-monotonic curve — worst at 4 threads, better at 8 and 16 — is **reproducible on this machine** but is a property of this scheduler, this core layout (10 performance + 4 efficiency) and this lock implementation. Do not generalise the shape; do reproduce it. - `score_event()` is a synthetic workload chosen to have a predictable cost. Real critical sections often contain allocation, logging or I/O, each of which has its own locks and can make the convoy dramatically worse than this. - Sharding by **worker id** is the easy case. Sharding by **key** — the usual real requirement — reintroduces the question of what happens when two workers hit the same key, and of whether any invariant spans keys.