Why 32 couriers beat one: understanding memory-level parallelism¶

Most of a bzip2 decode is one loop, the inverse Burrows–Wheeler transform's walk, and that loop spends most of its time waiting for memory. mibz2 doesn't make memory any faster. It keeps many of the walk's memory requests in flight at once, so the waits overlap. That is memory-level parallelism (MLP), and it is the library's basic premise.

This page explains it with couriers and a dispatcher, then gives the mechanism behind each part of the picture, and the measurements so far. How it works has the threads around the walk, and Prior work the work it builds on.

One courier, one chain¶

A motorcycle courier learns each delivery address only on arriving at the previous one: open the envelope, read the next address. The third destination can't be known before reaching the second. The bike is fast, but most of the time goes on waiting to find out where to go next.

That is the ordinary inverse BWT:

• The table. After Huffman decoding and move-to-front, a block's last column becomes the T-vector: one 32-bit entry a row, holding the row's byte (bits 0–7) and the next row (the bits above). A block holds up to 900,000 bytes, so the table is up to 3.6 MB, larger than most cores' L2 cache.
• The walk. Start at the block's primary index. Each step loads the current row's entry, writes its byte, and takes the next row from the same entry. The next row is anywhere in the table, so the load usually misses the cache.
• The wait. The step after can't start until that load returns, because its address is in the load's result. A chain of dependent loads keeps one miss in flight, and the core idles through each one.

The walk was measured as latency-bound directly, on the machine where mibz2's prototype was built: walking 1, 2, 4, 8 and 16 independent chains through one block, the cost fell from 28.5 to 4.4 cycles a byte of output (compute frontier, section 2). Memory bandwidth was nowhere near its limit. The walk was waiting, not moving data. libbzip2 and lbzip2 walk the one chain.

32 couriers, 32 independent journeys¶

Give each of 32 couriers a different delivery chain. While courier 1 waits for its next address, couriers 2, 3, 4… make progress. That is memory-level parallelism: the couriers don't travel faster, but there are enough independent journeys that waiting on one doesn't stop the rest. One courier is limited by the time it takes to get each new address; 32 keep many requests in flight.

Where the independent journeys come from¶

A block has one chain, not 32: the T-vector is a single cycle through every row (or, for a periodic text, a few). bzip2 carries no metadata to start a walk anywhere but the primary index. mibz2 makes the journeys itself:

• Random starts. 511 pseudo-random rows, plus the walk's own first row, become segment starts. A random row is a random position in the text, so the cycle is cut into 512 segments of about equal length. (Evenly spaced rows clustered in the text and stalled the lanes.)
• Flagged starts end a segment. Each start is flagged in bit 31 of its own T-vector entry, which links never use. A lane that reads a flagged entry has run into the next segment's start: its segment ends there, recording which start it ran into, and the lane takes the next unwalked segment.
• 32 lanes walk in lockstep. Each round, every lane takes one step, writing its byte into its own segment's buffer.
• The segments are stitched together afterwards. From the first row's segment, each segment is followed by the one it ran into, until the block's length is reached. The output is exactly the plain walk's, byte for byte, including a periodic block's several cycles. The flags are cleared before the walk returns.
• Short blocks walk plainly. Under 64 KiB, the segments' bookkeeping costs more than the waits it hides; only a stream's last block is ever that short.

Prefetching: phoning ahead¶

Lanes alone weren't enough. Without help, a lane's next load is issued only when its instructions enter the core's reorder buffer, which is full of the other lanes' steps. So the misses in flight were bounded by how many steps that window holds, and adding lanes didn't add misses.

mibz2 issues a software prefetch of each lane's next entry as soon as its row is known (prefetcht0 on x86-64, prfm pldl1keep on aarch64). A prefetch retires without waiting for its data, so every lane's miss starts at once. In the picture, the dispatcher phones each request through the moment an address is read, rather than when that courier's turn comes round on the board.

Try the counts yourself in this schematic. It has one dispatcher, whose paperwork for a step takes a tick or two, and each address takes 31 ticks to come back. The timings are made up for the picture.

The dispatcher becomes the bottleneck¶

There is only so much road, and one dispatcher. Add enough couriers and every wait is covered. Then the limit is the dispatcher: each step's paperwork, done for each courier in turn. Add more couriers past that point and the dispatcher spends more on coordination than the extra journeys earn.

In the core, the dispatcher's limits are these:

