The table stored the way it is filled

The order with the best depth filled one edit-distance table three ways and found two counts pulling in opposite directions. Filled one anti-diagonal at a time, the table needs 513 rounds when every ready cell is computed at once, against 65,793 for row order, because the cells on an anti-diagonal do not depend on each other. Stored the ordinary way, row by row, the same anti-diagonal fill misses the cache on 31.1% of its reads, where row order misses 6.3%. The order that suits a machine doing many things at once was the worst order for the memory underneath it.

That essay traced the misses to the layout rather than to the order. On a row-major array, consecutive cells of an anti-diagonal are a whole row apart, so the order strides across memory and fetches a new line for almost every read. It predicted the repair without measuring it: store the table by anti-diagonals, so the order that walks diagonals walks memory sequentially, and the misses should fall to about row order’s rate while the rounds stay at 513. It also named two ways the repair could disappoint — the offset arithmetic of a diagonal layout, and row order, which on that layout should become the order that strides.

This page stores the table both ways, fills it in every order on both layouts, and replays each through the same caches. The repair works, and it stops short of row order by a margin that turns out to be exact.

Two ways to lay out one table #

The table has a cell $(i, j)$ for every pair of prefixes, $0 \le i, j \le 256$. Filling a cell reads three others — $(i-1, j-1)$, $(i-1, j)$ and $(i, j-1)$ — and writes itself. Every order on this page performs the same reads and writes; only the sequence and the addresses change.

Stored by rows, cell $(i, j)$ lives at offset $i \cdot 257 + j$, which is the default layout of a two-dimensional array.

Stored by diagonals, the cells are grouped by $d = i + j$. Diagonal 0 holds one cell, diagonal 1 holds two, diagonal 256 holds 257, and they shrink again to one at diagonal 512. The cells of each diagonal are stored contiguously in order of $i$, and diagonal $d$ starts where diagonal $d - 1$ ends. A cell’s offset is the start of its diagonal plus its position along it. Nothing else about the table changes: the same 66,049 cells hold the same values.

On that layout the three reads of cell $(i, j)$ fall in a particular place. $(i-1, j)$ and $(i, j-1)$ both lie on diagonal $d - 1$, next to each other. $(i-1, j-1)$ lies on diagonal $d - 2$. The write lands on diagonal $d$. When the anti-diagonal order moves to the next cell on the same diagonal, every one of those four addresses moves forward by one.

Six fills of one table #

The plate confirms both halves of the prediction. Stored by diagonals, the anti-diagonal order misses 8.7% of its reads, down from 31.1%, and its rounds are still 513. The trade the earlier essay found, depth bought with locality, is almost entirely gone.

And the same layout does to row order exactly what the row layout did to the anti-diagonal order. Stored by diagonals, row order misses 28.3%, because consecutive cells $(i, j)$ and $(i, j+1)$ lie on consecutive diagonals, and moving from one diagonal to the next jumps a whole diagonal’s length through memory. Column order, which strided on the row layout, strides on this one too, at the same 28.3%. Each layout has exactly one order that walks it sequentially, and every other order pays the stride.

That symmetry is the plate’s plainest lesson. Neither layout is local, and neither order is local. A pair is.

The rounds row is worth reading once more for what it does not show. A layout changes addresses, and depth is a property of which cells depend on which, so no layout can change it. The anti-diagonal order’s 513 rounds are the recurrence’s own longest chain, and they are available on either layout. What the diagonal layout adds is that the order can now be used without paying five times row order’s misses to use it.

Three streams against two #

The repaired rate is 8.7% and row order’s is 6.3%, and the difference is not an artefact of this cache. It has a count behind it.

Row order on rows touches memory in two streams. Its reads of $(i-1, j-1)$ and $(i-1, j)$ walk along the row above, one element per cell. Its read of $(i, j-1)$ and its write of $(i, j)$ walk along the current row, also one element per cell. A stream that advances one element per cell needs a new line every eight cells, so two streams need two lines every eight cells, against four accesses per cell — thirty-two accesses per eight cells. Two misses in thirty-two is 6.25%.

The anti-diagonal order on diagonals touches memory in three streams. It reads diagonal $d - 2$, reads diagonal $d - 1$ and writes diagonal $d$, and each advances one element per cell. Three lines every eight cells against thirty-two accesses is 9.375%.

