The bound a block can and cannot have

The split scan cut into blocks found the way under the half-miss floor that every cell-at-a-time arrangement of an interval table stops at. Reordering whole cells does nothing — a cell still reads its whole row and column when its turn comes. Cutting each cell’s scan of split points into blocks, and applying a block of splits to a block of cells as a min-plus product, makes the same 357,760 splits at 0.094 misses each, flat across sizes and cache sizes, told nothing about either.

It ended on the repair it could not stack. Interval tables of the kind an optimal binary search tree produces satisfy the quadrangle inequality, and then Knuth’s condition holds: a cell’s best split lies between its two neighbours’,

$$k^*[i][j-1] \le k^*[i][j] \le k^*[i+1][j]$$

which turns the cubic fill into a quadratic one — the same collapse the cost is the number of subproblems describes from the other side, where the cells are the cost and the splits within a cell are what a bound can remove. Those bounds are monotone across a whole block of cells, so a block step that knew the range of split points any of its cells could need could skip the rest of the split range — not per cell, but per block.

This page asks the three questions that leaves: whether the bounds can be computed from cells the schedule has already finished, how much work they remove, and whether a fill that skips work keeps the flat cost per split that made the blocking worth having.

That flat cost per split is the property at risk. A fill that skips work applies fewer splits, and if the splits it skips are the cheap ones the cost per split rises — which is the third question below, and the one with the least obvious answer.

Which cells bound a block, and where they are #

The bound rises with both indices, so over a block of cells with rows $r_0 \ldots r_1$ and columns $s_0 \ldots s_1$ the smallest best split is the one at $[r_0][s_0]$ and the largest at $[r_1][s_1]$. Applying the condition to each:

$$k^*[r_0][s_0-1] \;\le\; k^*[\text{any cell of the block}] \;\le\; k^*[r_1+1][s_1]$$

Both of those cells lie outside the block: one column to its left, one row below it. That is the first thing worth knowing, and it is not obvious in advance — a bound computed from the block’s own corners would be worthless, because a block’s cells are exactly the cells the block is not finished with.

Whether the two neighbours are finished when the block runs is a property of the schedule, and the schedule was designed for locality with no thought for this.

The two sides are available about equally often, which is a small surprise: the upper bound’s cell is one row down — a shorter interval, which a fill by length would have finished long before — and the recursive schedule gives it no such priority. It finishes the near-diagonal quadrants of a square first, which helps, and then interleaves, which does not.

And the share falls as the table grows: both bounds on 52% of blocks at a table of 16 and 10% at 128. That is the right direction to expect and the wrong direction to want. A larger table has more blocks and a deeper recursion, so a block’s neighbours are more often in some other branch that has not run.

What the bound removes #

The block bound removes eleven per cent of the splits. The same condition applied a cell at a time removes ninety-five.

That is the answer, and the ratio between the two is the page. The gap is not a matter of tuning — no block size or base case closes a factor of twenty — and it comes from three compounding losses:

The cell-wise column is what the condition is famous for. 16,289 splits on a table of 128 against 357,760 is the collapse from cubic to quadratic, and it is the reason every textbook treatment of this recurrence mentions Knuth’s condition. The cells that were never worth having is the same kind of removal in a different table — work that a property of the weights proves unnecessary — and the arithmetic there is as favourable as it is here unfavourable.

A block is bounded by its extremes. A cell-wise bound restricts each cell to the interval between its own two neighbours, which on this data is a handful of split points. A block of cells is restricted to the union of its cells’ intervals, which spans from the first cell’s lower bound to the last cell’s upper bound. A block of 4 × 4 cells therefore admits every split point that any of its sixteen cells might want.

A block of splits is skipped or not, whole. The fill’s smallest unit is a block of split points, and it can be declined only if every split in it is outside the range. A block that half-overlaps the range is applied in full.

And the bounds are there for a tenth of the blocks. The previous plate.

