Eight cells at once

The table stored the way it is filled measured what happens when an edit-distance table is stored by anti-diagonals rather than by rows. The anti-diagonal fill order keeps its 513 rounds and its miss rate falls from 31.1% to 8.7%; row order, on the same layout, becomes the order that strides.

Every fill on that page is a serial walk. The reason to want the anti-diagonal order at all is that the cells of one anti-diagonal depend on nothing but earlier diagonals, so they can all be computed at once — the order that has a depth is the argument that this is what a fill order’s depth means — and nothing there used it. This page computes a diagonal in steps of several cells and counts what a step costs.

The unit has to change with the question. A serial fill is measured in misses per cell, because the cells arrive one at a time and the cache decides. A step of eight cells fetches its operands together, so what matters is how many distinct lines it has to have in hand at once, and how that number grows as the step widens. A column computed in machine words is the same substitution made at the level below — a column of the same table computed as bit operations on whole words rather than as a loop over cells — and it changed the unit in the same way, from cells to words.

That is also why this page does not report a speed-up. Nothing here is timed, and a step of eight cells is one instruction on a machine with a vector unit and eight on a machine without; what a layout decides is the memory traffic a step needs, and the rest belongs to a machine.

What a step touches #

At a step of eight cells the two layouts differ by a factor of 1.9 — and both numbers are worth reading against the prediction that preceded them.

The row layout’s was right. A step of eight cells on eight consecutive anti-diagonal positions touches eight different rows, and a row is 513 cells, so the eight cells are in eight different lines and their neighbours above are in eight more. The prediction was “at least nine”; it is 10.87.

The diagonal layout’s was wrong. The prediction was three or four, on the reasoning that a step’s three read runs and its write run are each a contiguous stretch of eight cells and a line holds eight cells. The measurement is 5.71. A contiguous run of eight cells spans one line only when it starts at a multiple of eight, and there is nothing making it do so: each anti-diagonal begins wherever the previous one ended, and a step begins wherever the diagonal’s first cell puts it. A run of eight cells at an arbitrary offset spans two lines seven times in eight.

The alignment, which does not fix it #

If the residual is misalignment, aligning should remove it.

The third series on that plate is the same layout with every anti-diagonal padded to start at a multiple of the line size — at most seven wasted cells a diagonal, which on a 512 × 512 table is about 7,000 cells of waste against 263,000 of table, under three per cent. It takes a step of eight from 5.71 lines to 4.94.

That is a real improvement and it is not the predicted three or four. Aligning each diagonal’s start does not align each step: the first step of a diagonal begins at the diagonal’s first cell, and the cells of a diagonal that has been cut short by the table’s edge do not begin at index zero. So about a third of the steps still straddle. Getting to four would need the step boundaries aligned as well, which means padding each diagonal at both ends and accepting a step that computes cells the table does not have.

The number to carry is not 5.71 or 4.94 but the gap between them and the prediction: a run of cells is not a line, and the difference is where the run starts. That is the same kind of finding as the aligned bucket of eight entries, which was one cache line only because it was aligned to one.

Per cell, which is what a wider step is bought for #

A step of sixty-four cells touching twenty-four lines sounds worse than a step of eight touching six. Divided by the cells, it is not.

Two things are visible and the second is the one that decides the design.

At one cell a step the row layout is the cheaper of the two — 2.25 lines against 3.125. A single cell reads $(i-1, j-1)$ and $(i-1, j)$, which are adjacent in the row above, and $(i, j-1)$, which is adjacent to the cell itself: two lines, sometimes three. On the diagonal layout the same three reads sit on two different diagonals at unrelated offsets: three lines, always. So a serial fill, judged one cell at a time, prefers rows.

Both slopes can be read off the layout rather than fitted, which is the test of whether the count is understood. On the diagonal layout a step’s accesses are three runs, not four: the reads $(i-1, j)$ and $(i, j-1)$ are adjacent cells of diagonal $d-1$, so across a step of $w$ they merge into one run of $w+1$; the reads $(i-1, j-1)$ are a run of $w-1$ on diagonal $d-2$; and the writes are the step’s own run of $w$ on diagonal $d$. Three runs, each costing one line plus $w/8$ more, gives $3 + 3w/8$ — which is 6.0 at a step of eight against a measured 5.71, and 27 at sixty-four against 24.07.

