The leaf that sits on the edge

The block size a recursion still has took the recursive elimination, sold as having no tuning parameter, and swept the width below which it switches to plain loops. The traffic was a staircase with its steps at the halvings of the matrix, and its cliff sat where the blocked elimination’s does: the first panel wider than $\sqrt{M} - 2$ moved 1.53 to 4.47 times the words. It then drew a conclusion about the choice. “The trade the recursion was supposed to escape comes back one level down — the processor wants wide leaves, the innermost cache wants narrow ones.”

Every measurement in that essay was on 96 columns, which is three times a power of two, so the only widths the halvings could produce were 3, 6, 12, 24 and 48. The edge $\sqrt{M} - 2$ is 6 at 64 words, 10 at 144 and 14 at 256, so at the two larger memories it fell between two measurable widths, and the width that matters most — the edge itself — was never measured. The same essay named the other gap: “a matrix of 100 columns halves to 50, 25, 12 and 13, 6 and 7, 3 and 4 — two widths at every level — and its staircase has intermediate steps.”

Both gaps close with the same instrument, and together they remove the trade.

Every width, built exactly #

A matrix of 8w columns halves three times to leaves of exactly w. Building one for every w from 3 to 16 measures the base case at every width, each against the same recursion on the same matrix split all the way to single columns. The machine model is the one these essays have used from the start: a fast memory of M words with least-recently-used replacement, and every word moved across its boundary counted. The matrices are diagonally dominant with random entries, and at every width the base case performs exactly the same operations and chooses exactly the same pivots as the pure recursion; only the order of the arithmetic changes.

At 144 words the curve is nearly flat from width 3 to width 7 — 1.00, 1.00, 1.05, 1.05, 1.03 — and then falls: 0.95 at 8, 0.87 at 9, 0.80 at 10. At 11 it is 2.45. The edge the preceding essay located between 6 and 12 is at 10 exactly, and the width on it is the cheapest the recursion has.

Turn the dial. At 64 words the lowest point is 0.81 at width 6 and the next width, 7, moves 1.77 times; at 256 words it is 0.84 at 14 and 3.15 at 15. At every memory measured, the edge is $\sqrt{M} - 2$ to the column, and the leaf that sits on it moves 16 to 20 per cent fewer words than the pure recursion.

No trade inside the edge #

Drawn against the distance from the edge, the three memories give the same shape: a plateau near one for narrow leaves, a descent to the lowest point at zero, and a cliff at one. The height of the cliff grows with the memory, 1.77, 2.45 and 3.15, because the words the recursion saves by fitting in a larger memory are the words it loses when it stops fitting.

So the preceding essay’s trade does not exist on the safe side. The cache does not want the narrowest leaves. It is indifferent to width up to about half the edge, and from there prefers wider leaves all the way to the edge; the processor prefers wider leaves everywhere, since each leaf is a call and a width-w leaf does $w^3$ of the arithmetic in one call. Both want the same leaf, the widest one that fits. The calls tell the other half of the story: the recursion on 80 columns split to single columns makes 335,606 calls, and with leaves of 10 it makes 356.

What the preceding essay measured was real and was read from the wrong side. On 96 columns at 144 words, the widths on offer were 6 and 12, one on each side of the edge. From 6 the only way wider was 12, over the cliff, and the rule “stay narrow” was the right rule among the widths 96 could produce. It was not a property of the cache. It was a property of the number 96.

The preceding essay’s own figure shows exactly the gap. Its points are at leaf widths 1, 2, 3, 6, 12 and 24, and the words jump from 1.03 at 6 to 2.55 at 12, with nothing between them. The widths 7 to 11, where the curve first rises by a few per cent, then falls to its lowest point at 10, then jumps, were not on offer. A staircase with its steps at the halvings of n is a curve sampled at the halvings of n, and on 96 columns those samples straddled the lowest point of the curve without landing on it.

Why the edge is the cheapest place #

