The split scan cut into blocks

A triangle stored in a square replayed an interval dynamic program through a small cache under every natural arrangement of its table and found a floor. Square array or packed rows, filled by length or by rows, every arrangement that keeps rows contiguous converged on half its reads missing once the table outgrew the cache, and storing the table by diagonals approached every read missing. The reason was in the recurrence. Filling cell $(i, j)$ considers every split point $k$ and reads $(i, k)$ and $(k+1, j)$, so each cell’s work is one sweep along its row interleaved with one sweep down its column, and a one-dimensional memory can keep only one of those contiguous.

That essay ended by naming the standard way past a floor of that kind, which is to change what work is done together rather than where the data is kept, and it posed two questions. Does a recursive fill that works in blocks get under the floor without being told the cache size? And what does it cost in transitions, since a fill that reads more cells in order to read them more locally has to win back its own overhead first?

This page builds two such fills and one alternative, and measures all of them against the arrangements already measured. The first recursive fill does nothing at all. The second goes under the floor by a factor of ten, at no cost in transitions.

The unit that every fill shares #

The fills on this page do not all make the same reads. One keeps two copies of the table and writes each cell twice; another updates a cell once for every split point it applies rather than once at the end. A share of accesses that miss would compare fills whose denominators differ, and a fill that makes more cheap accesses would look better for it.

What every fill does make is the same set of split point considerations. Each cell $(i, j)$ has $j - i$ of them, and the table over 128 keys has 357,760 in all, over 256 keys 2,829,056. A correct fill considers every one exactly once, whatever its order and whatever its storage, and every fill here is required to produce exactly that count. So the plates below report cache misses per split point considered. On the floor it is about one: each split reads one cheap cell along the row and one expensive cell down the column.

Whole cells in tiles #

The first recursive fill is the one the phrase “fill the table in tiles” suggests. It visits whole cells in a recursive order: a triangle of cells is its left half-triangle, its right half-triangle, and then the square of cells between them, and a square is its four quadrants, the one nearest the diagonal first. The order is valid — every cell comes after every cell it reads, which the fill checks — and it keeps neighbouring cells together at every scale.

It misses 1.007 times per split point, exactly as often as packed rows filled by rows.

The reason is that tiling moves the cells and leaves the work inside each cell alone. When cell $(i, j)$'s turn comes, it still scans all $j - i$ of its split points, reading its whole row from the diagonal to column $j$ and its whole column from row $i+1$ down to the diagonal. A cell near the top-right corner of the table has a scan as long as the table, and its column reads touch as many cache lines as there are rows in that column, however cleverly the cell was scheduled. The floor was never a property of the order in which cells are visited. It is a property of each visit.

Cutting the scan #

The second recursive fill applies the recurrence differently. Instead of computing a cell by scanning all its split points at once, it applies split points to cells in blocks, and a cell receives its split points over many separate steps.

The step it repeats has three ranges: a block of rows $R$, a block of split points $M$, and a block of columns $S$. For every $a$ in $R$, $m$ in $M$ and $b$ in $S$, it updates the cell for range $a$ to $b$ with the cost through split $m$. That reads a block of cells shaped $R \times M$ and a block shaped $M \times S$, and writes a block shaped $R \times S$ — three small rectangles of the table, provided every cell read is already final. When the three ranges are large, the step halves the largest and does the halves in turn.

Around that step sits a recursion that decides when inputs are final. A triangle of the table is filled by filling its two half-triangles, applying the one split point between them to the square of cells that spans both, and then finishing that square. A square whose two flanking triangles are finished is filled quadrant by quadrant: first the quadrant nearest the diagonal, then each of the others after the blocks of split points passing through already finished quadrants have been applied to it. Below a small base size, every part works directly.

The fill is longer to describe than to run, and three facts about it are checked every time it runs. It considers every split point of every cell exactly once — 357,760 at 128 keys. No cell is read before its last split point has been applied. And the table it produces equals the plain fill’s, cell for cell, on random costs. Nothing in it mentions a cache.

A tenth of a miss per split point #

