Adding worker threads seems like the most direct way to execute independent tasks faster. One thread takes a task from a queue and computes. Two threads take one task each at the same time. Sixteen should process roughly sixteen times as much work, at least until the machine runs out of cores.
In practice, sixteen threads can be slower than one.
The problem does not occur inside the tasks. They are independent, do not modify shared data, and all run the same short arithmetic loop. The threads interfere with one another in only one place: before starting work, each must take its next task from a shared queue.
The queue is protected by a mutex, but the lock is held for only a few nanoseconds, exactly long enough for one pop_front. It seems too brief to affect performance.
We will test this with two schedulers. In the first, every thread obtains work from one global queue. In the second, every thread has its own queue and accesses another only after its local queue becomes empty.
The workload, tasks, and thread counts remain identical. Only one answer changes: must a worker coordinate with everyone else before every task? The complete scheduler source is included in the appendix.
The Most Obvious Scheduler
Begin with one VecDeque protected by a Mutex.
Every worker thread repeats the same loop: take the lock, remove a task, release the queue, and perform the computation.
loop {
let next = match queue.try_lock() {
Ok(mut guard) => guard.pop_front(),
Err(_) => {
contended.fetch_add(1, Ordering::Relaxed);
queue
.lock()
.unwrap_or_else(PoisonError::into_inner)
.pop_front()
}
};
match next {
Some(seed) => {
local_sum =
local_sum.wrapping_add(task(weight, seed));
}
None => break,
}
}Before the ordinary lock, the thread first calls try_lock.
If the queue is free, it acquires the lock immediately. If another worker already owns the mutex, try_lock returns an error and the contended counter increases.
This makes contention directly visible. We are not estimating wait time or inferring it indirectly from a profiler. We count the exact occasions when a thread came for a task and found the door closed.
It then calls the ordinary lock and waits for its turn anyway.
The task is deliberately short:
a short arithmetic loopSuch tasks often appear inside runtimes, thread pools, and event-processing systems. They may be small callbacks, continuations of asynchronous operations, or brief work performed after a task wakes.
Run two million such tasks while gradually increasing the number of workers:
$ cargo run --release --quiet
global queue: 2000000 tasks of weight 20 each
workers time tasks/s speedup lock waits
1 63ms 31.57M 1.00x 0
2 220ms 9.09M 0.29x 321878
4 190ms 10.52M 0.33x 483512
8 290ms 6.90M 0.22x 614838
16 313ms 6.39M 0.20x 633691The single-threaded version finishes in 63 ms.
After adding a second thread, the time rises to 220 ms. Instead of speeding up, execution becomes almost three and a half times slower.
With sixteen threads, it takes 313 ms, roughly five times longer than with one.
The additional cores did not merely stop helping. They began actively interfering with one another.
Every Third Task Begins with Waiting
The last column explains where the time went.
With two threads, there were 321,878 failed attempts to acquire the mutex. With sixteen, the count reached 633,691.
There are two million tasks in total. That means roughly every third task starts with a thread arriving at the queue at the same time as someone else.
The mutex really is held briefly. The problem is not the duration of one critical section but its frequency.
Every worker passes through it before every task:
take the mutex
→ remove one number
→ release the mutex
→ compute briefly
→ take the mutex againWhen work is short, obtaining the next task becomes comparable in cost to executing it.
A thread that loses the mutex does not merely waste a few CPU cycles. It may enter a waiting state, yield its core, and wake again later. At the same time, ownership of the shared cache line containing the mutex and queue structure moves between cores.
Even if no individual step looks expensive, millions of such coordination points quickly become the program's main work.
Contention occurs when several threads simultaneously need to modify the same protected object. What matters is not only how long the lock is held, but also how often every participant must meet at that one point.
The global queue stopped being a mere task container. It became a serial entrance to a parallel system.
Many threads can execute tasks simultaneously, but they still obtain permission for the next piece of work one at a time.
Why the Second Thread Hurts Immediately
We might expect gradual degradation: two threads are slightly faster than one, four remain useful, and problems begin somewhere near sixteen.
Instead, the largest drop occurs when moving from one worker to two.
With one thread, there is no contention. It takes the mutex, removes a task, and continues immediately. The queue almost always remains in its local cache, and nobody else needs the lock.
After the second worker appears, the same structure constantly moves between cores.
Both threads finish a short task at about the same time, return to the queue almost together, and collide on the mutex again. The result is a stable rhythm in which computation synchronizes competitors instead of separating them in time.
Adding more workers only makes the situation noisier. Threads wake, compete for the queue, take one task, and return shortly afterward.
The scheduler that should distribute useful work spends most of its time distributing access to itself.
Giving Every Worker Its Own Queue
Now give each worker a local queue.
A thread takes tasks from the back of its own queue. While work remains there, it does not need to coordinate with other threads:
let mine = queues[me]
.lock()
.unwrap_or_else(PoisonError::into_inner)
.pop_back();
if let Some(seed) = mine {
local_sum =
local_sum.wrapping_add(task(weight, seed));
continue;
}In this simplified implementation, each local queue is also protected by a mutex, but normally only its owner accesses it. The lock therefore does not become a shared meeting point for every worker.
A thread looks into another queue only after its own becomes empty.
It chooses a random worker and takes not one task but half of that worker's remaining work.
This approach is called work stealing.
Work stealing means that each worker executes its own tasks by default. It accesses another worker only when it runs out of work, and moves several tasks at once so that synchronization happens less often.
Taking half is more efficient than taking one task.
A single stolen task finishes quickly, forcing the worker to search for work again immediately. Half a queue is more likely to keep it busy for a while without emptying the victim completely.
Why the Victim Is Chosen Randomly
When a local queue becomes empty, a worker could inspect its neighbors in order.
Worker 0 might try 1, then 2; worker 1 might begin with 2; and so on.
But a shared order can create a new contention point. Several idle threads may notice the same rich queue and line up to take its work.
The global mutex is gone, but everyone meets at one victim again.
Each worker therefore chooses a source randomly using its own generator. Requests spread across queues, reducing the probability that every idle worker arrives at the same owner.
Randomness is not used to improve the computation itself. It keeps threads from synchronizing their decisions.
Two Million Tasks and Only Two Hundred Steals
Run the same workload with local queues:
$ cargo run --release --quiet
local queues + stealing: 2000000 tasks of weight 20 each
workers time tasks/s speedup steals
1 58ms 34.51M 1.00x 0
2 28ms 70.62M 2.05x 2
4 16ms 124.05M 3.60x 7
8 11ms 173.94M 5.04x 138
16 12ms 173.25M 5.02x 197With two threads, performance almost exactly doubled.
Four workers produced a 3.6-fold speedup; eight produced roughly fivefold. Growth then stopped: sixteen threads delivered almost the same result as eight.
This plateau is expected. The machine has six physical cores, while its remaining logical processors use hyper-threading. For a short arithmetic loop, additional hardware threads do not provide new execution resources.
The main difference, however, is in the final column.
The entire sixteen-worker run required 197 steals.
Not one hundred ninety-seven thousand, but one hundred ninety-seven for two million tasks.
In the global scheduler, threads accessed the shared point two million times and found it occupied more than six hundred thousand times.
In the new scheduler, almost all work remained local. Workers communicated only in the rare cases when distribution became uneven.
That is why the difference is so large. Work stealing did not make the shared queue faster. It removed the need to use one before every task.
One Scheduler Slowed Down Fivefold; the Other Sped Up Fivefold
Compare the extreme results.
The global queue with sixteen threads:
6.39 million tasks per second
speedup 0.20xLocal queues:
173.25 million tasks per second
speedup 5.02xThey differ by roughly twenty-seven times.
The task code is identical. The amount of computation is identical. The same operating-system threads run on the same machine.
Only the frequency of coordination changed.
In the first case, every worker must obtain permission for every task. In the second, a worker runs independently for long periods and contacts its neighbors only when idle.
This difference is especially important for a scheduler. Its purpose is to help useful work execute in parallel. If dispatch costs grow with the number of workers, the scheduler consumes the benefit it was created to provide.
Does This Mean a Global Queue Is Always Bad?
So far, we have measured short tasks. Their arithmetic loop finishes quickly, so even a small queue cost occupies a significant share of the runtime.
Increase the computation inside one task and repeat the test:
$ cargo run --release --quiet
tasks per run: 2000000
weight workers global q local+steal ratio
4 1 55.17M 59.56M 1.08x
4 4 14.67M 232.41M 15.84x
4 16 10.59M 300.96M 28.41x
20 1 35.19M 33.83M 0.96x
20 4 9.86M 121.82M 12.35x
20 16 7.52M 145.72M 19.37x
400 1 1.44M 1.44M 1.00x
400 4 5.44M 5.74M 1.06x
400 16 6.75M 10.73M 1.59xThree distinct regimes are now visible.
At weight 4, a task is so small that the global queue loses by 28.41 times with sixteen threads. Workers barely compute; they compete for the right to receive another short action.
At weight 20, there is more useful work, but local queues remain almost twenty times faster.
At weight 400, the situation changes. One task runs long enough that the cost of one queue access disappears behind the computation.
The global scheduler now scales:
1 thread: 1.44 million tasks/s
4 threads: 5.44 million tasks/s
16 threads: 6.75 million tasks/sThe difference from work stealing falls to 1.59 times.
The mutex did not disappear. Workers simply return to it much less often relative to the time spent doing useful work.
What Matters Is the Mutex's Share of the Task
The statement "this mutex is fast" says almost nothing by itself.
Suppose obtaining a task costs one hundred nanoseconds.
If the task takes ten milliseconds, the queue cost is practically invisible. A simple Mutex<VecDeque<_>> may be sufficient, and architectural complexity will not pay for itself.
If the task takes two hundred nanoseconds, the same mutex consumes half the work even before contention begins.
The right question is therefore not:
is this mutex expensive?but:
what share of the task's time is spent obtaining work?A global queue can be an excellent choice for heavy tasks: image processing, file compression, a complex query, or another computation that lasts much longer than a queue operation.
Such a pool has simple code and natural balancing, and a worker always receives the next available task.
For a scheduler of very short jobs, however, the shared queue becomes a bottleneck. An asynchronous task, for example, may wake, execute a few instructions, register another wait, and yield again. If every step begins with all worker threads meeting at one mutex, dispatch can easily cost more than the task itself.
A Local Queue Also Improves Cache Behavior
The most visible difference in the experiment comes from locking, but locality provides another advantage.
When a worker takes the next task from its own queue, related data is more likely to remain in its CPU cache, especially if the task was created or recently executed on the same thread.
A global queue constantly moves tasks between cores. The data those tasks access may move with them.
Work stealing changes the rule: continue locally whenever possible and move work only to correct an imbalance.
That is why real schedulers often take local tasks from one end of a queue while thieves take from the other. The owner receives recently added work that is more likely to remain in its cache, while a thief moves an older batch.
Our implementation is simpler than a production scheduler, but the basic effect is already visible in the results: local execution is the normal state, while transfer between threads is a rare exception.
Steals Do Not Indicate a Balancing Error
It may seem that an ideal scheduler should distribute two million tasks evenly in advance and perform no steals at all.
Real work, however, rarely divides perfectly.
Tasks may have different durations. New work can appear while old work is still running. One worker may receive more continuations because it serves an active connection or repeatedly wakes related tasks.
Local queues deliberately tolerate temporary imbalance because continuous global coordination would cost more.
A steal corrects the imbalance only after it leaves a worker idle.
One hundred ninety-seven steals for two million tasks show that this lazy balancing was sufficient. The scheduler almost never coordinated workers in advance, yet every core received work.
What a Production Runtime Adds
A real multithreaded runtime usually does more than maintain local queues and choose random victims.
It needs a way to accept tasks from outside, such as work created by a thread that is not itself a worker. A global injector often remains for this purpose, but it no longer serves every local continuation.
A separate LIFO slot may hold a task that has just been woken. This allows the runtime to resume work whose data is still in the current core's cache.
Idle workers must not poll neighbors forever and burn CPU. After several failed steal attempts, they park and wake when new work appears.
Fairness limits are needed so that one active chain of tasks cannot monopolize a worker forever, along with a careful wakeup protocol that cannot lose notifications.
These mechanisms solve different problems, but they are built around the same idea demonstrated by the simple experiment:
a worker should execute locally while local work remains; coordination is needed only after that work runs out.
Sixteen Threads Were Not Too Many
With the global scheduler, sixteen threads were five times slower than one.
It is easy to conclude that the thread count itself is the problem: there are too many, the operating-system scheduler cannot cope, or hyper-threading is useless.
But the second scheduler used the same sixteen threads and completed the work almost twenty-seven times faster than the first.
The threads themselves were therefore not the main problem.
The protocol for obtaining work was.
In the global design, each of the two million tasks had to pass through one shared door. As more workers appeared, they spent more time waiting in front of that door.
With work stealing, almost all work was already beside the worker that would execute it. During the entire run, workers had to coordinate a transfer fewer than two hundred times.
Adding processors speeds up a program only when they have work they can perform independently.
If every next step begins with a fight for one mutex, additional threads increase not computing power but queue length.
The global scheduler lost performance not because the lock was held for a long time.
Everyone simply needed it, every time.
Appendix: Full Source Files
global-queue/src/lib.rs — 80 lines
//! Scene 01: the scheduler everyone writes first — one queue, one
//! mutex, N workers.
//!
//! The design is correct and obvious: tasks go into a shared queue,
//! every worker locks it, takes one, runs it. The lock is held for
//! nanoseconds, which is exactly why it looks harmless.
use std::collections::VecDeque;
use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::{Arc, Mutex, PoisonError};
use std::time::{Duration, Instant};
/// The unit of work: a deterministic arithmetic loop. `weight` sets
/// how long one task runs — the whole article turns on this number.
pub fn task(weight: u64, seed: u64) -> u64 {
let mut state = seed | 1;
for _ in 0..weight {
state = state
.wrapping_mul(6_364_136_223_846_793_005)
.wrapping_add(1);
state ^= state >> 33;
}
state
}
/// What a run produced: wall time and how many times a worker had to
/// wait for the queue's lock.
pub struct Run {
pub elapsed: Duration,
pub tasks: u64,
pub contended: u64,
}
impl Run {
pub fn throughput(&self) -> f64 {
self.tasks as f64 / self.elapsed.as_secs_f64()
}
}
pub fn run(workers: usize, tasks: u64, weight: u64) -> Run {
let queue: Arc<Mutex<VecDeque<u64>>> =
Arc::new(Mutex::new((0..tasks).collect::<VecDeque<u64>>()));
let contended = Arc::new(AtomicU64::new(0));
let sink = Arc::new(AtomicU64::new(0));
let started = Instant::now();
let mut handles = Vec::with_capacity(workers);
for _ in 0..workers {
let (queue, contended, sink) = (queue.clone(), contended.clone(), sink.clone());
handles.push(std::thread::spawn(move || {
let mut local_sum = 0_u64;
loop {
// try_lock failing IS the contention this article is about.
let next = match queue.try_lock() {
Ok(mut guard) => guard.pop_front(),
Err(_) => {
contended.fetch_add(1, Ordering::Relaxed);
queue
.lock()
.unwrap_or_else(PoisonError::into_inner)
.pop_front()
}
};
match next {
Some(seed) => local_sum = local_sum.wrapping_add(task(weight, seed)),
None => break,
}
}
sink.fetch_add(local_sum, Ordering::Relaxed);
}));
}
for handle in handles {
let _ = handle.join();
}
Run {
elapsed: started.elapsed(),
tasks,
contended: contended.load(Ordering::Relaxed),
}
}global-queue/src/main.rs — 41 lines
//! Scales the global-queue scheduler across worker counts and prints
//! what the extra cores bought.
use anyhow::Result;
use clap::Parser;
use global_queue::run;
/// Scale one scheduler across worker counts.
#[derive(Parser)]
struct Args {
/// Total tasks per run
#[arg(long, default_value_t = 2_000_000)]
tasks: u64,
/// Iterations of arithmetic inside one task
#[arg(long, default_value_t = 20)]
weight: u64,
}
fn main() -> Result<()> {
let args = Args::parse();
println!(
"global queue: {} tasks of weight {} each\n",
args.tasks, args.weight
);
println!("workers time tasks/s speedup lock waits");
let mut baseline = 0.0;
for workers in [1, 2, 4, 8, 16] {
let result = run(workers, args.tasks, args.weight);
if workers == 1 {
baseline = result.throughput();
}
println!(
"{workers:>7} {:>7.0?} {:>7.2}M {:>6.2}x {:>10}",
result.elapsed,
result.throughput() / 1e6,
result.throughput() / baseline,
result.contended
);
}
Ok(())
}work-stealing/src/lib.rs — 86 lines
//! Scene 02: the same workload, one queue per worker.
//!
//! Each worker owns a deque and takes work from its own end — no
//! agreement with anyone needed. Only when a worker runs dry does it
//! touch someone else's queue, and then it takes half, so the next
//! famine is far away. Same tasks, same threads, same machine; the
//! only change is who has to agree with whom.
use global_queue::{Run, task};
use std::collections::VecDeque;
use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::{Arc, Mutex, PoisonError};
use std::time::Instant;
pub fn run(workers: usize, tasks: u64, weight: u64) -> Run {
// Tasks are dealt out to the local queues up front.
let queues: Vec<Arc<Mutex<VecDeque<u64>>>> = (0..workers)
.map(|worker| {
let share = (worker as u64..tasks)
.step_by(workers)
.collect::<VecDeque<u64>>();
Arc::new(Mutex::new(share))
})
.collect();
let steals = Arc::new(AtomicU64::new(0));
let sink = Arc::new(AtomicU64::new(0));
let started = Instant::now();
let mut handles = Vec::with_capacity(workers);
for me in 0..workers {
let (queues, steals, sink) = (queues.clone(), steals.clone(), sink.clone());
handles.push(std::thread::spawn(move || {
let mut local_sum = 0_u64;
// A cheap per-worker RNG picks victims; identical victim
// order in every worker would create convoys.
let mut state = 0x9E37_79B9_u64 ^ (me as u64 + 1);
loop {
let mine = queues[me]
.lock()
.unwrap_or_else(PoisonError::into_inner)
.pop_back();
if let Some(seed) = mine {
local_sum = local_sum.wrapping_add(task(weight, seed));
continue;
}
// Dry: take half of a random victim's queue.
let mut stolen = VecDeque::new();
for _ in 0..workers {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
let victim = (state as usize) % workers;
if victim == me {
continue;
}
let mut queue = queues[victim]
.lock()
.unwrap_or_else(PoisonError::into_inner);
let length = queue.len();
let half = length / 2;
if half > 0 {
stolen = queue.split_off(length - half);
steals.fetch_add(1, Ordering::Relaxed);
break;
}
}
if stolen.is_empty() {
break;
}
queues[me]
.lock()
.unwrap_or_else(PoisonError::into_inner)
.extend(stolen);
}
sink.fetch_add(local_sum, Ordering::Relaxed);
}));
}
for handle in handles {
let _ = handle.join();
}
Run {
elapsed: started.elapsed(),
tasks,
contended: steals.load(Ordering::Relaxed),
}
}work-stealing/src/main.rs — 40 lines
//! Scales the work-stealing scheduler across the same worker counts.
use anyhow::Result;
use clap::Parser;
use work_stealing::run;
/// Scale the local-queue scheduler across worker counts.
#[derive(Parser)]
struct Args {
/// Total tasks per run
#[arg(long, default_value_t = 2_000_000)]
tasks: u64,
/// Iterations of arithmetic inside one task
#[arg(long, default_value_t = 20)]
weight: u64,
}
fn main() -> Result<()> {
let args = Args::parse();
println!(
"local queues + stealing: {} tasks of weight {} each\n",
args.tasks, args.weight
);
println!("workers time tasks/s speedup steals");
let mut baseline = 0.0;
for workers in [1, 2, 4, 8, 16] {
let result = run(workers, args.tasks, args.weight);
if workers == 1 {
baseline = result.throughput();
}
println!(
"{workers:>7} {:>7.0?} {:>7.2}M {:>6.2}x {:>6}",
result.elapsed,
result.throughput() / 1e6,
result.throughput() / baseline,
result.contended
);
}
Ok(())
}scoreboard/src/main.rs — 37 lines
//! Scene 03: both schedulers, three worker counts, three task sizes.
//!
//! The last dimension is the honest one. Contention is not a property
//! of the design alone — it is the ratio between how long a task runs
//! and how long the queue is held. Large tasks hide a global mutex
//! completely; small ones expose it.
use anyhow::Result;
use clap::Parser;
/// Compare the two schedulers across worker counts and task sizes.
#[derive(Parser)]
struct Args {
/// Total tasks per run
#[arg(long, default_value_t = 2_000_000)]
tasks: u64,
}
fn main() -> Result<()> {
let args = Args::parse();
println!("tasks per run: {}\n", args.tasks);
println!("weight workers global q local+steal ratio");
for weight in [4, 20, 400] {
for workers in [1, 4, 16] {
let global = global_queue::run(workers, args.tasks, weight);
let stealing = work_stealing::run(workers, args.tasks, weight);
println!(
"{weight:>6} {workers:>7} {:>7.2}M {:>10.2}M {:>5.2}x",
global.throughput() / 1e6,
stealing.throughput() / 1e6,
stealing.throughput() / global.throughput()
);
}
println!();
}
Ok(())
}