mibz2 · Research blog

Block dispatch in mibz2: mutexes, futexes and the scheduler¶

How mibz2's parallel decoder hands blocks to its workers, why some take up to a millisecond to be picked up, and how to tell lock contention from scheduling delay.

1 November 2026 · 12 min read · Investigation in progress

mibz2 has two very different kinds of parallelism:

1. Across blocks: different CPU cores decompress different bzip2 blocks at the same time.
2. Within a block: each worker follows 32 independent chains through the inverse BWT's table, to hide memory latency. The previous post is about that one.

This post is about the first kind: how work is handed to the workers, and an apparent delay in that handoff that may or may not be a real bottleneck. Finding out which takes a short tour of mutexes, futexes and the Linux scheduler.

1. The journey of a bzip2 block¶

A bzip2 block goes through several stages. In mibz2 they are split between two kinds of thread:

This split matters for everything below: a faster inverse BWT can't help if the scanner, or the handoff of jobs to workers, becomes the limit.

All seven threads (the feeder, the scanner, four workers and the reader) share the CPUs the operating system gives them. In the measurements below that is four physical cores, so there are moments when more threads could run than there are cores to run them.

2. Two waits in three lines of Rust¶

Here is how a worker gets its next job, from src/parallel.rs:

let job = {
    let rx = jobs.lock().unwrap_or_else(|e| e.into_inner());
    rx.recv()
};

jobs is a Mutex<Receiver<Job>>: one standard-library channel receiver, shared by all the workers behind a mutex. Two different waits can happen here:

1. Waiting for the mutex. Another worker holds it, so this one can't reach recv().
2. Waiting for a job. This worker holds the mutex, but the channel is empty, so recv() parks the thread until the scanner sends something.

The second wait happens while the mutex is held: the guard rx lives until the end of the block. That makes possible a situation that is easy to miss in the code:

None of this is incorrect. Every job is still taken exactly once, in order. The question is only whether it is slow.

What a futex is¶

When worker B "waits for the mutex", what actually happens? On Linux, Rust's standard Mutex is a single atomic word, with a futex ("fast userspace mutex") behind it.

A futex is the kernel's way of letting a thread sleep on an address until another thread says "wake up". Most lock operations never need it. The channel's recv() sleeps the same way: it parks the thread on a futex of its own.

3. Woken is not running¶

This is the distinction the whole investigation turns on. A thread can be in three states:

So when a job takes a long time to be claimed, there are at least three different explanations, each calling for a different response:

A simple application-level trace can't tell these apart. All three show up as "the job was enqueued at t₀ and claimed at t₁".

4. What the traces have shown so far¶

The decoder can record its own timeline: a mark at each step of each thread, with a nanosecond timestamp. On an i9-10900K, decoding a 207 MB slice of Wikidata at four workers, some jobs took nearly a millisecond to be claimed. That looked suspicious, until the delays were sorted by how busy the workers were when the job arrived:

Most of the slow claims are backlog. But a smaller set is more interesting: jobs that arrived with three workers decoding, no older job waiting, and one worker free. For those, the free worker's last recorded step tells us where it was:

When the free worker is already inside recv(), it claims the job in a median of 42 µs. When it is still trying to take the mutex, it takes ten times as long, and another worker claimed the job first in 89 of the 149 cases.

That gap could be mutex contention. But the kernel's own accounting of each thread's run-queue wait, read between decodes, points elsewhere: in the 120 gaps between decodes that contain such a JobLock case, 78% of the elapsed time was runnable but not running. The workers were awake and eligible to run, but weren't on a CPU. Across all the gaps between decodes, the figure is 34%.

That still doesn't make the delay waste. With seven threads on four cores, a runnable worker may simply be waiting while the scanner or another worker does useful work. The question is what the other CPUs were doing at that moment.

5. The reader has its own wait¶

When a worker finishes a block it doesn't write to the output. It publishes the block into a shared ready map keyed by its position, and the reader takes blocks strictly in order.

The scanner is held back by a bounded admission window: at most slots blocks may be between the scanner and the reader (eight at four workers). Before reading the next block, the scanner waits:

while !st.cancelled && st.issued - st.taken >= shared.slots {
    st = shared.cv.wait(st).unwrap_or_else(|e| e.into_inner());
}

That keeps memory bounded when one slow block holds up the reader.