The split fill misses 0.094 times per split point where the best cell-at-a-time arrangement misses 1.007 — ten and a half times fewer misses for the same split points, on the square array that missed half its reads when filled by length. It makes more accesses to get there, 1,073,280 against 723,776, because it writes a cell once for every split point it applies; measured as a share of accesses it misses 3.1%, which flatters it further. The fair comparison is the one on the plate.

The reason is the shape of the step. Once its three ranges are no more than about eight each, its three rectangles are eight short rows of eight cells, eight short rows of eight, and eight short rows of eight: at most twenty-four lines of a row-major array, and fewer where the rectangles overlap. That fits in a cache of 32 lines. A step of that size considers up to 512 split points, and after paying to bring its rectangles into cache it pays nothing for any of them. The recursion guarantees that all the work is eventually done in steps of that size, and in steps of every larger size too — which is why it needs no cache size to find the right one.

The second question from the earlier essay has a clean answer. The split fill considers exactly the split points the plain fill does, 357,760, and not one more. Its overhead is the extra writes and the bookkeeping of the recursion, neither of which is a transition, and on this cache it wins back both many times over.

Two copies #

The middle bar is the alternative that changes the data instead of the work. The floor came from reading a row and a column per split point in a memory that can keep only one of them contiguous. Keep the table twice — once stored by rows, once by columns — and read each half of the split from the copy in which it is contiguous. The first half walks along row $i$ of the first copy, the second walks down column $j$ of the second copy, and each cell is written into both.

Every split point then reads from two contiguous streams, and the plate shows what that buys: 0.151 misses per split point, seven times under the floor. What it costs is exactly what the layout says. The square array for 128 keys is 16,641 slots; two copies are 33,282, four times the packed triangle’s 8,385. And every write is two writes.

It is also a fix that only works for this shape of recurrence. The copies help because the recurrence reads exactly one row and exactly one column per cell. A recurrence that read along a third direction would need a third copy.

Across sizes #

At sixteen keys the whole table fits in the cache and the best arrangement is the simplest: packed rows miss 0.025 times per split point, the split fill 0.037, and two copies 0.116, because two copies are twice as many lines to touch for the first time. As the table grows past the cache, the cell-at-a-time fill climbs onto the floor and past it, 1.098 at 256 keys. Two copies stay between 0.15 and 0.21.

The split fill barely moves. It is 0.089 at 64 keys, 0.094 at 128 and 0.095 at 256 — flat, because the steps that do its work are the same size at every table size and the table’s size only changes how many of them there are. A fill whose cost per unit of work does not depend on the size of the table is the property the whole construction was for.

Without being told the cache #

The claim that a fill needs no cache size is a claim about every cache, and a sweep of cache sizes is the test. The split fill improves at every step: 0.449 misses per split point with 8 lines, 0.094 with 32, 0.026 with 128, 0.005 with 1,024. Each doubling of the cache lets larger steps fit, and larger steps amortise their loading over more split points. The fill was run identically at every size; only the cache changed.

The cell-at-a-time fill has a different shape. It sits on its floor until the cache holds a whole column of the table — 129 rows, 129 lines — and then drops steeply, from 0.712 at 64 lines to 0.163 at 128. It has one good regime and one bad one, and the boundary is set by the table.

Two copies are the most interesting line. They are nearly flat from 16 lines to 256, at about 0.14 to 0.24, because two streams need only a few lines and more cache does not shorten a stream. On the smallest cache they are the best fill on the plate: with 8 lines, two copies miss 0.287 per split point and the split fill 0.449, since a cache of 8 lines holds only the split fill’s smallest steps. By 16 lines the order has reversed, 0.200 against 0.236, and it stays reversed. A fill that is told nothing still has a smallest cache it suits, and here it is between 8 and 16 lines.

How small the base must be #

The recursion has one constant, the size below which it stops dividing and runs plain loops. Blocks of one and blocks of four miss 0.097 and 0.094 times per split point — the same, to within the noise of where boundaries fall. Blocks of sixteen miss twice as often, 0.186, and blocks of sixty-four 0.564, most of the way back to the floor.