• Instructions a step. Every lane's step is a handful of instructions: the load, the flag test, the byte's store, the write pointer's advance, the buffer-end check, the prefetch. With the misses overlapped, the walk runs at the rate the core can issue those instructions.
• Register pressure. One lane's state (its row, its write pointers, its segment) fits in registers, but 32 lanes' state doesn't. It lives in the L1 cache, and every step loads and stores some of it.
• Cache contention. The lanes' table lines, the 512 segments' buffers and the lanes' own state share the same caches. At four threads, four walks share the L3.
• Outstanding misses. A core tracks only so many misses at once (its line fill buffers, and the L2's own queue). Beyond that, more lanes only queue.

The record shows both sides. Without the prefetch, 16 lanes were within noise of 12, and 24 or 32 were slower (PR #21). With it, 16 to 32 lanes were about 26–28% faster than 12 lanes without it, and within noise of each other at one walk. With four walks at once, 32 lanes won clearly. So mibz2 runs 32 lanes and 512 segments (the measured points).

It also explains why a cleverer-looking algorithm can lose. Once 32 misses are in flight, the walk is bound by instructions a step, not by the latency of each load. A change that saves steps but makes each one dearer loses. A change that keeps the steps and makes them cheaper wins.

Make the dispatcher efficient¶

Once there are enough couriers, cut the paperwork a step. That's how the walk got faster:

• The flagged walk (#12). It replaced the first segmented walk, which tested every step's row against a separate bitmap of the starts (12 lanes, 256 segments). The flag moved into the entry the step loads anyway, bytes went out through raw per-lane pointers instead of a growable vector's push, and the test for idle lanes left the hot loop.
• The prefetch, with 32 lanes and 512 segments (#21): every lane's next miss starts at once, as above.
• The shared-offset walk, after libsais's chain decode (#37, the default walk since 0.1.5). libsais 2.12's decode_chains runs room rounds of every chain at a shared output offset, where room is the fewest bytes any chain's buffer has spare. Within a pass, a lane's byte goes to its buffer's base plus the pass's offset, so the per-step pointer store and buffer-end test are gone. The lanes, the prefetch and the segments are unchanged, so the same misses are in flight. Only the instructions a step drop: one dispatcher's paperwork, done in batches.

Two cleverer-looking ideas from the literature were built, measured and dropped. Both changed the journeys themselves, and both lost to their extra cost a step:

• The pair walk, ψ² (#34, after libsais and Kärkkäinen, Kempa and Puglisi's super-alphabet). Each entry holds the row two steps on, so the walk takes half the steps, two bytes at each. But each step costs about twice as much: the second byte comes from a first-byte lookup. With the prefetch keeping 32 misses in flight, halving the dependent loads bought almost nothing, and the pair table took about three times as long to build. Envelopes holding two addresses mean fewer stops, but twice the paperwork at each, and the envelopes take three times as long to fill.
• Precopy (#36, after Kärkkäinen and Puglisi). Where a stretch of the walk repeats one already walked, its bytes are copied instead of walked. It copied 31.5% of the Wikidata blocks' bytes, and was slower all the same. The repeat check ran on every step, and the steps it skipped were the cheap ones, whose table lines were already in cache. The cost is in the scattered steps, which repeats never cover. A courier who checks the logbook for a repeated stretch at every stop loses more time than the short, nearby stretches it saves.

The measurements¶

The walk alone¶

Cycles a byte of output (c/B), the walk on its own, one thread:

The losing ideas, the walk alone on the shared machine: the pair walk's walk was about 10 c/B against the flagged walk's 10.4–10.8, but its build was 7.1–7.6 against 2.5 (pair walk journal); Precopy was 13.5 against 10.3 c/B on Wikidata, with 31.5% of the bytes copied (PR #36).

By lane count: the measured points¶

Only measured points are drawn, each chart on its own axes and naming its source: two sweeps so far, on different machines, corpora and walks, not to be read against each other. A finer sweep of lanes and prefetching is planned. Its points will go into assets/data/lane-sweeps.json, one panel a sweep, and appear here.

The whole decoder, on CI¶

The walk is about 53–60% of a decode, so a walk change moves the whole decoder by less. Whole-decoder figures come only from the CI benchmark: paired rounds of a pull request's head against its base on one runner (methodology). The walk's changes, on the Wikidata blocks (wall time, head over base, with its 95% interval; − is faster):

Each row is its own runner and its own base, so the rows don't add up. Master's figures over its commits are on the History page, and mibz2 beside the other bzip2 decoders on Alternatives.

The picture, term by term¶