two threads to a task runtime
Two threads. Each one adds one to a shared counter, a million times. When they’re both done the counter should read exactly two million. Here’s what it actually read, six runs in a row:
1012274 1012084 1030689 1029327 1019485 1001727Never two million. Never even the same wrong number twice. Roughly half the increments, nearly a million of them, simply vanished, and a different set vanished each time. The code is as simple as it looks:
long counter = 0;
void* work(void* _){ for(int i=0;i<1000000;i++) counter++; return 0; }
// ... start two threads running work(), wait for both, print counterThere’s no bug in the sense of a typo; the program says what its author meant. And yet a million increments evaporated, nondeterministically, which is the single most disorienting experience in programming the first time it happens: correct-looking code that produces a different wrong answer every run. This post follows that lost million all the way down to the hardware and all the way back up to why serious concurrent systems refuse to let you write this loop at all. Everything here is real, run on a 10-core M4; you need to read a little C and to know a thread is a line of execution the OS can run on its own core.
counter++ is a lie
The whole disaster is hiding in the innocent ++. It reads like one indivisible action. In this unoptimized binary, however, the compiler lowered it to three instructions:
ldr x8, [x9] ; load counter from memory into a register
add x8, x8, #1 ; add one, in the register
str x8, [x9] ; store it back to memoryThree instructions: load, add, store. The counter lives in memory; this build copies it into a register, increments the register, and copies it back. Between those steps, the other thread can execute its own load-add-store on the same counter. Thread A loads counter and sees 5. Before A stores, thread B also loads counter and sees 5. A stores 6. B stores 6. Two source-level increments happened; the object changed once.
That interleaving explains one execution the hardware can produce. It does not define what the C program means. The C++ execution rules call two potentially concurrent conflicting accesses a data race when at least one is non-atomic and neither happens before the other. Any such race is undefined behavior. Once the race exists, the language no longer promises that the result can be reconstructed by interleaving source operations. The unoptimized assembly makes the lost update visible, but it must not become a model for every optimized execution.
I want to convince you the interleaving is really where the loss lives, not somewhere subtler, so I ran the naive version again on this machine at -O0, six fresh runs:
1018703 1013905 1028190 1034456 1031339 1022527Same shape, slightly different wrong numbers than the first six. Every one landed a little above one million. A load-load-store-store interleaving loses one of two increments and would land at one million if it happened on every iteration. Periods in which one thread advances alone preserve more updates. That is a plausible hardware explanation for this unoptimized binary, not a quantity the C language defines and not a reliable scheduler meter. The next build demonstrates why that distinction matters.
The optimizer makes it worse, by making it look fixed
Here is the part that genuinely rattled me, and it’s the reason “just test it” is not a defense for racy code. Everything above was compiled at -O0, no optimization, because that’s the version whose assembly matches the three-line story. So I turned the optimizer on, -O2, expecting the same race a little faster, and got this instead, eight runs:
2000000 2000000 2000000 2000000 2000000 2000000 2000000 2000000Exactly two million, every time. The race apparently cured itself the moment I asked for optimized code. It did not, and believing it did is how this bug ships. Look at what -O2 did to the loop body:
_work:
adrp x8, _counter@PAGE
ldr x9, [x8, _counter@PAGEOFF] ; load counter ONCE
add x9, x9, #244, lsl #12 ; = 999424
add x9, x9, #576 ; 999424 + 576 = 1000000
str x9, [x8, _counter@PAGEOFF] ; store ONCE
mov x0, #0
retThere is no loop. The compiler proved that a million counter++s with nothing else in the body is just counter += 1000000, folded the whole thing into a single add of one million (it even split the constant across two adds because a single immediate can’t hold 1000000), and emitted one load and one store for the entire function. That’s legal precisely because the language says a data race is undefined behavior: the compiler is allowed to assume no other thread is touching counter, so it optimizes as if this were single-threaded code, which single-threaded it is entitled to collapse.
So why does it print two million? Because now each thread’s entire contribution is a single load-add-store that takes a few nanoseconds, and pthread_create takes far longer than that to spin up the second thread. Thread A has already loaded zero, added a million, and stored a million before thread B has even started running. They almost never overlap, so almost no update is lost, and you get the right answer for entirely the wrong reason. The race didn’t go away. Its window shrank from a million iterations down to three instructions, small enough that the scheduler almost never splits it.
“Almost.” I wanted to see the collapsed race actually fire, so I forced the two threads to start together: both spin on a shared atomic flag, main waits until both are parked on it, then flips it and lets them go at the same instant. Same -O2, same collapsed single add, twenty runs:
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000
exact=0 lost-a-whole-thread=20 other=0Exactly one million, twenty times out of twenty, deterministically. When the window is a single load-add-store and both threads hit it simultaneously, they both load zero, both add a million, both store a million, and one entire thread’s work is gone. Not half the increments this time, all of them, from whichever thread stored second. The unoptimized version loses a random half because it’s a million tiny races; the optimized version, forced to overlap, loses a clean half because it’s one big race. Same undefined behavior, two completely different shapes, and the second shape only appears if you happen to make the threads start together. If you’d “tested” the -O2 build the normal way, you’d have seen two million and shipped it.
The natural next thought, and I’ve watched more than one beginner have it, is that the collapse is the disease and volatile is the cure: mark the counter volatile so the compiler is forbidden from folding the loop, and surely then it’s correct. So I tried it, volatile long counter, same -O2, six runs:
1022285 1024050 1003203 1018095 1003650 1004711Right back to losing half. volatile did stop the fold, the loop is really there in the assembly now, ldr / add / str once per iteration:
LBB0_1:
ldr x10, [x9, _counter@PAGEOFF]
add x10, x10, #1
str x10, [x9, _counter@PAGEOFF]
b.ne LBB0_1But volatile means “this memory can change behind your back, don’t cache it in a register across accesses,” which is a promise about the compiler not eliding loads and stores, not a promise about atomicity and not a word about ordering between cores. It forces the three-instruction load-add-store to actually happen a million times, which is exactly the racy thing the collapse had accidentally avoided. So volatile takes you from a program that prints the right answer for the wrong reason to a program that prints the wrong answer for the right reason, and it is worth burning this in early because the mistake is so common: volatile is not a concurrency tool, it never was, and reaching for it here fixes nothing while feeling like it should.
The indivisible add
The fix is to make the load-add-store indivisible, to tell the hardware “do all three as one uninterruptible operation, and don’t let any other core touch this address in the middle.” That’s an atomic operation, and modern CPUs have real instructions for it:
atomic_long counter;
// ... in the loop:
atomic_fetch_add(&counter, 1); // load-add-store, guaranteed indivisible2000000 2000000 2000000 <- always exactly two millionEvery run, exactly right. atomic_fetch_add compiles to a hardware instruction that performs the read-modify-write as a single atomic unit, no other core can slip a load or store into the middle, so no increment can be lost. This is the bedrock of all concurrency: a small set of operations the hardware promises are indivisible (atomic add, atomic exchange, compare-and-swap), from which everything else is built. The counter is fixed. But atomics buy correctness, and they’re not free, and the ways they cost you are the rest of this post.
Before I measure the cost, I wanted to see the actual instruction, because “atomic add” is a hardware promise and I don’t like trusting promises I can read. On this M4, atomic_fetch_add with relaxed ordering compiles to exactly one instruction:
ldadd x10, x11, [x9] ; atomic: load [x9] into x11, add x10, store backldadd is an ARMv8.1 LSE atomic (Large System Extensions). Architecturally it is one read-modify-write operation. Every modification of this atomic object occupies one position in that object’s modification order, so another update cannot be inserted between the read and write portions of this update. That is the guarantee the C operation needed. It does not reveal which cache or coherence component performs the serialization internally. If I compile the same code for an ARM target without LSE, the visible instruction sequence becomes a retry loop:
LBB0_1:
ldaxr x11, [x9] ; load-EXCLUSIVE: load and tag this address for me
add x11, x11, x10 ; do the add in a register
stlxr w12, x11, [x9] ; store-EXCLUSIVE: succeeds only if nobody touched it
cbnz w12, LBB0_1 ; w12 != 0 means it failed; go back and try againThis is load-exclusive / store-exclusive. ldaxr establishes an exclusive monitor for the address. stlxr reports failure if the exclusive state was lost before the attempted store, and cbnz retries. Under contention the emitted loop can execute several times before it succeeds. The LSE version removes that software-visible retry loop. It may still encounter contention inside the implementation, so one opcode does not mean one cycle. Same C operation, same language guarantee, two different instruction paths depending on the ARM target.
That retry loop isn’t just a historical curiosity, because +1 is the one update the hardware has a single instruction for. The moment you want anything else, “increment unless it’s already at the max,” “push onto a lock-free stack,” “add this float,” there’s no ldadd for it, and you write the retry loop yourself in C with compare-and-swap: read the current value, compute the new one, and atomically swap it in only if the value is still what you read. If someone changed it under you, the swap fails, you reload and try again. It’s the ldaxr/stlxr dance hoisted up into your source. I built the counter that way, compare_exchange in a loop, and counted how often the swap actually fails as I added threads all fighting over the one counter:
1 threads: retries=0, 0.0% of CAS attempts failed
2 threads: retries=677834, 6.3% of CAS attempts failed
4 threads: retries=9436470, 32.1% of CAS attempts failed
8 threads: retries=86131199, 68.3% of CAS attempts failedOne thread never fails, it’s alone, nothing changes the value under it. Two threads fail about one swap in sixteen. By eight threads more than two of every three CAS attempts fail and have to redo the read-compute-swap from scratch, so most of the work the CPUs are doing is thrown away and repeated, and the counter still comes out exactly right every time because a failed CAS changes nothing, it just wastes the trip. This is the tax the LSE ldadd was invented to avoid: for plain addition the hardware serializes the adds and nobody retries, but for everything else you’re back in the spin loop, and the spin gets worse the more you parallelize. The correctness never wavers. The efficiency falls off a cliff, and the cliff is contention.
What the atomic costs
So how much does indivisibility cost? I put a single thread in a tight loop doing 200 million atomic_fetch_adds and timed it, comparing memory orders, because atomics come in flavors and the folklore is that stronger ordering is slower:
plain non-atomic += 0 ms 0.00 ns/op <- compiler folded it away
atomic relaxed 322 ms 1.61 ns/op
atomic acq_rel 324 ms 1.62 ns/op
atomic seq_cst 320 ms 1.60 ns/opTwo things surprised me here. First, the plain non-atomic loop measured zero, because of course it did, the compiler folded 200 million += 1 into one add exactly like the racing loop above; you can’t benchmark against a baseline the optimizer deletes. When I forced a real per-op number with a volatile, a plain increment ran about 0.25 to 0.5 ns, so an uncontended atomic is roughly three to six times a plain add. Not free, but not scary either.
Second, relaxed, acquire-release, and sequentially-consistent atomics were indistinguishable in this single-threaded probe, about 1.6 ns each, even though relaxed compiled to ldadd and the ordered forms compiled to ldaddal. The result says that this benchmark could not resolve an ordering cost. It does not say acquire and release are universally free. The loop has no independent shared-memory traffic whose movement needs to be constrained, and its one dependency chain already serializes repeated updates to the same object. A different access pattern can expose costs this loop cannot.
The 1.6 ns is the uncontended number, one thread, the cache line sitting warm in its L1 the whole time. Contention is a different world. I gave two threads their own separate atomics on separate cache lines and had each hammer its own 100 million times, then pointed both threads at the same atomic and did it again:
plain volatile 1 thread 0.29 ns/op
2 threads, own atomics 0.89 ns/op (uncontended)
2 threads, SAME atomic 3.33 ns/op (contended)Two threads on their own lines run at 0.89 ns/op counting both threads’ work, so they’re genuinely parallel, each doing its ~1.6 ns of work at the same time as the other. Point them at one shared atomic and it jumps to 3.3 ns/op, nearly four times slower, because now the single cache line holding the counter has to bounce between the two cores on every increment: core A grabs the line, adds, then core B has to pull the line away from A to do its own add, then A pulls it back, hundreds of cycles a trip. The atomic instruction is still cheap; what’s expensive is that only one core can own the line at a time and they’re fighting over it. This is the real cost of the shared counter, and it’s a cost you pay for correctness whether you use atomics or locks, because the sharing itself is the problem.
I got that clean 0.89 ns number on the second try, because the first time my two “separate” atomics were declared as _Atomic long ca[2], two adjacent longs, eight bytes apart, and they measured 3.36 ns/op, indistinguishable from the fully-contended case even though the threads never touched each other’s variable. Two variables that are never shared, behaving exactly like one variable that is. That’s the next section, and I walked straight into it by accident.
There’s one more wrinkle this machine adds that a uniform CPU wouldn’t. The M4 is heterogeneous: four performance cores and six efficiency cores. I cannot pin these pthreads to a specific core on macOS. I can only give the scheduler quality-of-service hints, then infer from stable timing clusters that interactive work usually ran on faster cores and background work usually ran on slower ones. That is weaker evidence than reading a verified CPU identifier. With that limitation, the contended atomic produced two bands:
both P-cores (user-interactive) 3.29 ns/op
both E-cores (background) 4.63 ns/op
both P-cores (again) 2.78 ns/op
both E-cores (again) 4.37 ns/opThe hinted background runs cost about 40 percent more. The result is consistent with different core classes, but the probe did not prove placement. The safe conclusion is narrower: scheduler policy changed the cost of the same contended operation, and a run that reports only a mean without recording policy can mix two performance populations.
All of this points at a conclusion that felt wrong the first time I saw it, so I made the machine say it plainly. I fixed the total work at 200 million increments of one shared atomic and split it across more and more threads, expecting that two cores would finish in half the time of one, four in a quarter, the usual parallel dream:
1 threads 320 ms 1.60 ns per increment
2 threads 562 ms 2.81 ns per increment
4 threads 1246 ms 6.23 ns per increment
8 threads 3766 ms 18.83 ns per increment
10 threads 4833 ms 24.16 ns per incrementIt goes the wrong way. Every core I add makes the same total work take longer, not shorter. One thread does 200 million increments in a third of a second; ten threads take five to six seconds to do the exact same 200 million, fifteen to twenty times slower with ten times the hardware. The counter is always correct, all 200 million land. This is negative scaling, and it’s the whole tragedy of shared mutable state compressed into one table: the cores aren’t doing more work in parallel, they’re spending nearly all their time shipping one cache line back and forth and waiting their turn for it, and the more of them there are, the longer the line of cores waiting to touch the counter, and the worse it gets. A shared counter is not a thing you parallelize. It’s a thing that gets slower the more you try. Every layer of this post has been circling that fact, and here it is as a monotonic column of numbers going the wrong direction.
The other thing the hardware reorders
There’s a subtler problem that the counter race doesn’t even show, and it’s the one that turns lock-free programming into a minefield. Modern CPUs do not execute your memory operations in the order you wrote them. To hide memory latency, a core will reorder loads and stores, and, critically, two different cores can observe each other’s writes in different orders. On a weakly-ordered architecture like ARM (this machine), if thread A writes data = 42 then ready = 1, thread B can see ready == 1 while still reading the old data, because the two writes reached B’s core out of order. Code that carefully sets a flag after filling a buffer can be seen with the flag set and the buffer empty.
This is the memory model, and it’s why atomics carry more than indivisibility, they carry ordering guarantees. An atomic write with “release” semantics and an atomic read with “acquire” semantics form a barrier: everything the writer did before the release is guaranteed visible to a reader that sees the acquire. That pairing is what makes the flag-then-buffer pattern safe. x86 has a relatively strong memory model that forgives a lot of missing barriers, which is exactly why lock-free code written and tested on an Intel laptop so often breaks when it’s moved to ARM, the ARM chip actually does the reordering the x86 quietly didn’t, and the missing acquire/release that x86 tolerated becomes a real, rare, catastrophic bug.
I tried to catch it in the act. I wrote a message-passing litmus test, one thread storing data then flag with relaxed atomics, another reading flag then data, and ran it fifty million rounds looking for the reader that sees the flag set and the data stale:
violations (flag seen set, data stale): 0 out of 50000000Zero. Which is not proof this M4 won’t reorder them, it’s a demonstration of why the bug is so dangerous. My harness resets the variables between rounds with a barrier, and that barrier probably imposes exactly the ordering the bug needs to be absent; catching a real reorder wants free-running threads pinned to different core clusters and a much longer run, its own small project. So the scariest failure in concurrent programming is one I described, reached for, and could not make happen on demand in an afternoon, which is the whole point: it’s rare enough to survive a stress test built to provoke it, and then it fires in production six months later on someone else’s machine. That is the part of concurrency that’s genuinely hard, the failures are invisible on the machine you tested on.
I couldn’t leave it there. The whole post is supposed to be evidence, and that section was the one claim I was taking on faith, so I built the harness I’d just described as its own small project: free-running threads, no reset barrier between rounds, writer looping data=1; flag=1 and then clearing both, reader looping flag-then-data and counting every time it sees the flag set with the data stale, one thread nudged onto the P-cluster and the other onto the E-cluster so their writes have to cross a coherence boundary. Twenty seconds:
free-run 20s: 1982198251 reads, violations (flag set, data stale): 12558234Twelve and a half million violations. For about four seconds I thought I’d caught it. Then I looked at what my writer actually does, data=1; flag=1; flag=0; data=0, over and over, and realized the reader seeing flag==1, data==0 doesn’t need any reordering at all. It just needs its two loads to straddle the writer’s reset: read flag while it’s 1, the writer races ahead and sets flag=0; data=0, then read data and get 0. That’s a perfectly ordinary interleaving, the same load-then-clobber that ate the counter, and it has nothing to do with the memory model. My “violations” were an artifact of resetting inside the loop, a self-inflicted confound. The barrier’d version imposed too much order and saw zero; the free-running version imposed too little and drowned in false positives. Both harnesses were wrong in opposite directions.
So I built a third one designed to have no reset to straddle. The writer publishes a monotonically increasing tag: data = t then flag = t, forever, t only ever going up. Because in program order the writer sets data before flag, and both only increase, at every real instant in memory data >= flag. The reader reads flag into f, then data into d. Since data only grows and is always at least flag, a machine that respects the order can only ever see d >= f. If the reader ever sees f > d, the flag is somehow ahead of the data, and that can only happen if the writer’s flag store became visible before its data store, or the reader’s own two loads got reordered. Either one is a genuine weak-memory event, and there’s nothing to straddle because nothing resets. Twenty seconds, cross-cluster:
tag-litmus 20s: 2222175034 reads, flag>data events: 1049518190, max gap: 1472A billion events. Forty-seven percent of all reads saw the flag ahead of the data, by as much as 1472 tags. That is far too many. Real store-store reordering is supposed to be rare, the once-in-fifty-million ghost the acquire/release rule exists to exorcise, not something that happens on half your reads. A number that big means my harness is measuring something structural, not the rare bug. So I checked whether the compiler had quietly swapped my two loads (relaxed loads to different addresses can legally be reordered by the compiler), and it hadn’t, the assembly loads flag then data in the order I wrote. The reorder was real and it was happening in the hardware, but the volume told me it wasn’t the reorder I was hunting.
The C++ model gives a cleaner description than my first hardware story. Every atomic object has its own modification order. There is an order for updates to data, and another order for updates to flag, but relaxed operations do not combine those into one order across both objects. A reader is therefore allowed to observe a newer flag and an older data. The outcome is real for this program. The program alone cannot tell me whether the implementation produced it through store propagation, load execution, compiler scheduling, or some combination. Calling it a stale cache line would select a mechanism the counters do not identify.
I changed the layout anyway. The first version placed data and flag on separate 128-byte boundaries. The second put the two atomic words next to each other:
same line (data,flag adjacent): 3038553803 reads, flag>data events: 10922, max gap: 396
separate lines (original): 1580656268 reads, flag>data events: 741999650, max gap: 1340The layout changed the frequency by roughly sixty thousand times. It did not turn the pair into one atomic object. Cache coherence can govern transfers and ownership at a line-sized granularity while the architecture and the language still perform two separate word loads and two separate word stores. Another thread may observe a state between those operations even when the words occupy one line. The experiment proves that placement strongly affected this implementation. It does not prove that the same-line run read a consistent two-word snapshot, because no such guarantee exists.
I ran one more control to make sure the P/E boundary wasn’t the real story, since I’d deliberately put the two threads on different clusters. Same separate-line test, but both threads nudged onto the P-cluster this time, against the cross-cluster run:
both P-cluster: 10609361416 reads, events: 3430473077 (32.3%), max gap: 938
cross-cluster: 1434444049 reads, events: 672810044 (46.9%), max gap: 1348The background-hinted reader produced fewer reads and a higher event fraction than the interactive-hinted pair. Since QoS is not affinity, I cannot label those rows as verified P-to-P and P-to-E traffic. What survives the limitation is that scheduler policy and placement altered the observation rate. A litmus result reported only as an event count, without the number of reader iterations and the placement method, would hide both changes.
The remaining 10,922 events need no special promotion. They are permitted observations from two relaxed atomic objects. The failed part was my attempt to infer one microarchitectural cause from them. Three harnesses exposed three different limits: the barrier harness added synchronization that suppressed the outcome, the reset harness counted ordinary interleavings, and the monotonic harness showed an allowed cross-object ordering but could not attribute it to one hardware event.
The program that needs to publish ordinary data should stop trying to recognize a rare outcome and establish an ordering relation instead:
int data;
std::atomic<bool> ready = false;
// publisher
data = 42;
ready.store(true, std::memory_order_release);
// consumer
if (ready.load(std::memory_order_acquire)) {
assert(data == 42);
}If the acquire load takes the value written by the release store, the operations synchronize. The store to data is sequenced before the release, the acquire is sequenced before the read of data, and those edges compose into happens before. That is why the ordinary read is not a race and must see 42. This claim comes from the language rules, not from a run that happened to print zero violations. The rules are stronger evidence for all conforming executions than another billion iterations on one M4.
Correct and still slow: false sharing
Suppose the updates are atomic, target different objects, and remain slow. My first probe placed two counters in a struct, added 128 bytes of padding in the second version, and printed 52 ms beside 23 ms. The conclusion looked obvious. It was not yet a valid layout experiment because I had not printed the struct’s address. Two objects separated by eight bytes can land on opposite sides of a boundary, and two padded objects can inherit an unexpected offset. A byte distance without the base address is incomplete evidence.
I rebuilt the probe around 512 bytes of storage aligned to 256. One atomic counter begins at offset zero. The second is constructed at a chosen offset. Both threads perform twenty million relaxed atomic increments, so the program is defined and the compiler cannot replace the loop with one addition:
alignas(256) static std::byte storage[512];
auto* first = ::new (storage) std::atomic<std::uint64_t>(0);
auto* second =
::new (storage + offset) std::atomic<std::uint64_t>(0);
std::thread a([&] {
for (std::uint64_t i = 0; i < 20'000'000; ++i)
first->fetch_add(1, std::memory_order_relaxed);
});
std::thread b([&] {
for (std::uint64_t i = 0; i < 20'000'000; ++i)
second->fetch_add(1, std::memory_order_relaxed);
});The program printed both address residues before timing seven runs at every offset. These are the minimum, median, and maximum milliseconds from the run used for this revision:
base address modulo 128: 0
offset second address mod 128 min median max
8 8 111 148 211
16 16 128 155 210
32 32 113 163 210
64 64 31 32 32
96 96 31 32 32
120 120 32 32 32
128 0 32 32 32
192 64 31 32 32
256 0 31 32 32The placement result survived the correction, although the near placements varied substantially. Offsets through 32 had medians from 148 to 163 ms and individual runs as high as 211 ms. Offset 64 held at 32 ms, and larger offsets stayed there. Both final values were correct. The slowdown therefore came from coherence contention caused by nearby writes, not from lost updates.
This is false sharing: the program shares a coherence resource even though it does not share an object. A write needs sufficient ownership of the region containing the target. When the other core writes a nearby target governed by the same region, ownership moves again. The source contains two independent atomics; the coherence protocol sees a location at a coarser granularity.
The remaining surprise is still real:
$ sysctl hw.cachelinesize
hw.cachelinesize: 128The reported cache-line size is 128 bytes, while this write pattern has a sharp performance boundary at 64. The corrected alignment rules out an accidental crossing at offset 64. It still does not tell me whether the relevant implementation structure is a coherence sector, a write granule, a sub-line state, or something else Apple has not documented publicly. I can report the behavioral boundary and the addresses. I cannot derive a complete cache protocol from elapsed time.
Padding these counters to 128 bytes avoids the measured interference on this machine. It is not a universal constant to paste around every field. Padding increases object size, consumes more cache capacity, changes prefetch behavior, and may move the problem on another architecture. The durable rule is to isolate independently written hot state according to the target’s destructive-interference requirements, then print the addresses and measure the actual layout. That exact constraint returns when each runtime worker receives its own task queue.
When one operation isn’t enough: locks and deadlock
Atomics handle a single indivisible update. But most real critical sections are more than one operation, move money from account A to B, insert into a tree, update two fields that must stay consistent, and there’s no atomic instruction for “do these five things as a unit.” For that you need a mutex, a lock that only one thread can hold at a time: acquire it, do the whole critical section knowing no other thread is inside, release it. In C++ you wrap it in an RAII guard from the std::move post so it’s released automatically. Locks make arbitrary critical sections safe, at a price: threads waiting for a held lock are doing nothing, so a hot lock serializes your parallel program back into a sequential one.
I wanted the price in nanoseconds, so I built the same two-thread counter three ways and timed 20 million increments per thread: the atomic, and then a plain long guarded by a pthread_mutex_t locked and unlocked around each ++. Both come out correct at exactly 40 million:
atomic 2 threads 3.33 ns/op counter=40000000
mutex 2 threads 7.18 ns/op counter=40000000
mutex / atomic = 2.2xThe mutex is about 2.2 times the atomic, cheaper than I expected. A mutex implementation can acquire an uncontended lock through userspace state and use a kernel-assisted slow path when a waiter must sleep. This timing is consistent with most acquisitions avoiding a park, but I did not trace the kernel path in this run, so the ratio cannot identify the exact implementation. The critical section contains one increment and releases quickly. Lengthening it changes both the probability that another thread finds it held and the decision to spin or sleep. Even “locks are slow” hides the duration of the critical section, the number of waiters, and the implementation’s parking policy.
And locks introduce a failure mode atomics don’t have: deadlock. Two threads, two locks. Thread A grabs lock 1 and reaches for lock 2; thread B grabs lock 2 and reaches for lock 1. Neither will let go of what it holds, neither can get what it needs, and both wait forever, the program simply stops. The classic cause is two threads acquiring the same locks in opposite orders, and the classic fix is a global rule that locks are always acquired in a consistent order (or a primitive like std::scoped_lock that takes several at once with deadlock avoidance built in). Deadlock is where concurrency stops being about wrong answers and starts being about frozen programs.
I’d sketched that from the mechanics, so I went and actually built it, because “the program simply stops” is more convincing when you watch it stop. Thread A locks L1, sleeps 50 ms to guarantee B gets a head start, then reaches for L2. Thread B locks L2, sleeps, then reaches for L1. A third watchdog thread sits on a two-second timer so the program doesn’t hang my terminal forever:
A: holds L1, wants L2
B: holds L2, wants L1
WATCHDOG: 2s elapsed, still frozen. state: A_got_L1=1 A_got_L2=0 B_got_L2=1 B_got_L1=0
WATCHDOG: classic deadlock, A waits on L2 (held by B), B waits on L1 (held by A). killing.There it is, frozen solid. A_got_L1=1 but A_got_L2=0, B_got_L2=1 but B_got_L1=0: both threads are holding exactly one lock and blocked forever on the other one, and the two seconds the watchdog waited was the program doing absolutely nothing, no CPU, no progress, just two threads politely waiting on each other until the heat death of the process. The whole run took 2.4 seconds, all of it dead air. Then I applied the fix, made both threads take L1 before L2, same order, and ran it again:
B: holds L1, wants L2 (same order as A now)
A: holds L1, wants L2
finished cleanly (no deadlock this run)Done in 0.687 seconds, no watchdog. The fix isn’t a clever algorithm, it’s a discipline: everyone agrees on an order for the locks and never violates it, and the cycle that deadlock needs can’t form because you can’t have A waiting on B while B waits on A if both always reach for the lower-numbered lock first. That’s the entire content of “always acquire locks in a consistent order,” and it’s a rule you have to hold in your head across an entire codebase, in every function that touches two locks, forever, which is exactly the kind of global invariant humans are bad at maintaining and exactly why the next section wants to take the locks away from you.
The thread lasted longer than the work
The ordered-lock version finished, but its fix left a new ownership problem. Every caller that wanted concurrent work still had to create a thread, retain its handle, join it on every exit path, decide where an exception should go, and prevent the thread from referring to objects that had already died. The locks were ordered. The program around them was not yet manageable.
I reduced the next question to an empty function. If each unit of work receives a fresh std::thread, how much time goes into work that does nothing?
for (int i = 0; i < 2000; ++i) {
std::thread([] {}).join();
}Creating and immediately joining 2,000 threads took 41 ms in the recorded run. I then created four workers once, submitted 2,000 tasks through a queue, waited for all their returned values, and got this:
dispatch fresh-threads-ms=41 pool-ms=1 tasks=2000 sum=1999000The pool measurement deliberately starts after its four worker threads exist. It measures steady-state dispatch, while the first measurement includes every thread creation and join. That is the comparison a reused runtime is designed to change. The sum is the sum of integers from zero through 1,999, so it also prevents the empty task path from becoming an unverified timing loop.
This is not a universal 41-to-1 speedup. Both numbers are too short, and the printed milliseconds discard fractions. It establishes the scale of this specific failure. A few thousand tiny tasks cannot each own an operating-system thread without making thread lifecycle a material part of their cost.
The queue eventually became the work
Removing thread creation does not make task submission free. Each task in this pool allocates shared state, constructs a move-only wrapper, acquires the queue mutex, enters the deque, wakes a worker, leaves the deque, writes a result, wakes a future, and is finally destroyed. If the function does less work than that path, the runtime is processing envelopes rather than payloads.
I kept useful work fixed at 120 million xorshift iterations and changed only how many tasks carried it. Four workers ran every case. With four tasks, each task performed 30 million iterations. With 400,000 tasks, each performed only 300. Five runs at each point produced:
tasks iterations per task min ms median ms max ms
4 30,000,000 45 45 50
40 3,000,000 45 49 50
400 300,000 46 46 46
4,000 30,000 49 49 50
40,000 3,000 52 53 54
400,000 300 163 165 166The first three rows stay close. Dividing the work into 400 tasks gives the scheduler a hundred times more choices than four tasks while adding one millisecond to the median. At 4,000 tasks the management path becomes visible. At 400,000 tasks, the same arithmetic takes 165 ms instead of 45 ms.
Subtracting the four-task baseline leaves about 120 ms. Dividing by 400,000 gives roughly 300 ns of additional wall time per tiny task:
(165 ms - 45 ms) / 400000 tasks = 0.00030 ms per task
= 300 ns per taskThat is not the latency of one queue operation. Four workers overlap result production, while the submitting thread serializes part of the enqueue path, and allocator behavior is mixed into both. It is an empirical marginal cost for this complete submit-to-get path under this workload. Treating it as the mutex cost would repeat the mistake of inferring a cache protocol from one elapsed time.
Three hundred nanoseconds looks small until the useful function also lasts a few hundred nanoseconds. The 400,000-task case turns approximately the same amount of arithmetic into 3.7 times as much wall time. The runtime did not suddenly become inefficient. I asked it to perform 400,000 allocations, state transitions, queue transfers, and destructions in order to schedule chunks that contained only 300 simple iterations each.
Combining adjacent work is one repair. If one task processes a block of 1,000 elements rather than one element, queue and future costs are paid once for the block. The block cannot be arbitrarily large. Four giant tasks leave no spare work to redistribute when one block encounters slower data, a page fault, or a different branch. A cancelled operation may also wait longer for a coarse task to reach its next stop check.
The useful boundary is therefore measured, not named. Tasks must be small enough to expose parallelism and imbalance, and large enough to amortize scheduling. The 4-to-400 rows say this loop had a wide safe region on four workers. The 400,000 row says single-element style decomposition would spend more time moving task ownership than exploiting it.
This benchmark is friendly to the central queue. The producer submits from one thread, tasks return one integer, and no task creates children. Multiple producers would contend on the same mutex. Larger result types would change shared-state construction and movement. A custom allocator could remove part of the allocation cost. None of those changes remove the need to measure granularity using the complete runtime path rather than timing the user function alone.
A task must therefore be an object that can wait somewhere until one of a fixed number of longer-lived workers is ready. The first runtime had only these pieces:
class BoundedThreadPool {
public:
using Task = std::packaged_task<void()>;
private:
const std::size_t capacity_;
std::vector<std::thread> workers_;
std::deque<Task> queue_;
std::mutex mutex_;
std::condition_variable not_empty_;
std::condition_variable not_full_;
bool accepting_ = true;
bool stopping_ = false;
};std::packaged_task<void()> is used here as a move-only callable container. The runtime does not use its built-in future. The submitted callable will capture the small promise implementation that appears later, and that promise must have one owner. A std::function<void()> would reject that move-only capture in this C++20 build because the stored target must be copyable.
The deque owns tasks that have been accepted but not started. The worker vector owns the operating-system threads. The pool owns both, so its destructor has somewhere to join the workers. Those ownership edges are the first thing the raw-thread version lacked.
The queue capacity is not a tuning detail. Without it, a producer can allocate tasks faster than workers retire them until memory becomes the accidental admission controller. With a capacity, submission sometimes has to wait. That waiting path forced the runtime to confront the same locks and ordering rules the task interface was supposed to hide.
The queue needed two reasons to wake
A worker has three relevant observations: the queue contains a task, shutdown has started, or neither is true. It cannot hold the queue mutex while sleeping because a producer needs that mutex to insert the task that will wake it. It also cannot unlock and then call an unrelated sleep operation because a producer could notify during the gap. The notification would be lost, leaving a task in the queue beside a sleeping worker.
A condition variable joins those actions. The C++ condition-variable specification defines wait to unlock the mutex and block as one atomic operation with respect to notifications, then lock the mutex again before returning. It also permits a wait to return spuriously. The worker must therefore test a predicate before every sleep and again after every wake:
void worker_loop() {
while (true) {
Task task;
{
std::unique_lock lock(mutex_);
not_empty_.wait(lock, [&] {
return stopping_ || !queue_.empty();
});
if (queue_.empty()) {
return;
}
task = std::move(queue_.front());
queue_.pop_front();
}
not_full_.notify_one();
task();
}
}The predicate has two terms because a worker must wake for work and for shutdown. A notification is not stored as a durable fact. The protected state is the fact. queue_.empty() and stopping_ are read while holding the same mutex used to change them. The condition variable only makes it efficient to wait until that state might have changed.
Moving the task out before releasing the lock would be necessary anyway. Executing it under the queue mutex would turn four workers into one worker plus three blocked threads. User code might run for seconds, submit another task, or throw. None of that belongs inside the scheduler’s queue critical section.
After the pop, one slot is free, so the worker notifies a producer waiting on not_full_. This is a different condition from not_empty_. Combining them into one condition variable can be made correct because every waiter rechecks its predicate, but it wakes threads that cannot make progress. Keeping the conditions separate records why each population is asleep.
Submission is the mirror image:
std::unique_lock lock(mutex_);
not_full_.wait(lock, [&] {
return queue_.size() < capacity_ || !accepting_;
});
if (!accepting_) {
throw std::runtime_error("submit on stopped pool");
}
queue_.push_back(std::move(task));
lock.unlock();
not_empty_.notify_one();The test for accepting_ happens after the wait. A producer may begin waiting while the pool accepts work, then wake because shutdown changed the state. Checking only before sleeping would allow a task to enter after the shutdown boundary.
Unlocking before notify_one is not required for correctness here. It avoids waking a worker only to make it block immediately on the mutex still held by the producer. Correctness comes from modifying the predicate state under the mutex and testing it in a loop, not from a fragile notify-before-unlock or notify-after-unlock rule.
This queue is first-in, first-out. That is easy to reason about, but it creates one mutex all workers and producers must acquire. The earlier shared counter already predicted what happens when more cores fight over one location. I kept the central queue because it gives the shutdown and result paths a small surface on which to become correct. It is not the final scheduling design.
The value could outlive the worker
A void() task is not useful enough. The caller submits f, the worker eventually runs it, and the caller needs either the returned value or the exception. The worker cannot write into a local variable in submit; that stack frame usually ends before the task begins. The result needs storage whose lifetime is independent of both stack frames.
That storage is a shared state:
template<class T>
struct SharedState {
std::mutex mutex;
std::condition_variable ready_cv;
std::optional<T> value;
std::exception_ptr error;
bool ready = false;
};The promise is the producing end. The future is the consuming end. Both hold a std::shared_ptr to this state, so destroying the pool after a task finishes does not destroy a result whose future still exists. The state owns either a T or an exception. ready says one of them has been installed.
This is the same shape the standard futures clauses specify: an asynchronous provider puts a value or exception into shared state, makes the state ready, and unblocks an asynchronous return object. I implemented the small subset this pool needs because the location of every synchronization edge matters to the investigation:
template<class T>
class Promise {
public:
Promise() : state_(std::make_shared<SharedState<T>>()) {}
Promise(const Promise&) = delete;
Promise& operator=(const Promise&) = delete;
Promise(Promise&&) noexcept = default;
Future<T> get_future() {
if (future_taken_)
throw std::logic_error("future already retrieved");
future_taken_ = true;
return Future<T>(state_);
}
void set_value(T value) {
std::unique_lock lock(state_->mutex);
if (satisfied_)
throw std::logic_error("promise already satisfied");
state_->value.emplace(std::move(value));
state_->ready = true;
satisfied_ = true;
lock.unlock();
state_->ready_cv.notify_all();
}
void set_exception(std::exception_ptr error) {
std::unique_lock lock(state_->mutex);
if (satisfied_)
throw std::logic_error("promise already satisfied");
state_->error = std::move(error);
state_->ready = true;
satisfied_ = true;
lock.unlock();
state_->ready_cv.notify_all();
}
private:
std::shared_ptr<SharedState<T>> state_;
bool future_taken_ = false;
bool satisfied_ = false;
};The complete probe gives the move constructor special treatment and makes an abandoned unsatisfied promise store a broken-promise exception. Those cases are omitted from this excerpt only to keep the synchronization path visible.
Future::get waits on the same state mutex and predicate:
template<class T>
class Future {
public:
T get() {
if (!state_)
throw std::logic_error("future has no state");
auto state = std::move(state_);
std::unique_lock lock(state->mutex);
state->ready_cv.wait(lock, [&] { return state->ready; });
if (state->error)
std::rethrow_exception(state->error);
return std::move(*state->value);
}
private:
explicit Future(std::shared_ptr<SharedState<T>> state)
: state_(std::move(state)) {}
std::shared_ptr<SharedState<T>> state_;
friend class Promise<T>;
};Moving state_ into a local object makes this future single-use. A second get sees no state. Returning moves the value out because this implementation has one consumer. A shared future would need a different interface and rules for concurrent access to the returned object.
The promise modifies the result and ready while holding the mutex. The waiter observes ready while holding the same mutex after the producer releases it. That mutex synchronization makes the constructed T or stored exception_ptr visible. The condition variable prevents idle spinning; it is not the source of visibility by itself.
Submission now creates the shared state before the task enters the queue:
template<class F>
auto submit(F&& function)
-> Future<std::invoke_result_t<std::decay_t<F>&>> {
using Function = std::decay_t<F>;
using Result = std::invoke_result_t<Function&>;
Promise<Result> promise;
Future<Result> future = promise.get_future();
Task task(
[function = Function(std::forward<F>(function)),
promise = std::move(promise)]() mutable {
try {
promise.set_value(std::invoke(function));
} catch (...) {
promise.set_exception(std::current_exception());
}
});
// Wait for queue capacity, then move task into queue_.
return future;
}The task owns the producing endpoint after submission. The caller owns the consuming endpoint. The worker need not know Result; it invokes a type-erased void() wrapper. The wrapper turns every normal return into set_value and every thrown exception into set_exception.
I submitted one task returning 6 * 7 and another throwing runtime_error("task failed"):
future-value=42
future-exception=task failedThe exception did not escape the worker function. If it had, it would have crossed the top-level thread function and called std::terminate. It also was not swallowed. Future::get rethrew it on the caller’s thread, where the caller could handle it as part of retrieving that task’s result.
This changes error propagation from a global side effect into a dependency. A task can fail without corrupting the queue, and the code that depends on its value receives the failure. It does not decide policy. The caller still chooses whether to retry, cancel related work, return an error, or terminate the process.
The future could block the only worker
Future::get waits by blocking its calling thread. That is fine when the caller is outside the pool and the workers can continue. It can deadlock when a worker waits for another task in the same bounded execution resource.
Consider a pool with one worker. Task A begins running, submits task B, then calls b.get(). B is ready to run in the queue, but the only worker is occupied by A. A will not release the worker until B’s future is ready. B cannot make the future ready until A releases the worker. This is the same wait cycle as the two mutexes, expressed through a queue and a future:
worker runs A
A waits for B's future
B waits in the pool queue
pool queue waits for the workerIncreasing the pool to two workers only changes how many such waits it takes to exhaust the pool. If two parent tasks each submit a child and block, both workers can wait while both children remain queued. A future records a dependency, but a blocking get does not schedule that dependency.
One repair is helping. When a worker calls get on an unready pool future, it does not sleep immediately. It runs another ready task from its local queue or steals one, then checks the future again. In the one-worker example, the worker suspends A’s logical execution, runs B, makes B’s state ready, and resumes A. The operating-system thread never becomes unavailable to the dependency that can release it.
Helping introduces reentrancy. Code inside get can now execute arbitrary tasks. A thread-local assumption may be invalidated before get returns. Locks held across the wait can be encountered again by the task chosen to help, recreating deadlock through a less obvious path. The scheduler must define whether helping is permitted, which tasks are eligible, and how cancellation or priority affects the choice.
A continuation avoids occupying the worker in another way. Instead of blocking:
Result b = child.get();
return use(b);the logical task registers “run use when child becomes ready” and returns control to the scheduler. The future’s ready transition enqueues the continuation later. A coroutine packages this suspension point into language machinery so the function can retain local state without retaining the thread. The suspended coroutine frame owns those locals in allocated storage, and the scheduler resumes it when the awaited operation completes.
This probe does not implement continuations or coroutine suspension. Its get is deliberately blocking, so the deadlock is a stated boundary rather than a feature hidden behind the name Future. A production task runtime that expects arbitrary dependency graphs needs helping, non-blocking continuations, enough reserved threads, or a rule forbidding worker-side waits. Merely increasing the default worker count postpones the cycle and makes its arrival workload-dependent.
The callable’s captured inputs have a separate lifetime problem. submit decays and owns the callable object, but a lambda can still contain references:
Future<int> unsafe(BoundedThreadPool& pool) {
int local = 41;
return pool.submit([&] { return local + 1; });
}local dies when unsafe returns. The task may run later and dereference storage whose lifetime ended. The pool owns the lambda, not the object the lambda refers to. Capturing by value changes the ownership edge:
return pool.submit([local] { return local + 1; });For a large object, the caller might move an owning pointer into the task or use shared ownership when several tasks genuinely need the same immutable input. Shared ownership keeps an object alive; it does not make mutation safe. Two tasks holding shared_ptr<vector<int>> can still race if both write the vector.
Result storage solves only the worker-to-caller lifetime. Input captures, cancellation state, queue entries, coroutine frames, and any referenced external resource each need their own owner. The task interface makes those relationships visible enough to inspect. It cannot infer them from a capture written as &.
Shutdown was part of the algorithm
The first pool destructor I wrote set a flag and joined the workers. That sentence hides at least three incompatible meanings:
- Stop accepting new work and finish everything already accepted.
- Stop accepting and abandon queued work.
- Ask running work to stop, abandon queued work, and wait.
The probe implements the first. Calling shutdown closes submission, wakes every sleeper, drains the queue, and joins every worker:
void shutdown() {
{
std::lock_guard lock(mutex_);
if (joined_)
return;
accepting_ = false;
stopping_ = true;
}
not_empty_.notify_all();
not_full_.notify_all();
for (std::thread& worker : workers_) {
if (worker.joinable())
worker.join();
}
joined_ = true;
}The worker does not exit merely because stopping_ is true. Its wait predicate wakes, then it exits only when the queue is empty. If tasks remain, it pops one and continues. The queue eventually becomes empty, each worker returns, and each join completes. A task that runs forever makes drain shutdown wait forever. That is not a hidden timeout. It follows directly from the contract.
I submitted twelve tasks to two workers with a queue capacity of four. Each task slept briefly, incremented a completion counter, and returned its index. Then the pool went out of scope before I called get on the final future:
drain-completed=12 last-value=11All accepted tasks finished before the destructor returned. The future remained valid after the pool and workers died because its shared state owned the result. This run checks both halves of the lifetime boundary.
Submission after shutdown must not disappear silently:
submit-after-shutdown=submit on stopped poolThrowing is one possible API. A production interface might return an expected-like error because rejection is an operational state rather than a programming error. The important property is that the caller receives a definite outcome. A task cannot be accepted into storage no worker will ever drain.
The implementation also gives an unsatisfied promise a broken-promise error when its producing endpoint is destroyed. Otherwise abandoning a queued task could leave Future::get asleep forever. The standard future model requires the same general outcome: an abandoned provider makes its state ready with a broken-promise error. Readiness on failure is what lets every wait terminate.
shutdown is not safe to call concurrently from several owners in this small pool because joined_ is not protected across the complete join operation. The intended owner is the thread that owns the pool. Making shutdown itself concurrent would require another state transition, another waiter population, and a rule for which caller performs the joins. Leaving that unsupported is better than implying that an idempotent-looking early return has proved it safe.
The full queue moved the waiting upstream
Two workers, a capacity of four, and twenty tasks that each sleep for 10 ms create a predictable queue. At most two tasks run and four wait. The producer reaches the seventh submission before the first pair has had time to finish, so submit begins blocking on not_full_.
One verified run printed:
backpressure max-queued=4 blocked-submissions=14
submit-ms=85 total-ms=120 sum=190The maximum queue size never exceeded four. Fourteen calls encountered a full queue before their wait. The submission loop itself took 85 ms because capacity returned only as workers popped tasks. Waiting for every result took 120 ms from the original start. The sum of values zero through nineteen is 190.
The ideal service time is easy to estimate. Twenty tasks multiplied by 10 ms is 200 ms of worker occupancy. Two workers can supply 2 ms of occupancy per millisecond of wall time, so the lower bound is 100 ms if their sleeps overlap perfectly. The measured 124 ms includes thread wakeups, queue operations, timer granularity, and the probe’s other bookkeeping. The dimensions agree:
20 tasks * 10 ms per task / 2 workers = 100 msThe same arithmetic predicts why an unbounded queue is dangerous. If arrivals average 300 tasks per second and two workers each retire 100 per second, the backlog grows by 100 tasks every second. No queue optimization changes that sign. A finite capacity converts growth in memory into delay at the producer. That delay is backpressure: the system refuses to pretend it can accept work faster than it serves work.
Blocking submit is not always the right response. A request-serving runtime may need to reject immediately so the caller can shed load before an SLO expires. A latency-sensitive producer may use a timed submission. A graph runtime may suspend the producing task instead of occupying a worker thread. The bounded queue exposes the overload point. Policy decides what happens there.
This pool has a serious bounded-queue failure that the external producer probe does not trigger. Suppose every worker is executing a task that calls submit, and the queue is already full. Each worker blocks waiting for not_full_. No worker remains available to pop the queue and make space. The runtime deadlocks on one queue even though no user mutex is involved.
That failure follows from treating a worker like an ordinary outside producer. Possible repairs include reserving capacity for internal submissions, executing a submitted child inline when the local queue is full, letting a waiting worker help run other tasks, using per-worker deques that grow, or making submission non-blocking inside the runtime. Each choice changes memory bounds, stack depth, fairness, or scheduling order. A task abstraction concentrates concurrency machinery; it does not remove the need to reason about cycles in waits.
A stop request could not stop a thread
Shutdown closes the pool, but it does not tell a running task to stop. C++ has no safe general operation that kills an arbitrary thread at an arbitrary instruction. The target could hold a mutex, own half-constructed state, or be between changing an object and restoring its invariant. Forced termination would strand those resources and make every scope-based destructor unreliable.
Cancellation therefore has to be cooperative. I implemented the smallest form as a shared atomic flag:
struct StopState {
std::atomic<bool> requested = false;
};
class StopToken {
public:
bool stop_requested() const noexcept {
return state_ &&
state_->requested.load(std::memory_order_acquire);
}
private:
std::shared_ptr<StopState> state_;
};
class StopSource {
public:
StopSource() : state_(std::make_shared<StopState>()) {}
StopToken get_token() const { return StopToken(state_); }
bool request_stop() {
bool expected = false;
return state_->requested.compare_exchange_strong(
expected, true, std::memory_order_acq_rel);
}
private:
std::shared_ptr<StopState> state_;
};The library shipped with Apple clang 15 on this machine did not expose std::stop_source and std::stop_token, despite compiling in C++20 mode, so the probe uses this reduced implementation. The current C++ stop-token specification has a richer shared stop state, callbacks, and guarantees around concurrent registration. This version supports only polling.
The task decides where its invariants permit a stop:
auto result = pool.submit([token = source.get_token()] {
std::uint64_t rounds = 0;
while (!token.stop_requested()) {
++rounds;
if ((rounds & 0xffff) == 0)
std::this_thread::yield();
}
return rounds;
});
std::this_thread::sleep_for(std::chrono::milliseconds(5));
source.request_stop();
std::uint64_t rounds = result.get();The verified result was:
cancel-requested=yes task-observed=yesrequest_stop returning true means this call changed the state from false to true. A second request would return false. The task can return only after it observes the request, so a positive iteration count and a ready future establish that the cooperative path completed.
The acquire and release orders on this one-bit state are stronger than the polling loop alone requires. If the only information is “stop” and no other data is published with the request, relaxed access can make the flag atomic without creating another ordering edge. I used release and acquire so any state prepared before the request would become visible after the task observes it. That is a protocol choice, not a property automatically granted to every object the task can reach. Cancellation code should still avoid treating the flag as permission to read unrelated mutable data without defining who wrote it and which synchronization edge publishes it.
The shared pointer solves another race. The source may be destroyed after issuing the request while a queued task still owns a token. The stop state lives until the last source or token releases it. A raw pointer to a boolean owned by the caller would make cancellation itself susceptible to the dangling-reference failure from task captures.
This does not provide a latency bound. If the task checks once per billion iterations, cancellation waits for that interval. If it blocks in an I/O operation that knows nothing about the token, polling code cannot run. If it ignores the token, the request changes one bit and nothing else. Cancellation latency is a property of every cancellation point along the execution path, not of request_stop.
Queued work introduces another decision. A task whose token is already stopped when a worker pops it can avoid starting expensive work. Removing an arbitrary cancelled task from the middle of the central deque would require finding it under the queue lock and satisfying its promise with a cancellation result. Per-task removal can make cancellation itself an O(n) contended operation. Many runtimes leave the lightweight entry in the queue and let it notice cancellation when scheduled.
An exception and a cancellation are also different outcomes. An exception says execution began and failed. Cancellation says the result is no longer requested, perhaps before execution began. Encoding both as an arbitrary runtime_error loses policy information. The probe keeps the cancellation task’s return simple, but a production future needs a distinct stopped state or an error type that preserves the difference.
Ten hardware threads did not justify thirty-two workers
The pool prevents one thread per task, but it still needs a worker count. std::thread::hardware_concurrency() returned ten on this M4. That number is a hint about hardware execution contexts, not an instruction to create ten threads for every kind of work. Blocking tasks, memory-bound loops, shared locks, and CPU-bound independent work put different pressure on the machine.
I fixed total CPU work at 600 million xorshift iterations. Each worker received an equal slice in one task, and each future returned a checksum so the compiler had to retain the loop. Pool construction occurred before timing. I tested seven worker counts, ran five trials for each, and recorded minimum, median, and maximum elapsed milliseconds:
workers min median max
1 819 820 822
2 409 410 412
4 228 229 230
8 136 138 139
10 114 120 121
16 116 118 121
32 112 114 115The run used Apple clang 15.0.0 with -std=c++20 -O2 -pthread on macOS 15.7.7. Threads used the default scheduler policy. There was no affinity control, no warmup phase beyond earlier probe activity, and no isolation from other processes. Those limitations matter most in the few-millisecond differences at the bottom of the table.
One to two workers halves the median. Four is slower than perfect scaling but still useful. Eight and ten continue to improve. Sixteen and thirty-two do not create another tier of throughput. Their medians remain in the same 114-to-120 ms band as ten. Thirty-two happened to be six milliseconds faster than ten in this set, and their observed ranges overlap. On this non-isolated machine that is not evidence that 22 extra workers found a new supply of execution capacity.
For this independent arithmetic, oversubscription mostly flattened rather than collapsing. That result is more useful than the slogan that extra threads always hurt. These tasks do not share a hot atomic, acquire a mutex, or touch enough memory to exhaust bandwidth. The operating system can time-slice them with limited extra cost at this duration. The earlier shared-counter sweep went in the opposite direction because every additional thread increased coherence contention on one line.
A worker count therefore cannot be selected from core count alone. The runtime needs to know what workers do while scheduled and what makes them wait. CPU-bound independent tasks normally want enough runnable workers to occupy the available cores. Blocking tasks may justify more threads, although asynchronous I/O or coroutine suspension can avoid occupying a thread during the wait. Memory-bound tasks may saturate bandwidth before all cores are busy. Tasks with a shared lock can become slower with every additional waiter.
The benchmark also divided work into exactly as many tasks as workers. That gives each worker one coarse piece and hides queue overhead. If the work has irregular sizes, one unlucky worker can receive most of the long tasks while others empty their queues. The fixed worker count is then correct and the schedule is still poor.
The empty workers could see the work
I forced the imbalance instead of waiting for random task sizes to create it. Four workers each received a private deque, but all forty tasks were inserted into worker zero’s deque. Every task occupied its worker for 5 ms. With stealing disabled, only worker zero was allowed to remove those tasks:
local-deques steal=off ms=234 steals=0 executed=40,0,0,0Forty tasks multiplied by 5 ms predicts at least 200 ms on one worker. The measurement was 234 ms. Three operating-system threads existed and completed no tasks because ownership of queued work, not compute capacity, was the bottleneck.
Then I allowed an empty worker to inspect the other deques and remove from their opposite end:
local-deques steal=on ms=62 steals=30 executed=10,10,10,10Worker zero completed ten. The other workers stole thirty and completed ten each. Four equal workers would have an ideal lower bound of 50 ms for forty 5 ms tasks. The observed 62 ms includes timer behavior, deque locks, wakeups, and steal searches. The important change is not the exact speedup. The same intentionally bad placement went from three idle workers to an even 10,10,10,10 distribution.
Each queue is explicitly separated in memory:
struct alignas(128) Queue {
std::mutex mutex;
std::deque<Task> tasks;
};
std::vector<Queue> queues_;That alignment comes directly from the false-sharing probe. Workers frequently touch their own queue mutex and deque metadata. Packing those fields together would make scheduling state contend before any user task began.
The owner takes from the back of its deque. A thief takes from the front:
bool take_own(std::size_t worker, Task& task) {
Queue& queue = queues_[worker];
std::lock_guard lock(queue.mutex);
if (queue.tasks.empty())
return false;
task = std::move(queue.tasks.back());
queue.tasks.pop_back();
return true;
}
bool steal(std::size_t thief, Task& task) {
for (std::size_t offset = 1; offset < queues_.size(); ++offset) {
std::size_t victim = (thief + offset) % queues_.size();
Queue& queue = queues_[victim];
std::lock_guard lock(queue.mutex);
if (queue.tasks.empty())
continue;
task = std::move(queue.tasks.front());
queue.tasks.pop_front();
return true;
}
return false;
}Taking from opposite ends reduces direct conflict between the common owner operation and the less frequent steal. It also gives the owner recently created work, which often retains useful data near the code that created it, while thieves take older work that may represent a larger remaining branch. Those are tendencies, not guarantees supplied by deque.
The classic Chase and Lev work-stealing deque gives one owner cheap access to the bottom and lets thieves compete for the top with atomic indices. My probe copies the scheduling shape but protects every deque with a mutex. It is not a lock-free Chase-Lev implementation. Calling it one because the ends match would erase the hardest parts: races on the final element, growth of the circular array, memory ordering on weak machines, and reclamation of an old buffer while a thief may still reference it.
Even the locked version has choices the forty-task result hides. It scans victims in a fixed circular order, which can concentrate thieves on the same victim. Random victim selection often spreads attempts. Stealing one task balances gradually but pays more steal overhead; stealing half a queue moves more work but may overshoot. Sleeping after one failed scan reduces wasted CPU but adds wake latency when work arrives. Topology-aware stealing may prefer a nearby core or NUMA node before crossing a slower link.
This M4 cannot provide the multi-socket NUMA experiment the scheduler needs. I did not measure first-touch placement, remote DRAM, or an affinity policy here. A topology claim would therefore be a prediction: on a NUMA system, blindly stealing a task can move execution away from the memory it touches, replacing idle time with remote-memory latency. The scheduler needs task and allocation placement evidence before “better balance” can be equated with “faster.”
The local-deque probe also lacks futures, cancellation, bounded admission, and nested-task help. It proves one scheduling mechanism in isolation. Merging it with the central pool is additional work because every feature interacts with queue ownership. A cancelled task must still satisfy its state. Shutdown must know whether any local deque or executing worker owns work. A future waited on by a worker may need that worker to execute other ready tasks, or a dependency cycle can occupy the entire pool.
The future created an ordering edge, not a force field
The task interface changes the default ownership pattern. Instead of two tasks both incrementing one global counter, each can compute a value it owns and return it:
auto a = pool.submit([] { return 1; });
auto b = pool.submit([] { return 1; });
int counter = a.get() + b.get();No object is concurrently modified. Each worker constructs one result in one shared state, and the caller combines the values after both futures become ready. The final counter is two because the dataflow does not contain a race.
If I hide the original global inside the lambdas, the original failure returns:
long counter = 0;
auto a = pool.submit([&] { return ++counter; });
auto b = pool.submit([&] { return ++counter; });The pool schedules these functions concurrently. The future orders each task’s result with its own get; it does not order the two increments with each other. They remain conflicting non-atomic accesses with no happens-before edge. Tasks are not safer because their syntax is different. They are safer when the program passes immutable inputs, returns owned results, and expresses dependencies through synchronization rather than shared mutation.
The queue itself still contains all the mechanisms from the first half of the investigation. Its mutex has acquire and release behavior. Its condition variables need predicates. Its counters can false-share. A scalable deque needs compare-and-swap and precise memory ordering. The runtime did not remove atomics and locks from the process. It moved them into a smaller component with explicit ownership and tests.
That component is still missing production properties:
- The central queue becomes a contention point as submission rates and worker counts grow.
- Blocking nested submission can deadlock a bounded pool.
- The stealing probe uses mutexes and a linear victim scan.
- No scheduler fairness rule prevents one task class from waiting indefinitely.
- There are no priorities, deadlines, timers, or admission classes.
- A blocking system call occupies its worker because tasks cannot suspend.
- Cancellation is polling only and has no callback integration.
- Shutdown drains forever if a task never returns.
- There is no CPU affinity, NUMA placement, or topology-aware stealing.
- There is no reclamation proof for a lock-free queue.
Those are not decorations for an industrial library. Each is another way accepted work can fail to run, finish too late, observe invalid memory, or keep the process alive forever.
The original counter made one wrong number. Following it far enough produced a sharper prediction. Two raw threads mutating the same object can lose updates or permit the optimizer to replace the loop with something that changes the failure completely. An atomic makes one update indivisible but can turn added cores into coherence traffic. A mutex protects a larger invariant but can create a wait cycle. A task runtime can make owned values and explicit dependencies the normal path, but its queues inherit the same hardware and language rules.
The final difference is visible in two lines. Submit ++counter twice and the runtime cannot predict the answer. Submit two functions that each return one, then combine two ready futures, and it can. The threads did not become easier. The ownership graph did.