The base is the one place the fill can be wrong about the cache. A direct step over sixty-four rows, sixty-four split points and sixty-four columns reads rectangles of sixty-four short rows each, which is sixty-four lines per rectangle against a cache of thirty-two, so inside that step the fill is a cell-at-a-time fill again. A base of sixteen reads rectangles of about thirty-two lines, and three of them do not fit. A base of four reads rectangles of four lines and fits any cache there is. The rule that follows is simple: the base must be smaller than the smallest cache the fill will ever meet, and a constant as small as four meets that for every real machine, while costing nothing measurable against a base of one.

The same idea for a tree, and a table #

The layout that is told nothing measured this idea for search trees. The van Emde Boas layout divides a tree recursively and stores each piece contiguously at every scale, so that whatever the block size, a search’s path crosses few blocks — and across seven block sizes it tracked the layout that had been told the size. The split fill is the same move made on the work instead of the data: it divides the computation recursively so that at every scale a piece of work touches a piece of memory no larger than itself.

That is the distinction the tiled cells missed. Where an algorithm looks set out that an access pattern is priced by its locality, and a pattern is a sequence of reads, not a sequence of cells. Tiling the cells rearranges which cell is computed next; cutting the scans rearranges which reads happen next. Only the second reaches the reads that were missing.

It also changes the account of what the table stored the way it is filled found for edit distance. There a layout fixed an order’s misses, because each cell read only two earlier fronts, and the right layout could make both contiguous. An interval cell reads every earlier front, no layout can make them all contiguous, and the repair has to come from the order of the reads instead. The two results mark the two sides of one boundary: a recurrence that reads a bounded number of fronts can be fixed by storage, and one whose reads grow with the table must be fixed by restructuring the work.

What cutting the scan does not combine with #

The argmin that cannot go backwards repaired the same scan in a different way, for weights with a monotone property: a cell’s best split lies between the best splits of two neighbouring cells, so the scan can be shortened to that range, and the total work falls from cubic to quadratic. That repair reads far less, and it would dominate every plate on this page if it applied.

As written, the two repairs do not stack. The shortened scan needs each cell’s neighbours finished before the cell starts, so that their best splits are known. The split fill applies a cell’s split points long before the cell is finished and often before its neighbours are, and it never knows a cell’s best split until its last block has been applied. A fill that keeps both properties would have to find the bounds some other way.

The same table, filled two ways measured two fills of one table that computed identical cells; the split fill is a third, and the first on this collection whose intermediate states are not cells at all but partial minima.

What the measurement leaves out #

The recursion’s own cost. Every call divides ranges and decides what to do next, and none of that is a read of the table. With a base of four the calls number far fewer than the split points, but they are not free, and a base of one would pay for a call per split point.

Writes as reads. The split fill updates a cell in place for every block of split points it applies, and each update is counted as one access to the cell. A running minimum kept in a register would save some of those writes and none of the reads.

One cache level and no prefetching. On a real hierarchy the split fill’s advantage should compound, since a fill whose cost falls at every cache size falls at every level. A prefetcher helps the cell-at-a-time fills’ streams and cannot predict a recursion. The cliff where the data stops fitting is the standing account of why the table-to-cache ratio, and not either number alone, is what these plates depend on.

Memory. The split fill needs the same table the plain fill does. Two copies double it. Neither can keep only a few fronts, as the table nobody has to keep did for edit distance, because an interval cell reads every shorter range.

Still open: blocks that know the monotone bound #

The repair this page could not stack is the one with the larger prize. The monotone property says a cell’s best split lies between its neighbours’ best splits, and those bounds are monotone across a whole block of cells. A block step that knew, for its rows and columns, the range of split points any of its cells could need, could skip the rest of $M$ — not per cell, but per block.

The measurement that follows asks whether such bounds can be computed from already finished corners of each block before the block’s split points are applied, how much of the split fill’s work they remove on weights that satisfy the property, and whether the result keeps the split fill’s flat cost per split point across cache sizes — or whether skipping work breaks the regularity that made the steps fit.