The first of those three is the one that would survive any implementation, and it is worth a number. On a table of 128 the cell-wise bound leaves each cell an average of 16,289 / 8,256 ≈ 2.0 split points to try, out of an average of 43. A block of 4 × 4 cells covers sixteen cells whose best splits span a range of their own, and the union of sixteen intervals of width two, spread across four rows and four columns of the table, is wide enough that a block of four consecutive split points usually meets it. The bound is tight per cell and loose per block for the same reason it is a bound at all — it says the best split moves slowly, and a block is a place where it has had sixteen chances to move.

Multiply the three and eleven per cent is what is left. On a table of 128 it is 683 blocks skipped of 6,077, and 38,572 splits of 357,760.

The eleven per cent should be read against that plate rather than against the cell-wise column. A fill that removes a tenth of its arithmetic and keeps that curve is worth having; one that removes a tenth of its arithmetic and gives the curve back is not.

What eleven per cent of the work is worth #

The cost per split rises by twelve per cent at every cache size while the split count falls by eleven, and the two nearly cancel.

That is the answer to the third question and it is a clean no. Skipping work does break the regularity that made the steps fit, and it breaks it in a specific and predictable way: the splits a bound removes are the ones at the edges of a block’s range, and a block’s range is walked in order, so the skipped splits are the ones whose operands the previous block has just brought into the cache. What is left is the middle of each range, which is exactly as local as before but has lost the cheap ends.

So the bound buys arithmetic and does not buy transfers. The cells are not the cost is the standing form of that distinction on this collection, and this is an unusually clean instance: two fills, the same table, the same answer, a tenth fewer operations and half a per cent fewer transfers. On a machine where an addition and a comparison are free beside a cache miss — which is the machine this whole field’s model is about, and the machine the split scan cut into blocks was measuring for — the bound buys nothing at all.

The base case is where a compromise between the two would have to be made, and it is worth sweeping rather than assuming. On a table of 96 through a cache of sixty-four lines, the bound saves 7.0% of the splits at a base of two, 11.1% at four, 12.3% at eight and 8.1% at sixteen — a peak in the middle, because a smaller base makes the blocks too many for the bounds to be available and a larger one makes each block admit every split its cells might want. The share of blocks with both bounds rises monotonically with the base, from 6% to 35%, and the saving does not follow it.

Locality, meanwhile, is nearly flat over that whole range: 0.0490 misses per split at a base of one, 0.0494 at four, 0.0487 at sixteen, and 0.1801 at sixty-four. So the two are not in direct opposition along this dial after all — there is a setting that is best for the bound and costs the locality nothing, and it is a base of eight, and it saves 12.3% rather than 11%. A percentage point, for the one tuning parameter the fill has.

Why the two repairs want opposite orders #

The deeper reason they do not stack is worth stating, because it is a property of the two techniques rather than of this implementation.

The monotone bound wants the length order. It needs $[i][j-1]$ and $[i+1][j]$ finished before $[i][j]$ starts, and the fill by increasing length finishes every shorter interval before any longer one, so both are always there. That is why the cell-wise column on the first plate is quadratic.

The blocking wants any order but that one. The length order is precisely the order that gives the half-miss floor: each cell reads a whole row and a whole column, the rows and columns are long, and consecutive cells of one length share almost nothing. The blocked fill exists to visit the same splits in an order that reuses what it has fetched, and reuse means departing from length.

So the two are not merely awkward together; they are competing claims on the same degree of freedom, which is the order the splits are applied in. A fill can spend it on knowing which splits to skip or on knowing where the ones it applies will be, and this page measures what it gets for spending a tenth of it on the first.

The order that has a depth made the same observation in a third currency: an order is chosen for depth, or for locality, or now for what it lets a bound know, and no order is best at all three. What is new here is the arithmetic of the compromise — 11% against 95% — which says the compromise is not worth making.

What a reader should take from a tenth #