On the row layout each cell of a step is in its own row and therefore its own line, and the cell above it is in another. Those upper cells are adjacent to each other, so consecutive step positions share the line above and the second line is amortised: about $1.1$ lines a cell, which is 10.8 at a step of eight against a measured 10.87.

And the two curves have different floors. The row layout’s flattens at about 1.27 lines a cell and cannot go below one, because each cell of a step is in its own row and therefore its own line. The diagonal layout’s keeps falling — 0.42 at a step of sixty-four and still descending — because a step’s cells share lines with each other, so a wider step amortises each line over more of them. The row layout’s cost per cell is bounded below by one line; the diagonal layout’s is bounded below by four over the step.

That is the whole case for the layout, stated in a way the serial fill could not state it. The earlier page justified the diagonal layout by a miss rate — 8.7% against 31.1% — which is a statement about one cache and one table size. The per-cell floor is a statement about the layouts.

The two plates together separate the two terms of the account. Halving the cells a line holds changes the diagonal layout’s step from 4.35 lines to 5.71 — almost exactly the $3w/8$ against $3w/16$ the three runs predict — and changes the row layout’s from 9.88 to 10.87, which is the constant and not the slope. A layout that reads runs is paid in line width; a layout that reads strides is not. The cliff where the data stops fitting measured the other boundary of the same model, where a working set crosses a cache; this is the boundary below it, where a run crosses a line.

The same at every size #

The prediction that this would hold “whatever the table size” is the part of it that was right, and it is right for a reason worth stating. A step’s lines are decided by where four short runs of cells fall relative to line boundaries, and that is a property of the runs and the line, not of how many other cells exist. The slow rise from 5.38 to 5.74 is the short diagonals near the table’s two corners, which are a smaller share of a larger table.

This is what makes the quantity worth measuring at all. A miss rate depends on the cache, the table and the fill order together, so it has to be re-measured for every case; a step’s line count is a property of the layout and the step, and the plate above is what “a property of” looks like when it is measured rather than claimed.

The measurement that measures nothing #

There is an obvious next plate and it is worth reporting that it is empty.

Running the whole fill through a cache and counting misses, at each step width, gives the same miss rate at every width: 9.40% through a cache of eight lines, 8.70% through sixty-four, 3.14% through 256 — identical to three decimal places from a step of one cell to a step of 256.

The reason is that grouping cells into steps does not reorder them. A step of eight cells computes the same eight cells in the same order as eight serial steps would; all that changes is that they are issued together. The cache sees one sequence of addresses either way, so it produces one answer. Anyone reaching for a cache simulation to price a vector width will get a flat line and should, and the flat line is not evidence that the width does not matter — it is evidence that the simulation was asked the wrong question.

What a step width changes is not the order of the accesses but the number of them that have to be outstanding at once. That is the quantity the plates above count, and it is the one with a limit in it.

How wide a step can be #

The question the earlier page asked was where a wider step stops paying: at some width, its runs no longer fit in the cache at once, and then a wider instruction fetches more lines per cell than a narrower one.

On the diagonal layout that width is far beyond any instruction’s. A step of sixty-four cells needs twenty-seven lines resident, which is under two kilobytes — a fraction of any first-level cache. A vector register holds eight or sixteen 32-bit lanes on current machines and sixty-four at the widest; at sixty-four lanes the operands are twenty-seven lines, and the step’s own working set is not the binding constraint on anything.

On the row layout it binds, and early. A step of sixty-four cells needs 129 lines — over eight kilobytes on a 64-byte line, which is a quarter of a typical first-level cache used by one instruction’s operands. At a step of thirty-two it is sixty-five lines. So the row layout has the limit the prediction described, and the diagonal layout, which the prediction was about, does not.

