The order with the best depth

The order that has a depth counted three numbers for one edit-distance table: the cells it holds, the transitions it considers, and the depth of the order it is filled in — the number of rounds needed if every cell whose inputs are ready is computed at once. Row order and column order have a depth equal to the number of cells, since every cell depends on the one before it in the order. The anti-diagonal order has a depth equal to the number of anti-diagonals, about the sum of the two strings’ lengths, because every cell on an anti-diagonal depends only on the two anti-diagonals before it.

That makes the anti-diagonal order the natural one for any machine that does several things at once. A column computed in machine words computed a whole column of a table in a few word operations, which is one way of doing a round in parallel; a vector instruction that computes eight cells at once is another; a graphics processor computing a thousand is a third. All of them want an order in which many cells are ready together, and the anti-diagonal order is the one with the most.

This page measures what that order costs on the machine a table usually lives on — a sequential processor with a cache — when the table is stored in the ordinary way.

The table and the three orders #

The table is the edit distance between two strings of $n$ characters each, stored as an $(n+1) \times (n+1)$ array in row-major order — row 0 first, then row 1 — which is how a two-dimensional array is laid out by default in most languages and how every table on this site has been stored. Cell $(i, j)$ lives at offset $i(n+1) + j$.

Filling a cell reads three cells — the one above, the one to the left, the one diagonally above-left — and writes one. Every order fills the same cells with the same values and makes the same reads; only the sequence differs.

• Row order fills row 1 left to right, then row 2. Each cell reads the cell just written, to its left, and two cells in the row above, one of which the previous cell also read.
• Column order fills column 1 top to bottom, then column 2. Each cell reads the cell just written, above it — which in a row-major array is a whole row away — and two cells in the previous column.
• Anti-diagonal order fills every cell with $i + j = 2$, then every cell with $i + j = 3$. Consecutive cells on an anti-diagonal are at $(i, j)$ and $(i+1, j-1)$, which in a row-major array are $n$ offsets apart.

Every read and write is replayed through the cache model this field uses: fully associative, 32 lines of 8 elements, least-recently-used eviction. The two quantities reported are the order’s depth and the share of its reads that miss.

Two hundred and fifty-six characters #

The two sets of bars run in opposite directions. The anti-diagonal order needs 128 times fewer rounds than row order and misses five times as often. Column order combines the worst of both: the depth of row order and nearly the misses of the anti-diagonal.

The row order’s low rate has a precise explanation. Each cell makes four accesses — three reads and a write — and they come in two streams, one along the current row and one along the row above, both advancing by one element per cell. A stream advancing one element at a time needs a new line only once every eight elements, so the two streams together fetch about two lines per eight cells, against thirty-two accesses in those cells: one miss in sixteen accesses, which is the 6.3% on the plate. Two rows of 257 elements is 514 elements against a cache of 256, so the rows do not fit entirely, but the part of each row the order is working on always does.

The anti-diagonal order has no stream. Each cell is $n$ offsets from the previous cell on its anti-diagonal — a whole row minus one — so every cell is on a different cache line from the last, and its three reads are on the lines of the previous two anti-diagonals’ cells in neighbouring rows. An anti-diagonal of 257 cells touches 257 different rows and nearly as many cache lines; the cache holds 32. So almost every read of the previous anti-diagonal has been evicted by the time it is needed.

It helps to follow one cell. Filling $(100, 157)$ on anti-diagonal 257 reads $(99, 157)$ and $(100, 156)$ from anti-diagonal 256 and $(99, 156)$ from 255. Those cells were written about 257 and 513 fills earlier, when the order last passed through rows 99 and 100 — and in the meantime it has written one cell in every other row of the table, each on its own cache line, while the cache holds 32 lines. The reads are neighbours in the table and far apart in the order of access, and the order of access is the only distance a cache measures.

Column order is the anti-diagonal’s problem in one direction: the cell above is a row away, so the stream down a column strides by a row per cell, and only the reads of the previous column’s neighbouring cells benefit from anything.

When the table is small #

On a small table the anti-diagonal order does better, and the reason is the size of its working set. An anti-diagonal of 33 cells spans 33 rows, which is 33 cache lines’ worth of neighbourhood in a cache of 32. That almost fits, so many reads of the previous anti-diagonal find their line still present, and the miss rate is 12.4% rather than 31%.

Column order does not improve at all — 28.9% here, 28.2% at 256 characters — because its penalty is per cell, not per diagonal: every read of the cell above strides a row, regardless of how large the table is, as soon as a row is longer than a cache line.

The sweep #

The sweep separates the two kinds of penalty cleanly. Column order’s miss rate is a constant — about 28% — at every size, because it is caused by a stride of one row per cell, and every row here is longer than a cache line. The anti-diagonal order’s miss rate climbs from 12% towards the same constant, because its stride is also one row per cell but its working set, an anti-diagonal’s worth of rows, fits in the cache on small tables and not on large ones. Row order stays low throughout, stepping from 3% to 6% where two whole rows stop fitting in the cache.

The asymptote is the same for both striding orders, and it is the signature of an access pattern that has lost all locality in one dimension and kept it in the other: every read in the striding direction misses, every read in the contiguous direction does not.

The depth side of the trade is the one the order that has a depth established, drawn on the same sizes so the two plates can be read together. Depth grows as the square of the length for the orders that walk rows or columns and linearly for the one that walks diagonals. The anti-diagonal order’s advantage in depth grows without limit; its disadvantage in misses is bounded, at about five to one against row order.

So the two counts disagree about which order is best, and they disagree for a structural reason rather than an accidental one. Two counts disagree is this collection’s theme for pairs of measurements that rank the same algorithms in opposite orders, and this pair is exact: the property that makes an order good for depth — cells that do not depend on each other are processed together — is the property that scatters them across a row-major array, since independent cells of an edit-distance table are exactly the cells in different rows and different columns.