The recursion’s pure form is cache-oblivious: it splits until the pieces fit, whatever the memory, and pays for the splitting in the traffic of the small products near the leaves, where each operand is re-read from slow memory more often than a fitted block would need. A base case replaces the bottom of that recursion with a single loop nest. If the nest’s three operands fit in fast memory together, it reads each once and saves every re-read the finer recursion would have made; if they do not fit, it re-reads them on every pass and loses more than it saved.

A block size is a property of the machine found where that fit ends for a blocked elimination: the best block is $\sqrt{M} - 2$, affine in the square root of the memory, not the $\sqrt{M/3}$ of the three-line count. The recursion’s leaf is the same loop nest with the same three operands, so it reaches its best at the same width for the same reason, and the saving is largest at the largest nest that still fits. The recursion finds the block size of the blocked elimination as its own best base case, which is a stronger statement than the preceding essay’s, that the two cliffs coincide: the two optima do too.

What the counting models would have chosen #

The three-line count of the earlier essays puts the best block at $\sqrt{M/3}$: 4.6 at 64 words, 6.9 at 144, 9.2 at 256. A base case set from it, rounded down as the model’s own rule rounds, would sit at widths where the curve is 1.02, 1.05 and 1.09 — no better than the pure recursion, and a quarter to a third worse than the leaf on the edge. A block size is a property of the machine found that count low by a factor of 1.56 for the blocked elimination’s best block and wrong in form, affine rather than proportional in $\sqrt{M}$; the recursion’s base case is where that error costs the most, because the whole of the base case’s benefit lies in the last few columns below the edge, and a model low by a third never reaches them.

That makes the measured rule more demanding than it looks. The difference between 0.80 and 1.05 at 144 words is the difference between a leaf of 10 and a leaf of 6 or 7 — a few columns — and the difference between 0.80 and 2.45 is one column. A code that wants the saving has to know its innermost cache to within a column, which is a harder requirement than the one the recursion was adopted to avoid, and it has to be right in the safe direction, because the penalty for being one column over is three times the saving for being exactly right.

The same factorisation at every width #

None of this changes the answer. The same arithmetic at a different price opened these measurements by finding that a blocked and an unblocked elimination return the same factorisation to the last bit, and the same holds here at every width: the operation count is identical to the pure recursion’s and the pivots are the same rows in the same order, which the measurement checks at every width before it counts a word. The base case is a choice about the order in which the same products are formed, and on a diagonally dominant matrix that order changes nothing a user of the factors could detect. What it changes is the number of words that crossed the boundary between the two memories, which is the whole of what these essays have been measuring.

A matrix that does not halve evenly #

Most matrices do not have 96 columns. A matrix of 100 halves to 50, then 25, then 12 and 13, then 6, 6, 6 and 7 — two widths at every level after the second — and a base case of 12 produces leaves of 6, 7 and 12, because 25 splits into 12, which is kept, and 13, which is split again.

On 96 columns at 144 words the staircase goes from 1.03 with leaves of 6 to 2.55 with leaves of 12, in one step. On 100 it has a step in between. Leaves of 6 and 7 move 1.05 times the pure recursion’s words; leaves of 6, 7 and 12, with 48 per cent of the columns in the 12-wide leaves past the edge, move 1.33; leaves of 12 and 13, all past the edge, move 2.57. The uneven halving gives the cliff a ledge a third of the way up.

That is a warning a code could use, where the evenly halving matrix gave none. It also means that on a matrix like 100 the base case has a second safe setting the evenly halving matrix lacks: leaves of 6 and 7, which a base of 7 to 11 produces, cost 1.05 at 144 words, and the next setting up costs 1.33 rather than 2.57 — so a code that overshoots the edge by a little on such a matrix pays a third, not two and a half times. A base case that puts some of its leaves past the edge costs something but not everything, and the size of the ledge says how many.

The ledge, on eight sizes #

