A triangle stored in a square

This ladder has now counted an interval table three ways. The cells are not the cost counted its transitions — every cell considers every split point of its range, so the cells are quadratic and the work is cubic. The argmin that cannot go backwards cut the transitions to quadratic for weights with a monotone property. The order that has a depth counted the rounds a fill needs if independent cells run at once, and found that the length-ordered fill an interval table is forced into is exactly its optimal depth.

Every one of those counts is independent of where the table is kept in memory. This page asks the question they leave out. The table’s cells have to be stored somewhere, in some order, and a cell’s work is a sequence of reads of other cells. How much the machine charges for those reads depends on how far apart they are in memory, and that depends on the layout.

Three ways to store a triangle #

An interval table over $n$ keys has a cell $(i, j)$ for every range $i \le j$, and no cell with $j < i$. Three layouts are natural.

A square array. Allocate an $(n+1) \times (n+1)$ array and use only the upper triangle. Cell $(i, j)$ lives at $i(n+1) + j$. Half the array is never touched, but addressing is a multiplication and an addition.

Packed rows. Store row $i$’s cells, $j$ from $i$ to $n$, one after another, with row $i+1$ immediately after. No slot is wasted — the triangle occupies $(n+1)(n+2)/2$ slots — and each row is contiguous, as it was in the square.

Packed diagonals. Store all cells of range length zero, then all of length one, then all of length two. This is the order an interval table is filled in — every cell of length $\ell$ depends only on shorter ones — so a fill that walks the diagonals writes its output in one sequential pass through memory.

The same table under packed diagonals numbers its cells very differently, and the difference is the whole of what the measurements below find.

Offsets run along each diagonal in turn, so the cells of one length sit together and a cell’s row-mates and column-mates are scattered across every shorter diagonal. Drawn as numbers, the two layouts already say where the reads will land: in the square, a split scan walks one run of adjacent offsets and one run nine apart; in the diagonal packing, both of its runs leap by a whole diagonal’s length at every step.

The fill needs to know one more thing to be priced: what a cell reads. Filling cell $(i, j)$ considers every split point $k$ and reads the two halves, $(i, k)$ and $(k+1, j)$. As $k$ runs from $i$ to $j-1$, the first half walks along row $i$ and the second half walks along column $j$. Every cell’s work is one sweep along its row and one along its column, interleaved.

The measurement #

The fill is the ordinary one for an optimal binary search tree over $n$ keys, and every read and write it makes is recorded as an address under a layout, then replayed through the cache model this field uses: fully associative, 32 lines of 8 elements each, least-recently-used. The counted quantity is the share of accesses that miss. The access sequence is identical under every layout — the same cells are read in the same order — and only the addresses differ, so any difference between layouts is a difference in locality and nothing else.

Two fill orders are measured. By length fills every diagonal in turn, which is the order the dependencies suggest. By rows fills row $n-1$, then $n-2$, and so on up to row 0, each row from left to right — which is also a valid order, since every cell a cell reads is either further right in its own row or in a row below, and both are already filled.

The first result is the one that looks paradoxical: storing the table in the order it is filled is the worst layout by a factor of two. Packed diagonals make every write sequential, and the fill makes far more reads than writes — each cell writes once and reads twice for every split point. A cell on diagonal $\ell$ reads $2\ell$ cells from every shorter diagonal, scattered across memory, and none of those reads is near the last.

The second is that packing the rows does almost nothing. It saves nearly half the table’s memory and misses 38.8% where the square misses 39.7%. The square’s wasted half is never read, so it never costs a miss; it only costs space.

The third is that the fill order matters a little and the layout matters a little, and neither gets far below 35%.

Why a row-major layout misses half its reads #

The reason every row-major layout stalls near the same rate is in the shape of a cell’s reads, and it is worth spelling out because it says what no layout can fix.