The recurrence decides this. Row order finds all of a cell’s inputs in one earlier row. The anti-diagonal order finds them in two earlier diagonals, because the diagonal neighbour $(i-1, j-1)$ is two steps back along $d$. Whatever layout a fill order is given, its best possible miss rate is one line per stream per line’s worth of cells, and the number of streams is the number of earlier fronts the recurrence reaches back to, plus the front being written.

Halving the line size is a direct test, since the account predicts the rates double and keep their ratio. With four elements to a line, a stream needs a new line every four cells: two streams in sixteen accesses is 12.5%, and three in sixteen is 18.75%. The plate reports 12.5% and 18.5%. The ratio between the two layouts’ best orders stays at three to two, and the striding order on the wrong layout gets worse, 37.4%, because its strides now cross more boundaries.

How small a cache can be #

The stream count also predicts the smallest cache on which each pair reaches its floor, and the sweep across cache sizes shows it. A fill with $s$ streams needs a line for each, plus one more for the moment a stream straddles a boundary — a read at the last element of one line followed by a read at the first element of the next.

Row order, with two streams, reaches 6.3% with three lines and stays there; with two lines it misses 12.5%, twice its floor, as its two streams take turns evicting each other at boundaries. The anti-diagonal order on diagonals, with three streams, needs four lines. With three it misses 14.8%, and with two its streams have nowhere to live: 77.8% of its reads miss, far worse than either striding order. On a cache of two lines, the repaired fill is the worst fill on the plate.

That is a small but real price. On any real processor the first cache level holds hundreds of lines, and the difference between needing three and needing four never binds. It is still worth stating, because it is the same account seen from the other end: the diagonal layout makes the anti-diagonal order’s working set small, and small is three lines’ worth, not two.

At the top of the sweep something else appears. The row layout’s rates hold flat until the cache can hold two whole rows — 514 elements, 65 lines — and only the cache of 1,024 lines brings them down to the compulsory rate, about 3%. The diagonal layout’s anti-diagonal fill improves earlier, to 8.7% at 32 lines and 6.6% at 64. The reason is the shape of the table. Every row has 257 cells, but diagonals run from one cell to 257 and back, averaging about 129, so near the table’s corners three whole diagonals fit in a cache of 32 lines and the reads there are free. The row order’s working set is the same size everywhere; the diagonal order’s is small at the start and end of the fill and large in the middle.

Across sizes #

On small tables the repaired fill and row order are indistinguishable, 3.2% each at 32 and 64 characters, because the cache holds the whole working set of either and every miss is a first touch. As the table grows, row order steps to its two-stream floor first, at 128 characters, when two rows stop fitting; the diagonal fill follows more slowly, at 6.5% and then 8.7%, as fewer of its diagonals fit. The unrepaired anti-diagonal fill climbs away from both from the start. Extrapolated, the diagonal fill settles at 9.4% and row order at 6.3% on any table too large for its working set, which is the ratio the stream count gives.

What a vector instruction sees #

The anti-diagonal order matters because of the machines it serves. A vector instruction that computes eight cells at once, or a column computed in machine words, needs the cells it computes together to be independent, and the cells of one anti-diagonal are. The earlier essay measured the order’s depth as the promise and its misses as the cost of keeping the promise on a row-major array.

The diagonal layout changes what a round of eight cells costs. On the row layout, eight consecutive cells of an anti-diagonal lie in eight different rows and read from a ninth, and each row is 257 elements from the next, so their inputs and outputs sit on at least nine different lines, 256 elements apart — a vector instruction that reads them together is gathering from scattered memory. On the diagonal layout, the eight cells are eight adjacent elements of one diagonal, and their inputs are eight or nine adjacent elements of each of the two diagonals before it. One round reads a short run from each of two diagonals and writes a short run of a third: three runs, on three or four lines depending on where the boundaries fall. The cache model on this page counts the addresses of a serial walk, but the addresses are the same whichever way a round is computed, and on the diagonal layout they are contiguous in exactly the groups a vector instruction wants.

So the layout does more than recover row order’s locality for a serial fill. It is what makes the anti-diagonal order’s depth usable by the hardware that wants it. Implementations of alignment that compute along anti-diagonals with vector instructions keep each diagonal as its own contiguous array for this reason, and the plates here are the cache-level account of why that arrangement and not another.

What keeping only three diagonals costs #

A table stored by diagonals can also be kept partially, and the accounting is the same one. The table nobody has to keep showed that row order needs only two rows at a time when only the distance is wanted — 514 cells in memory instead of 66,049. The anti-diagonal order needs the two earlier diagonals and the current one: three diagonals of at most 257 cells, 771 cells at the widest point of the table, half as much again as row order’s two rows.