On eight sizes from 96 to 124 columns in steps of four, every base case falls into one of three groups. With every leaf inside the edge the words are between 0.93 and 1.07 of the pure recursion’s. With every leaf past it, between 2.46 and 2.62. Four base cases mix the two, on 100, 108, 116 and 124 columns, each with about 48 per cent of its columns past the edge. Three of those land on the ledge, at 1.31 to 1.42. The fourth, on 124 columns with leaves of 8 and 15, lands at 2.20, most of the way over.

The share of columns is therefore not the whole story. The leaves of 15 on 124 columns are further past the edge than the leaves of 12, 13 and 14 on the other three, and a leaf further past the edge re-reads more per operation; the cliff has a slope on its far side that the share cannot see. What the eight sizes do establish is that a matrix which halves unevenly usually meets the edge in two steps, and that the evenly halving 96 — the matrix every earlier measurement used — is the one shape that cannot.

What a recursive code should do with its base case #

The rule the measurements support is short, and it has a cost the pure recursion did not: a number to know. The whole case for a recursive elimination was that it needed none, and it still performs within about a quarter of the best tuned block without one. What the width sweep adds is that the one number it can use, if a code has it, buys more than the preceding essay allowed — a saving over the pure recursion rather than a limit on a penalty.

Set the base case to $\sqrt{M} - 2$ for the innermost cache that matters, and let the halvings put the leaves at or below it. A recursion that halves always produces leaves between half the base case and the base case, so a base of exactly the edge gives leaves in the band where the curve is at or below one, and the ones at the top of the band are the cheapest. The recursion that was never told the memory found the pure recursion within 0.94 to 1.28 times the best tuned block without knowing the memory; told it once, as a base case, it moves fewer words than the pure recursion and makes a few hundred calls instead of hundreds of thousands.

On a machine with several caches the base case can be right for one, and the block size a recursion still has showed the innermost decides, since a leaf past its edge falls off its cliff whatever the outer caches can hold. That conclusion stands. What changes is the reading of it: the base case sized for the innermost cache is not a concession to it, paid for in calls. It is the best leaf that cache allows, and on a single level it is the best leaf there is.

What this does not settle #

One test matrix, diagonally dominant so that the pivots are the same in every ordering, and one model of memory: a single fully associative cache with least-recently-used replacement and no line size. A real cache moves lines of several words and has limited associativity, both of which shift the edge by a constant; the claim that the cheapest leaf sits exactly on the edge is a claim about this model.

Each width is measured on its own matrix of 8w columns, so the ratios at different widths compare different matrices with the same recursion. The ratio is taken against the pure recursion on the same matrix in each case, which is what makes them comparable; the absolute words are not.

The fourth mixed case, on 124 columns, is not explained by the share of columns past the edge. The width of the over-wide leaves is the obvious second variable, and a sweep that held the share fixed while varying how far past the edge the leaves sit would separate the two.

Still open: splitting to the edge, and the panel #

A recursion that splits to the edge on purpose. A halving recursion can only offer the widths its halvings produce, and on most n those do not include $\sqrt{M} - 2$ exactly. A recursion that split off a leading piece of exactly the edge’s width at the bottom level, and halved everything above it, would put every leaf on the edge for any n. Whether that recovers the full 16 to 20 per cent on sizes like 100, and what it does to the uneven ledge, is one sweep with the same counter.

Recursive QR. Householder QR has a recursive formulation with the same halving of columns, accumulating a compact representation of the reflections at each level. Doing it twice and a reduction that changes the order measured QR’s traffic between processors; between caches, whether its base case sits on the same $\sqrt{M} - 2$ when the leaf is a block reflector rather than an elimination — whose loop nest carries a fourth operand, the triangular factor of the reflections — is the question this measurement makes precise.

The panel. Every measurement here uses partial pivoting on a full column at every step, which the base case does not touch. On a matrix much taller than it is wide the panel dominates the traffic, and the base case chosen for the square part of the recursion is not the one the panel wants. The swap that is not optional is where that search is measured, and a recursion whose base case is right for the square part and wrong for the panel is the next thing the counter should see.