A cell’s split scan interleaves reads along its row with reads along its column. In a row-major layout — square or packed — the row reads are sequential: $(i, k)$ and $(i, k+1)$ are adjacent in memory, so after the first miss the rest of that stretch of the row is in cache. The column reads are not: $(k+1, j)$ and $(k+2, j)$ are in consecutive rows, a whole row length apart, and each one lands on a different cache line. So of every pair of reads the scan makes, one is cheap and one misses. As soon as the column is longer than the cache can hold in lines, the miss rate approaches one half.

That is a property of the recurrence, not of the layout. Any layout that keeps rows contiguous scatters columns, and any layout that keeps columns contiguous — storing by columns — scatters rows. Storing by diagonals scatters both, which is why it approaches one.

The geometry is general and it is worth naming. A table is two-dimensional and memory is one-dimensional, so every layout is a way of flattening a grid into a line, and every flattening keeps one direction of the grid contiguous at the price of spreading the other. A list and a block of memory found the same constraint for graphs, where no ordering of vertices can put every vertex next to all its neighbours. For a table whose recurrence reads along both directions at once, the price is paid on every cell, and it is paid at a rate that no choice of flattening avoids — only a change in which cells are read together can.

The sweep #

At sixteen keys the table has 153 cells and fits in the cache’s 256 elements, so every layout misses only on first touch, and the layouts are indistinguishable — a measurement at that size would conclude layout does not matter.

As the table grows past the cache, the row-major layouts climb towards one half and settle there, exactly as the account above predicts. Packed diagonals climb towards one and reach 92.6% at 128 keys. Filling by rows helps most in the middle of the range — at 32 keys it misses 5.4% where filling by length misses 15.5% — and the help disappears by 128 keys.

The middle of the range is where the row fill’s advantage comes from, and it is a working-set effect. Filling row by row from the bottom, a cell’s column reads go down into rows that were just filled, which are still in cache while the table is only a few cache-sizes large. Filling by length, a cell’s column reads reach rows filled at every earlier stage. Once the table is much larger than the cache, neither order keeps the recent rows in cache and both fall to the half-miss floor.

At 128 keys the bar plate makes the floor visible. The three row-major arrangements differ by one and a half points out of fifty; the choice between square and packed, and between the two fill orders, has become a detail. In absolute terms the half-miss floor at 128 keys is about 360,000 misses for one fill, and each of them is a fetch from a slower level of memory. The difference between the best and worst row-major arrangement is about eleven thousand of them, and the difference between keeping rows together and keeping diagonals together is about three hundred thousand — the whole of the cost the layout decides. What remains is the factor of nearly two between keeping rows together and keeping diagonals together.

The fill order and the layout separately #

The four-way plate separates the two choices cleanly. The fill order is worth about half the miss rate at mid sizes, whichever layout it runs on. Packing is worth a few more points at those sizes, because a packed row is shorter than a square row — it starts at the diagonal — so more rows fit in cache at once. Both advantages vanish at large sizes, where the column reads are too far apart for either to matter.

That is a small instance of the theme the order is the algorithm: two orders that compute the same table, both valid under the dependencies, both of the same depth in rounds, and one of them costs half the cache misses of the other on tables a few times larger than the cache. The same table, filled two ways measured that choice in operations; here it is measured in the currency the operations do not see.

A larger cache moves the floor and reorders the layouts #

With eight times the cache the half-miss floor is out of reach at every size measured, since a column of 128 rows fits in the cache’s lines. At 128 keys the table has outgrown even this cache, and the order of the layouts has changed: packed diagonals now miss less than the square array.

This is the result the page’s title could mislead about, and it needs stating plainly. “Storing by diagonals is the worst layout” is true in the regime where the table is much larger than the cache, and it is false in a regime where the cache holds several diagonals’ worth of cells. With a large cache, a cell’s reads from shorter diagonals mostly land on recently written diagonals still in cache, and writing each diagonal sequentially becomes a real advantage. A ranking of layouts is a statement about a ratio of table size to cache size, and the cliff where the data stops fitting is this collection’s account of why the ratio, not either number, is what a measurement should report.