That is the three-to-two ratio again, appearing in memory rather than in misses, and for the same reason. The quantity that sets both is how many earlier fronts the recurrence reads. A recurrence that reads one front costs two streams and two fronts of memory; a recurrence that reads two costs three of each.

It also explains the result that seemed to contradict this one. A triangle stored in a square found that storing an interval table by diagonals was the worst of its layouts. An interval cell reads from every shorter diagonal, not from the two before it, so its number of fronts grows with the table, and no layout gives it a small number of streams. The diagonal layout helps the edit-distance recurrence because that recurrence reads two fronts back; it hurts the interval recurrence because that one reads all of them. Where an algorithm looks is this collection’s general form of that point: the access pattern belongs to the algorithm and the data together, and a layout chosen for one pattern is a stride for another.

The same decision elsewhere on the machine #

The result has a shape now met three times, and naming it is more useful than any one instance. A structure’s layout is a prediction of the order in which it will be read, and the layout is right exactly when the prediction is.

The bucket that fits a line is the same decision for a hash table. Cuckoo hashing’s two candidates were two single slots, which a lookup reads in an order no layout can make contiguous. Widening each candidate to a bucket laid out on one cache line made the lookup’s reads contiguous within each candidate, and the misses fell below linear probing’s at every load. The alignment was the whole of it: buckets of eight on lines of four lost the bound.

The layout that is told nothing is the same decision for a search tree, made without knowing the cache at all. A search reads a path from the root, and the van Emde Boas layout stores each small subtree of that path contiguously at every scale, so a path’s reads come in runs whatever the line size turns out to be. The diagonal layout here is simpler and less general — it is contiguous at one scale, the diagonal — but it answers the same question: which cells will be read one after another, and can they be stored one after another?

And a search with no branch to miss is the same decision aimed at a different part of the processor. There the rewrite made a search’s control flow predictable, at no change to its comparisons. Here the rewrite makes a fill’s memory traffic predictable, at no change to its cells or its depth. In each case the count the analysis uses is untouched, and the count the machine charges moves by a factor of three or more.

What the three have in common is that the right layout cannot be chosen from the structure alone. A table, a hash table and a tree each have many layouts that hold the same data. The one to use is set by the algorithm that will read it, which is why a library that fixes a layout before it knows the access pattern has already chosen which algorithms will run well on it.

What the measurement leaves out #

The offset arithmetic. A cell’s address on the row layout is a multiplication and an addition. On the diagonal layout it is the start of its diagonal plus a position that depends on whether the diagonal has passed the table’s longest one. A fill that walks diagonals need not compute that per cell: it keeps three base offsets, one per diagonal it touches, and adjusts them once per diagonal. Whether that bookkeeping costs anything measurable depends on a compiler, and the model here counts memory and not arithmetic.

Prefetching. A stride prefetcher detects a constant step and fetches ahead, and the row layout’s anti-diagonal order does stride by a constant within most of a diagonal. On a machine with a good one the unrepaired order’s 31.1% would be smaller, and the gap the layout closes would be smaller with it. The count is not the time is the reminder that these plates count fetches, and a fetch predicted in advance costs less than one that is not.

One cache level. The floors on this page — 6.3% and 9.4% — are the rates at whichever level of a real hierarchy first cannot hold the working set, and on a large table that is the first level. The cliff where the data stops fitting measures the step between those regimes, and the sweep across cache sizes here has two such steps per layout: one where the streams fit, and one where the fronts do.

Square tables. Both strings have the same length. For strings of very different lengths the diagonals are short and many, and the diagonal layout’s working set is smaller still, while row order’s is set by the longer string.

Still open: a round eight cells wide #

Every fill on this page is a serial walk, and the depth the diagonal layout makes affordable was never used. The measurement that follows computes each diagonal in steps of eight cells — the width of a common vector instruction — on both layouts, and counts the lines each step reads and writes rather than each cell. The prediction from this page is that a step on the diagonal layout touches three or four lines and a step on the row layout at least nine, whatever the table size. The question worth asking is what happens as the step widens to sixteen, thirty-two and beyond: at some width a step’s three contiguous runs no longer fit in the cache at once, and a wider instruction begins to fetch more lines per cell than a narrower one. Where that width falls is a property of the cache and the recurrence together, and it is the number an implementation choosing a vector width would want to know.