A tenth of the work is not nothing, and it is worth being careful about the conclusion, because “the two do not stack” is a stronger claim than the measurement makes.

They stack, and the product is not the sum. The blocked fill keeps its locality with the bound applied — the misses per split rise by a tenth and the misses fall — so there is no interference in the sense of one repair undoing the other. The disappointment is only that the bound, which is worth a factor of twenty-two on its own, is worth a tenth here.

And what the bound is worth is a property of the schedule, not of the bound. The cell-wise fill gets ninety-five per cent because it has both neighbours for every cell, every time. The blocked fill gets ten per cent because it has them for a tenth of its blocks and applies them to a block’s worth of cells at once. A schedule that finished a block’s bounding cells first would have the first of those and not the second, which is the measurement at the end of this page.

The honest comparison is against what each fill is for. A table small enough to sit in cache should be filled by length with the cell-wise bound: it is twenty-two times less arithmetic and the cache is not the constraint. A table too large for cache should be filled by blocks: the arithmetic is cheap and the transfers are not, and the cliff where the data stops fitting is where the answer changes. The two techniques belong to the two sides of that cliff, and this page is the measurement of how much of one survives a crossing to the other side.

What is not measured here #

One weight family. The weights are prefix sums of a positive sequence, which is the optimal binary search tree’s weight function and the case Knuth’s condition is stated for. A weight matrix that violated the quadrangle inequality would make the bound unsound, and the check that every fill produces the same table cell by cell is what would catch it — which is why the check compares values and not only counts.

One blocking scheme. The recursive fill is the one the earlier page measured, unchanged. A scheme designed with the bound in mind — one that finished a block’s two bounding neighbours first, deliberately — would raise the ten per cent, and would be a different fill whose locality is not the one measured here.

Blocks skipped, not narrowed. A block whose split range half-overlaps the bound is applied in full. Splitting such a block and skipping the half that is outside would remove more work at the cost of more, smaller blocks — which is the base case the fill already tunes for locality.

Splits counted, misses simulated. The split counts are exact; the misses are a fully associative LRU cache over the trace, as everywhere in this field, and a set-associative cache would treat the bounded and unbounded fills differently in a way this model cannot see.

No time. Eleven per cent fewer additions and comparisons is a real saving on a machine where they are not free, and nothing here is timed. The claim is that it buys no transfers, not that it buys nothing. The count is not the time is the standing caution and it cuts the other way here than usual: this page’s unit is transfers, and the quantity the bound moves is the one the unit ignores.

The bookkeeping is not charged. Deciding to skip a block costs two lookups of a best split and two comparisons; deciding not to costs the same. At 6,077 blocks that is twenty-four thousand operations against the 38,572 splits saved, which is the same order — so a fill that counted operations rather than splits would report a much smaller saving than eleven per cent.

One base case for the headline numbers. Blocks of four throughout except in the sweep above, which is the earlier page’s setting. The sweep says the best base for the bound is eight, and every other number on this page would be about a percentage point better there.

Still open: a fill that earns its bounds #

Every number on this page comes from applying a bound to a schedule that was built without it. The obvious repair is to build the schedule with it: before filling a block, fill the two cells that bound it — one to its left and one below — and only then apply the block’s splits. Each is a single cell and each costs its own scan, so the preparation is two cells’ work for a block of up to sixteen.

The measurement that follows implements that, and it has to answer a question the ordering makes awkward. The cell to a block’s left is itself in some other block, and filling it early means filling the splits it needs, which are in blocks of their own. So the repair either recurses — in which case it is a different fill and may be the length order in disguise — or it stops after one level and gets its bounding cells by a direct scan.

The second is measurable and is what follows: how much the two direct scans cost against the splits the resulting bound skips, whether the share of blocks with both bounds goes from ten per cent to all, and whether a fill that pays for its own bounds still reads 0.09 misses a split — since the two extra scans are exactly the long row-and-column reads the blocking was built to avoid.