The row fill on packed rows is the best arrangement in both regimes, which is the only layout recommendation the page can make without a cache size attached.

What packing buys, which is not misses #

If packing barely changes the miss rate, it is fair to ask why a table would ever be packed. The answer is on a different axis altogether, and the numbers are simple. At 128 keys the square array has $129^2 = 16{,}641$ slots and the packed triangle $129 \times 130 / 2 = 8{,}385$. Packing halves the memory, and the half it removes is never read.

Halving the memory matters at exactly one boundary: the one where the square does not fit and the triangle does. A table whose square is a little larger than main memory and whose triangle is a little smaller is the difference between a computation that pages to storage and one that does not — and the cliff where the data stops fitting measures how steep that difference is. Space is the other axis is the theme: packing is a space optimisation that happens to cost almost nothing in time, which is the best kind, and its value is invisible to any measurement of misses at a level where both versions fit.

It also has a price the plates do not charge. A packed layout’s address is a quadratic expression in the row index — $i(n+1) - i(i-1)/2 + (j-i)$ — where the square’s is a multiplication and an addition, and a fill that recomputes it for every read pays that arithmetic on every transition. Measured in a cell that has to know where it is, the cost is small against a cache miss and large against nothing, which is the right size for a tie-breaker.

What this changes about counting subproblems #

This ladder has insisted that the subproblem is the unit — the cost is the number of subproblems — and every count so far has been a count of cells or of transitions. The measurements here do not contradict that; they add a second unit on top of it. The transitions are the same in every layout and every order. The misses per transition vary by a factor of two between layouts in one regime and by a factor of ten between cache sizes.

Where an algorithm looks set out the general version for arrays: an access pattern’s cost is its locality, and two patterns with the same count can differ enormously in cost. An interval table is a clean case, because its access pattern is fixed by the recurrence — a row and a column per cell — and the only freedom is how those rows and columns are laid out in a one-dimensional memory. Any one-dimensional layout of a two-dimensional structure must separate one of its dimensions, and the recurrence reads both.

A cell that has to know where it is measured the addressing cost of a packed table — the arithmetic to find a cell in a layout with no multiplication-friendly structure — and found it small. This page’s results are the other half of that trade: packing’s saving is space, its addressing cost is small, and its effect on misses is a few points at most.

What the measurement leaves out #

One cache level with a small capacity. A real machine has several, and the half-miss floor at one level becomes a much lower rate at the next level up, where the whole table may fit. The results say which layout is better when the table exceeds a level, not what the total cost across levels is.

The inner loop’s arithmetic. A cell’s work is recorded as reads and one write; the comparisons and additions between them are not charged, which is this field’s convention for a cache measurement and understates how much of the time is not memory.

The monotone optimisation. The argmin that cannot go backwards cut each cell’s split scan to a short range, which shortens both the row and the column sweep and changes the access pattern entirely. Measuring the layouts under that fill is a separate measurement, and it is likely to change the regime boundaries, since the reads per cell fall from linear to nearly constant.

Where this ladder goes next: the table filled in tiles #

The half-miss floor is a consequence of reading a whole row and a whole column per cell while memory holds only a few lines. The standard way past that kind of floor is to change the order of the work rather than the layout of the data: fill the table in square tiles small enough that a tile’s rows and columns fit in cache, and within each tile touch only data the tile keeps close.

For an interval table that is not as simple as tiling a matrix product, because a cell reads cells from every shorter diagonal, not just from its tile. There are recursive fills that split the triangle into smaller triangles and a square, fill the square by combining the two triangles’ results, and recurse — and their access patterns are cache-oblivious in the sense the layout that is told nothing measured for search trees. The next rung measures such a fill on the same table, through the same two caches, and asks whether it gets below the half-miss floor without knowing the cache size — and what it costs in transitions to do so, since a fill order that reads more cells to read them more locally has to win back its own overhead first.