The scanner and the reader share one condition variable, shared.cv, though they wait for different things: the scanner for a free slot, the reader for the next block in order. Workers call notify_all() when they publish a block, and the reader calls it when it takes one. That is correct, but every notification wakes both kinds of waiter, whether or not its own condition changed. Earlier measurements suggested the reader is sometimes late to take a block that is already ready. Whether notification, the lock or scheduling causes that is still open.

6. Measuring it without fooling ourselves¶

To separate the three explanations, the next experiment joins two views of the same run:

• The decoder's own marks, now at every boundary that matters: the attempt to take the receiver mutex, holding it, recv() returning, the guard's release, the decode, the publication, and the reader's waits and wake-ups. Each thread records into a fixed, preallocated buffer, with its operating-system thread id.
• The kernel's scheduler events, recorded with perf on the allocated CPUs: every wake-up, every switch of a CPU from one thread to another, and every futex wait with its address.

With both, every moment a worker spends not decoding while a job is available can be classified. Was it asleep while another worker owned the receiver? Asleep in the handoff, with the mutex free? Runnable but not running, and if so, what was occupying each CPU? Or publishing, or waiting on the shared lock?

Joining them needs care:

• Two clocks. The marks use Rust's Instant, and the kernel stamps its events with its own clock. The decoder reads CLOCK_MONOTONIC and immediately makes a recognisable system call, so the gap between the two clocks can be measured from the trace itself. On the preparation machine it is known to within 0.6 µs.
• The instrument changes what it measures. Each instrumented run is paired with an uninstrumented one. If tracing moves throughput or CPU time by more than 3%, the result is reported as provisional.
• The decision rules were written down before any data. An isolated multi-consumer queue experiment is justified only if receiver-specific obstruction is at least 5% of the workers' total time, in at least 80% of runs. Runnable time near the mutex is reported beside that, but never counted in it, because it may be ordinary competition for the cores.

When the instrument lies¶

The preparation runs turned up a lesson worth sharing. A review of the analysis asked a pointed question: could lost kernel events pass unnoticed? Checking it showed they could. perf script prints nothing about events it dropped unless asked with --show-lost-events. Events whose thread perf couldn't resolve were printed in a form the parser skipped.

The surprise came from the kernel itself. On the virtual machine used for preparation, the kernel emitted every switch into idle on three of its four CPUs, but never a switch out of idle. perf's raw dump and ftrace showed the same, so it isn't perf or the parser.

The effect was subtle and pointed in a dangerous direction. A worker switched in from idle appeared to be woken but never running, so its running time was classified as waiting for a CPU, which is exactly the "scheduling" explanation. In one run, 19 ms of the 77 ms counted as runnable was this artifact.

Now, the analysis:

• treats any interval the scheduler stream contradicts as unknown;
• requires every CPU's switches into and out of idle to pair up;
• runs a short probe before any capture, and refuses to start on a kernel that fails it.

A wrong answer delivered confidently would have been worse than no answer.

7. Two problems, one CPU¶

Even with perfect dispatch, four workers each decode less efficiently than one. On the i9, four workers spend about 30% more cycles per decoded byte than one worker, while executing almost the same instructions (1.3% more). The extra cycles go to stalls on memory: each worker's inverse-BWT table competes for the same 20 MB last-level cache, alongside the input, output and intermediate buffers.

These interact. Better dispatch keeps more inverse-BWT walks running at once, which raises the competition for cache and claws back part of its own gain. That is why every experiment is judged on the whole decoder's throughput and CPU-seconds per GB, never on one stage in isolation.

8. What happens next¶

The measurement comes next. It ends in one of two places:

• If receiver ownership really does keep free workers from available jobs, at least 5% of their time in at least 80% of runs, a multi-consumer queue becomes a justified, isolated experiment.
• If the receiver is usually free and the delay is scheduling or backlog, that hypothesis is retired, and the effort goes to the larger problem: the inverse BWT's memory behaviour.

This post is a snapshot of an investigation in progress, and its figures come from the traces available so far. A few lines of synchronisation code can decide how well a 32-lane, latency-hiding decoder uses a whole multicore CPU. Whether they do here is a question for the evidence.

Sources:

• the worker, scanner and reader loops: src/parallel.rs;
• the i9 traces and the cycle accounting: the resource attribution's analysis;
• the diagnostic's registered protocol: 2026-11-01-dispatch-causality-protocol.md;
• the trace-completeness checks: amendment 1.