A cache large enough for an anti-diagonal #

With a cache of 1,024 lines — 8,192 elements, enough to hold the neighbourhood of every cell on two consecutive anti-diagonals — all three orders miss about three per cent, which is roughly the compulsory rate: the first touch of every line. The anti-diagonal order’s penalty was entirely a working-set penalty, and a cache that holds its working set removes it.

That is the machine-independent way to state the result. Each order has a working set, and an order is cheap on any cache that holds it. Row order’s working set is two rows. Column order’s is two columns, which in a row-major array is two whole rows’ worth of lines touched per column of cells. The anti-diagonal order’s is two anti-diagonals, spread across every row of the table. On a cache smaller than a working set the order pays a miss per read in the direction that does not fit; on a larger one it pays nothing. The cliff where the data stops fitting measures that step for a single array, and here there are three steps at three different sizes, one per order.

The fix is to store the table the way it is filled #

The working-set account says what to do about the anti-diagonal order’s misses, and it is not to change the order. It is to change the layout.

If the table is stored by anti-diagonals — all cells with $i + j = 2$ in one run of memory, then all with $i + j = 3$ — then the anti-diagonal order walks memory sequentially, and each cell’s three reads are in the two runs immediately before the current one. The working set becomes two anti-diagonals of memory, contiguous, and the order’s misses fall to a streaming rate while its depth is untouched. Vectorised implementations of alignment that work along anti-diagonals keep each anti-diagonal in its own contiguous array for exactly this reason: a vector instruction wants the eight or sixteen cells it computes together to be adjacent in memory, and adjacent in the order they are read.

It is worth setting that beside a triangle stored in a square, which found storing an interval table by diagonals to be the worst layout on a small cache. The two results do not conflict; they are about two recurrences. An edit-distance cell reads only from the two diagonals before its own, so diagonal storage keeps its reads together. An interval cell reads from every shorter diagonal, so diagonal storage scatters them. Whether a layout is local is a property of the layout and the recurrence together, and nothing about the word “diagonal” settles it.

Why this is a machine result and not a table result #

Everything on this page is invisible to the counts this site uses for tables. The cells, the transitions and the values are identical in every order; the depth differs, and that was already measured; and the misses differ by a factor of five on one cache and not at all on another.

In absolute terms the difference is large. At 256 characters each order makes about a quarter of a million reads and writes, so the gap between 6.3% and 31.1% is roughly sixty thousand extra fetches from a slower level of memory for one fill of one table — work that no count of cells or transitions records, and that a timing would attribute to the algorithm rather than to the order it happened to be written in.

The count is not the time is the general statement, and where insertion sort actually wins is its most familiar instance: two algorithms whose comparison counts rank one way and whose memory traffic ranks the other, with the crossover set by the cache. Here the ranking inverts between two quantities that are both about the order — depth for a parallel machine and misses for a sequential one — and the order a table is filled in turns out to encode an assumption about which kind of machine it will run on.

That assumption is rarely stated because on a sequential processor with a large cache it does not matter: the last plate shows three orders within a tenth of a per cent of each other.

There is a well-known version of this trade that runs through the whole of the machine field, and a search with no branch to miss is its cleanest statement on this site: a binary search rewritten to do the same comparisons in a form a processor can predict does no less work and takes much less time. The anti-diagonal order is the same kind of rewrite aimed at a different part of the processor — at its ability to do several things at once rather than at its branch predictor — and like the branchless search, whether it pays depends entirely on which part of the machine is the bottleneck. Two searches, one comparison count measured two searches whose counts agreed and whose times did not; the three orders here are three fills whose counts agree, whose depths do not, and whose times depend on which of those the machine cares about. It matters on a machine with a small, fast cache relative to the table, which is the situation of every table longer than a few thousand characters on the fastest level of a real cache hierarchy.

What the measurement leaves out #

One cache level. A real processor has several, and a table whose anti-diagonal working set overflows the first level may fit comfortably in the second. The miss rates here are for a single level of 256 elements and should be read as the rate at whichever level the working set first overflows.

No prefetching. A hardware prefetcher detects strides and fetches ahead, and a constant stride of $n$ elements — which the anti-diagonal order has — is exactly what a stride prefetcher detects. On a machine with one the anti-diagonal order’s penalty would be smaller; on a machine without one it is what the plates show.

Serial execution. The anti-diagonal order is measured as a serial walk, which is what it is on one core. Its depth advantage is realised only by a machine that computes a round at once, and on such a machine the misses per round, not per cell, are the relevant cost.

Only the edit-distance recurrence. Its three reads are all within one row and one column of the cell being filled, which is the most local recurrence a two-dimensional table has. A triangle stored in a square measured a recurrence whose reads span a whole row and column per cell, and there every row-major layout converges on half its reads missing regardless of the order. The ranking of orders on this page is a ranking for local recurrences, and it should not be carried to a recurrence whose reads are not local.

Where this ladder goes next: the table stored the way it is filled #

The section above predicted a layout from the working-set account and did not measure it.

The measurement is direct. Store the edit-distance table by anti-diagonals, compute each cell’s offset from its diagonal and its position along it, and replay the anti-diagonal order’s reads through the same caches. The prediction is that its misses fall to about the row order’s rate while its depth stays at 513, which would remove the trade on this page entirely. Two costs could spoil it: the offset arithmetic, which is no longer a multiplication and an addition, and the row order, which on a diagonal layout becomes the striding order and should now be the one that misses. If both predictions hold, the layout and the order are one decision rather than two, and the right statement of the result is that a table should be stored in the order its fastest target machine fills it.