Sources this series builds on: Chili's (ChiliTomatoNoodle) multithreading
playlist,
CMU 15-213 (Computer Systems: A Programmer's Perspective), various CppCon talks,
and LLMs for restructuring and sanity-checking. Everything here is my own code,
compiled and run — not just transcribed.
Recap
Parts 3 through 7 were entirely about where data lives — bytes, cache
lines, coherency, false sharing. All of that assumed the actual work being
handed to each thread was already fair: four threads, four equal chunks,
done. This article breaks that assumption. Splitting a job into four
equal-sized pieces by count is not the same as splitting it into four
equal-sized pieces by actual work, and the gap between those two ideas is
a completely different kind of slowdown than anything the hardware track
covered — this one lives entirely in how the job is divided, not in where
its variables sit in memory.
What we're actually studying here: unbalanced load
Strip away the specific code for a moment and name the general shape of
the problem, because it's one you'll recognize outside this series too:
you have N workers and a pile of work, and you split that pile into N
equal-count groups — one per worker. That's the intuitive, almost
automatic way to divide work. It's also only correct under one silent
assumption: that every item in the pile costs roughly the same to process.
The moment that assumption breaks — some items are cheap, some are
expensive, and the expensive ones aren't spread out evenly — equal-count
splitting quietly stops meaning equal-work splitting. Some workers finish
early and sit idle. Others are still grinding through a disproportionate
share of the expensive items. The total work didn't change, and the number
of workers didn't change — only how unevenly the cost of that work was
distributed across them.
That's what "unbalanced load" means as a general term, and it's the exact
case this article measures, concretely, with real code and real numbers:
same tasks, same worker count, three different arrangements of where the
expensive tasks happen to land.
The task: not all work is the same size
class Task {
public:
double val;
bool heavy;
unsigned int process() const {
size_t iterations = heavy ? HEAVY_IT : LIGHT_IT;
double intermediate = val;
for (auto i = 0; i < iterations; i++) {
intermediate = static_cast<double>(static_cast<unsigned int>(std::abs(std::sin(std::cos(intermediate)) * 10'000'000)) % 100'000) / 10'000;
}
return static_cast<unsigned int>(std::exp(intermediate));
}
};
using Chunk = std::array<Task, CHUNK_SIZE>;
Every Task carries a heavy flag. A "heavy" task runs HEAVY_IT
iterations of the inner loop; a "light" task runs LIGHT_IT — an order of
magnitude fewer. Same function, same code path, wildly different cost
depending on that one boolean. Split CHUNK_SIZE tasks into 4 equal-count
groups of CHUNK_SIZE / 4 each, and you've guaranteed each thread gets the
same number of tasks — you've guaranteed nothing about how much actual
work landed in each group.
Three ways to lay out the same tasks
std::vector<Chunk> Thread::generateRandomDataSet() {
std::vector<Chunk> chunks;
chunks.reserve(CHUNK_COUNT);
std::mt19937 rnd(2828);
std::uniform_real_distribution<double> v_dist{ 0, std::numbers::pi };
std::bernoulli_distribution h_dist{ HEAVY_PROBABILITY };
for (size_t c = 0; c<CHUNK_COUNT; c++) {
Chunk chunk;
for (auto& task : chunk) {
task.val = v_dist(rnd);
task.heavy = h_dist(rnd);
}
chunks.push_back(chunk);
}
return chunks;
}
std::vector<Chunk> Thread::generateEvenlyDataSet() {
std::vector<Chunk> chunks;
chunks.reserve(CHUNK_COUNT);
std::mt19937 rnd(2828);
std::uniform_real_distribution<double> v_dist{ 0, std::numbers::pi };
int nth = static_cast<int>(1.0 / HEAVY_PROBABILITY);
for (size_t c = 0; c < CHUNK_COUNT; c++) {
Chunk chunk;
for (auto it = 0; it<chunk.size(); it++) {
chunk[it].val = v_dist(rnd);
chunk[it].heavy = (it % nth == 0);
}
chunks.push_back(chunk);
}
return chunks;
}
std::vector<Chunk> Thread::generateStackedDataSet() {
std::vector<Chunk> chunks = generateEvenlyDataSet();
for (auto& chunk : chunks) {
std::ranges::partition(chunk, [](const Task& t) {return t.heavy; });
}
return chunks;
}
Three datasets, same total number of heavy and light tasks in each chunk —
only the arrangement changes:
-
Random — each task independently has a
HEAVY_PROBABILITYchance of being heavy. Heavy tasks land wherever the random draw puts them. -
Evenly — every
nthtask is heavy, spaced out deterministically through the chunk (nth = 1 / HEAVY_PROBABILITY). -
Stacked — take the evenly-spaced layout and
std::ranges::partitionit, sorting all the heavy tasks to one side. This is the worst case on purpose: every heavy task now clusters together instead of being spread out.
If you then split each Chunk into 4 equal-count slices — CHUNK_SIZE / 4
tasks per thread — the Stacked layout guarantees one or two threads get
almost every heavy task in the chunk, while the others get almost none.
Measuring the imbalance, not just guessing at it
class WorkerController {
// ...
float timeSpendPerWorker = -1.f;
size_t heavyCount = 0;
// ...
void processTasks() {
heavyCount = 0;
for (const auto& task : input) {
*output += task.process();
heavyCount += task.heavy ? 1 : 0;
}
}
public:
float getTimeSpentPerWorker() const { return timeSpendPerWorker; }
size_t getHeavyCount() const { return heavyCount; }
};
Each WorkerController tracks two things per chunk it processes: how long
it actually spent, and how many heavy tasks it happened to get. Both get
written out per chunk:
struct ChunkTimingInfo {
std::array<float, WORKER_COUNT> timeSpentPerWorker;
std::array<size_t, WORKER_COUNT> heavyCountPerWorker;
float totalChunkTime;
};
for (auto& chunk : chunks) {
t.start();
for (int j = 0; j < 4; j++) {
std::span<Task> batch(chunk.begin() + j * (CHUNK_SIZE / 4), chunk.begin() + (j + 1) * (CHUNK_SIZE / 4));
workers[j]->setJob(batch, &outputs[j]);
}
master.wait_for_all();
float chunkTime = t.stop("Chunk Processing Time", false);
ChunkTimingInfo info;
for (int i = 0; i < 4; i++) {
info.timeSpentPerWorker[i] = workers[i]->getTimeSpentPerWorker();
info.heavyCountPerWorker[i] = workers[i]->getHeavyCount();
}
info.totalChunkTime = chunkTime;
chunkTimings.push_back(info);
}
Every chunk gets split into 4 equal-count slices, handed to 4 persistent
workers, and master.wait_for_all() blocks until every worker reports done
— meaning the total chunk time is bounded by whichever worker finishes
last. The per-worker CSV this produces is the actual measurement of the
imbalance, not a guess:
std::ofstream outFile(std::format("chunk_timings_{}.csv", s), std::ios_base::trunc);
for (int i = 0; i < 4; i++) {
outFile << std::format("time_worker_{0:},idle_time_{0:},heavy_{0:},", i);
}
outFile << "total_chunk_time,total_idle,total_heavy\n";
for (const auto& info : chunkTimings) {
float totalIdleTime = 0.f;
int totalHeavyCount = 0;
for (int i = 0; i < 4; i++) {
float idleTime = info.totalChunkTime - info.timeSpentPerWorker[i];
outFile << std::format("{},{},{},", info.timeSpentPerWorker[i], idleTime, info.heavyCountPerWorker[i]);
totalIdleTime += idleTime;
totalHeavyCount += info.heavyCountPerWorker[i];
}
outFile << std::format("{},{},{}\n", info.totalChunkTime, totalIdleTime, totalHeavyCount);
}
idleTime here is the key number: for each worker, it's simply how much
time it spent doing nothing while waiting for the slowest worker to catch
up. A perfectly balanced chunk has every worker's idle time near zero — all
four finish at roughly the same moment. An imbalanced chunk has some
workers idle for a real fraction of the total chunk time, because they ran
out of tasks long before the worker holding all the heavy ones did.
Why this is invisible if you only look at total time
Here's the trap: summing up "total time" across a whole run can look
completely fine even when individual chunks are badly imbalanced, because
imbalance in one chunk doesn't change the total amount of work done —
it only changes how that work was distributed across the 4 workers during
that specific chunk. You have to look at idle time per worker, per chunk,
to actually see the problem. Aggregate throughput numbers can hide it
entirely.
flowchart TD
C["One chunk, 4 equal-count slices"] --> W1["Worker 1: mostly light tasks<br/>finishes early, sits idle"]
C --> W2["Worker 2: mostly light tasks<br/>finishes early, sits idle"]
C --> W3["Worker 3: mostly light tasks<br/>finishes early, sits idle"]
C --> W4["Worker 4: gets the heavy cluster<br/>still working"]
W1 & W2 & W3 & W4 --> Wait["Chunk isn't done until<br/>Worker 4 finishes"]
style W4 fill:#FAECE7,stroke:#993C1D,color:#4A1B0C
style Wait fill:#FAEEDA,stroke:#854F0B,color:#412402Splitting by count guarantees each worker gets the same number of tasks.
It says nothing about whether those tasks cost the same to run, and once
they don't, the whole chunk's completion time is bound to whichever worker
got unlucky — not to the average.
Results — 100 chunks, each layout, same machine
Averaged across 100 chunks per layout, computed directly from the CSV this
code produces:
| Layout | Avg chunk time | Avg total idle (sum of 4 workers) | Idle as % of total worker-time available |
|---|---|---|---|
| Evenly | 0.0162s | 0.00937s | 14.5% |
| Random | 0.01657s | 0.01401s | 21.1% |
| Stacked | 0.00756s | 0.01926s | 63.7% |
That last column is the number that matters: it's total idle time across
all 4 workers, divided by the total worker-time that was actually
available (4 × chunk time) — the fraction of all available work-seconds
that were spent doing nothing.
Evenly is the best case, by design: heavy tasks are spaced out so every
nth task lands in a different worker's slice, and every worker's slice
ends up with almost exactly 100 heavy tasks. Per-worker idle time barely
varies — 13.6% to 15.6% across the four:
| Worker | Avg time | Avg idle | Idle % | Avg heavy tasks |
|---|---|---|---|---|
| 0 | 0.01398s | 0.00222s | 13.7% | 100.0 |
| 1 | 0.01379s | 0.00241s | 14.9% | 100.0 |
| 2 | 0.01367s | 0.00253s | 15.6% | 100.0 |
| 3 | 0.01399s | 0.00221s | 13.6% | 100.0 |
Random gets a real, measurable penalty even though heavy tasks are
still spread out roughly evenly on average — each worker ends up with
close to 100 heavy tasks too (99.4 to 100.4). The difference is that
"close to equal on average across 100 chunks" doesn't mean "equal in any
one specific chunk" — the per-chunk variance in exactly how many heavy
tasks land in each quarter is enough to push idle time up to 20.4%–22.1%
per worker, noticeably worse than Evenly's tight spread despite very
similar heavy-task counts:
| Worker | Avg time | Avg idle | Idle % | Avg heavy tasks |
|---|---|---|---|---|
| 0 | 0.01318s | 0.00338s | 20.4% | 100.4 |
| 1 | 0.01305s | 0.00352s | 21.2% | 99.8 |
| 2 | 0.01291s | 0.00366s | 22.1% | 99.4 |
| 3 | 0.01311s | 0.00345s | 20.8% | 99.5 |
Stacked is where the effect stops being a percentage-point difference
and becomes a completely different shape of result. One worker gets
every single heavy task in the chunk. The other three get none at all:
| Worker | Avg time | Avg idle | Idle % | Avg heavy tasks |
|---|---|---|---|---|
| 0 | 0.00752s | 0.00004s | 0.5% | 167.0 |
| 1 | 0.00115s | 0.00641s | 84.8% | 0.0 |
| 2 | 0.00114s | 0.00642s | 84.9% | 0.0 |
| 3 | 0.00118s | 0.00639s | 84.5% | 0.0 |
Three of the four workers spend roughly 85% of every chunk sitting
completely idle, waiting on the one worker that got the entire heavy
cluster. This is the concrete version of the diagram above — not a
hypothetical, the actual measured outcome once heavy tasks are clustered
instead of spread out.
Worth being precise about what changed and what didn't: the total amount
of heavy work in the Stacked dataset differs from Evenly's in this specific
run (167 vs 400 heavy tasks per chunk) — that's a difference in the
underlying dataset, not something this comparison is claiming to control
for. What the per-worker breakdown isolates cleanly, independent of that,
is the shape of the imbalance: concentrate the same category of
expensive tasks together instead of spreading them out, and idle time
stops being a modest tax and becomes the dominant cost of the chunk.
Takeaways
- Splitting a job into N equal-count pieces only equals "balanced work" if
every piece of work costs the same. The moment cost varies — a
heavyflag, variable-length data, anything — count-based splitting stops guaranteeing anything about actual balance. - Layout matters as much as proportion. Measured across 100 real chunks, idle time went from 14.5% (Evenly) to 21.1% (Random) to 63.7% (Stacked) — same total heavy-task category, only its arrangement changed.
- Even random placement, which balances heavy tasks close to equally on average, still costs more than deliberate spacing — average-case balance across many chunks isn't the same as balance within any single chunk.
- In the worst measured case (Stacked), three of four workers sat idle ~85% of the time, waiting on the one worker that inherited the entire heavy-task cluster — a chunk's completion time is bound to its slowest worker, not its average.
- Aggregate/total timing numbers can hide this problem completely. Only measuring idle time per worker, per chunk, actually reveals it.
Top comments (1)
What do you thing about splitting into very small 'tasks' and using signal trees?
I've just got a fork of BuildingCPP Signal trees (github.com/buildingcpp/concurrency) to work on Windows. It seems almost too fast to be true but also seems to require a lot of situation specific setup to use it. Unlike a much more general thread pool with work stealing. It would be great to generalize 'work contracts' so they're as easy to use as just posting tasks to a thread pool.