That inversion is the page’s other finding. The question was posed about the layout that turned out not to have the problem, because the layout that does have it is the one whose lines per cell never fell in the first place — and the two facts are the same fact. A layout whose step costs one line per cell will always need as many lines as the step has cells.

What this adds to the layout’s case #

The serial measurement and the step measurement agree about which layout to use and disagree about why, and both reasons are worth having.

The serial one says: on this cache, filling this table this way, the diagonal layout misses a third as often. It is a strong number and it is contingent on three things, any of which a different problem changes.

The step one says: a step of $w$ cells costs about $3 + 3w/8$ lines on the diagonal layout and about $2 + 1.1w$ on the row layout, at every table size, for reasons that are arithmetic about where runs of cells fall. It is a weaker claim about any particular machine and a stronger one about the layouts.

And there is a third thing the step measurement says that the serial one cannot. A serial fill on the diagonal layout reads 3.125 lines per cell against the row layout’s 2.25 — the diagonal layout is worse one cell at a time. The layout is not an improvement that also happens to allow a wide step; it is a bet on the wide step, and it loses without one. The earlier page’s 8.7% against 31.1% comes from reuse across many cells, which the serial walk gets for free; the per-cell line count is what one step sees, and it points the other way.

What is not measured here #

Lines, not instructions, and not time. A step of eight cells is one instruction on a machine with a vector unit and eight on a machine without, and nothing here counts either. The count is not the time applies with unusual force: the whole argument for a wide step is that the cells are independent, and independence is a property this model cannot see because it never charges for a dependence.

A step, not a schedule. Every step here runs to completion before the next begins, and the plates say nothing about how many could be in flight at once. A machine issues several instructions before the first has its operands, so the lines a sequence of steps needs resident is the quantity a real processor faces; where an algorithm looks is the argument that an access pattern is the thing to measure, and a pattern of overlapping steps is a different pattern from a sequence of separate ones.

Gathers are free here. A step on the row layout reads eight cells at a stride of 513, which a real machine does with a gather instruction that is several times slower than a contiguous load even when every line is resident. Counting lines charges the row layout for its lines and not for its gathers, so the factor of 1.9 at a step of eight is a lower bound on the difference.

One fully associative cache with LRU. The resident-set plate compares a step’s lines against a cache’s capacity and assumes a step’s operands can all be held. A set-associative cache can evict one of a step’s lines to make room for another, and a step whose runs land in the same set would thrash at a width far below the one counted here.

No edges. Every step is a full run of the stated width where the diagonal allows it and a short one where it does not, and the short steps at the table’s corners are counted as they fall. A real implementation would mask them, and masked lanes are fetched whether or not they are used.

Three cells read, one written. The table is an edit distance, so the recurrence has three inputs. A recurrence with more — an alignment with affine gaps, or an interval table whose cell reads every shorter diagonal, as a triangle stored in a square measured — has more runs a step must hold, and the counts here do not carry across to it.

One recurrence whose cells are independent along a diagonal. That independence is what a step is, and it is a property of the edit distance rather than of dynamic programming. The cost is the number of subproblems is the general statement of what a table costs; how many of those subproblems can be computed together is a separate question with a separate answer for every recurrence, and the anti-diagonal answer here is the easiest one there is.

Still open: the step that spans two diagonals #

Every step on this page is a run along one anti-diagonal, which is the largest set of cells with no dependence between them. It is not the largest set a step could usefully hold. The cells of diagonal $d$ and the cells of $d+1$ that depend only on cells already finished form a staircase two diagonals deep, and a step shaped like that would reuse the lines of diagonal $d$ immediately rather than after a whole diagonal’s worth of other work.

The measurement that follows builds a step of that shape — half of it on one diagonal and half on the next, offset by one — and asks whether the lines it holds at once fall below the $4 + w/2$ a single-diagonal step of the same size needs, since the two halves share their reads. The prediction from this page is that they do, by close to a factor of two at small widths and by little at large ones, and that the cost is a step whose two halves must be issued in order — which is a dependence, and therefore exactly the thing the anti-diagonal order was chosen to remove.