The short leaf belongs at the bottom

Leaves cut to the edge on purpose built a recursive LU that cuts every dimension at a multiple of the cache’s edge — $\sqrt{M} - 2$ columns, the width a block size is a property of the machine found to be the cheapest leaf — so that every leaf is exactly the edge wide except one per dimension. On every size from 96 to 127 columns it moved 14 to 21 per cent fewer words between cache and memory than the pure recursion, where halving to the same base case was at the pure recursion’s traffic or a little above it on half the sizes. Its one weakness was the short leaf. A leftover of one column ends up as a one-column panel at the bottom of the recursion, and at 256 words the sizes with one column over — 99, 113 and 127 — moved 0.90 to 0.95 of the pure recursion’s words against 0.85 to 0.90 for sizes with none.

Its last section named two measurements. “Cutting it off first, at the top — an $x = r + bk$ split into r and bk, with the bk part cut into full leaves — would make it a thin strip of a large product instead. The prediction with a sign is that the one-column sizes at 256 words fall from 0.90–0.95 to the 0.85–0.90 of the full sizes.” And: “The aligned cut’s leaves are all the edge wide, so an edge overestimated by one puts every leaf on the cliff, where halving would put only its widest.”

Three cuts, one counter #

The setting is the earlier essays’. A recursive LU with partial pivoting over the full column, run against a counted memory: a single fully associative cache of M words with least-recently-used replacement, every word fetched from memory counted. The factorisation, the triangular solve and the product that updates the trailing matrix are each cut along their largest dimension until every dimension fits the base case, and then done by plain loops. The test matrix is diagonally dominant so that every ordering of the same elimination pivots identically, and on every run the multiply-adds are counted and the permutation compared: three cuts, the same arithmetic, the same pivots, different traffic — the situation the same arithmetic at a different price opened this line of argument with, between two orderings of one elimination.

The three cuts differ only in where a dimension of x columns is divided. Halving cuts at $\lfloor x/2 \rfloor$. Aligned, leftover last cuts at the multiple of the base case b nearest the middle, so that the remainder $x \bmod b$ ends up as the last leaf. Aligned, leftover first — the new one — cuts a dimension that is not a multiple of b into its remainder and the rest, so that the short piece is the first thing the recursion does and every later cut is between full leaves. At 256 words the edge is fourteen columns, and 99 columns cut leftover-first become one column and then seven leaves of fourteen.

The short leaf is cheaper at the bottom #

The figure at the top of the page is every size at 256 words. Moving the leftover to the front makes the cut worse on every size that has one — twenty-nine of the thirty-two — and identical on the three that do not, 98, 112 and 126, where both cuts are the same recursion. The one-column sizes, which the prediction was about, go the wrong way: 99 columns from 0.947 to 0.978 of the pure recursion’s words, 113 from 0.898 to 0.923, 127 from 0.902 to 0.924. At 144 words, where the edge is ten, the same holds on every size with a leftover, and the one-column sizes 101, 111 and 121 go from 0.856, 0.831 and 0.843 to 0.879, 0.853 and 0.857.

The difference is largest where the leftover is one column — up to 0.031 of the pure recursion’s traffic — and at 64, 144 and 256 words it is positive at every leftover, on all twenty-six to twenty-nine sizes that have one at each memory. In absolute words it is 3,237 at 99 columns and 256 words, 4,015 at 113, and 3,299 at 101 columns and 144 words: a third of the $n^2$ entries of the matrix, give or take. At 400 words the picture splits, and the next section is about why.

The reasoning behind the prediction was about shapes, and it got the shapes backwards. At the bottom of the recursion a one-column leftover is a panel, and a one-column panel is the pure recursion’s most expensive kernel — that much was right. But at the bottom it is small: by the time the last leaf is factorised the trailing matrix it touches is the leaf’s own height, and every update it received from the left arrived inside products whose inner dimension was a full leaf, which is where the aligned cut’s saving comes from. At the top, the one column is factorised first and then has to update everything to its right: a product of the whole trailing matrix with an inner dimension of one. That is the outer product, the shape in which every word fetched supports one multiply-add, and the strip makes it happen once over nearly the whole matrix. Moving the short piece up the recursion does not make it a cheaper shape. It makes it touch more.

The leaf that sits on the edge found the same economics in the width sweep: below the edge, narrower is dearer, because a narrow leaf reloads its operands more often per multiply-add. A leftover is a narrow leaf no rule can widen, and the measurement says to keep it where it reaches the least.

Where the rule turns over #

At 400 words the edge is eighteen columns, and a matrix of 96 to 127 columns is only five to seven leaves wide. Two things change there, and both say that the rule above is about matrices many leaves wide.

The first is that the aligned cut stops saving anything on the median size. Its words are 0.998 of the pure recursion’s at the median, against 0.799 at 64 words, 0.823 at 144 and 0.886 at 256, and on the smallest sizes — 96 to 103 columns — it moves more than the pure recursion, up to 1.131. Halving is at 1.002. The saving the aligned cut collects comes from products whose inner dimension is a full leaf, repeated across many leaves; with five leaves across, the first and last of them are a large share of the work, and the edge-width leaf’s advantage over the pure recursion’s own sequence of shapes has nowhere to accumulate.

The second is that the leftover’s best position depends on how short it is. At 400 words a leftover can be anything from one column to seventeen. The one- to four-column leftovers are still cheaper last: 109 columns, with one left over, moves 1.049 of the pure recursion’s words with the leftover last and 1.070 with it first, and 127 columns 1.024 against 1.055. But leftovers of five columns or more are cheaper first on most sizes — 96 columns, with six left over, 1.127 against 1.105 — and on twenty-three of the thirty sizes with a leftover the front is the cheaper place. A leftover that is a third of a leaf or more is not a narrow panel; it is a leaf of its own, and as the first piece of the recursion its update of the trailing matrix carries an inner dimension of six to sixteen, which is no longer the outer product that made a one-column strip expensive.

So the measured rule has a size on it. A leftover of a few columns belongs at the bottom at every memory measured, from 64 words to 400. A leftover of a third of a leaf or more, on a matrix only a few leaves wide, is slightly better at the top, by up to three hundredths. And on a matrix that few leaves wide, the aligned cut is not worth having in the first place.

The edge has no margin on one side #

The second measurement is the one a real code faces, because a real code does not know its edge to the column. The earlier essay’s caution was that the aligned cut makes every leaf the edge wide, so a base case one column too large puts every leaf on the cliff that the leaf that sits on the edge measured — one column wider than the edge costing two to three times the words.

The dial at 144 words shows the whole shape, and its other stops show how it moves with the memory. At the edge, ten columns, the aligned cut’s median size moves 0.823 of the pure recursion’s words. One column under, at nine, it moves 0.881; two under, 0.959; three under, 1.040 — the saving erodes by six to eight hundredths a column, and only at three columns short does the median size lose it entirely. One column over, at eleven, the median moves 2.478 times the pure recursion’s words, and two over 2.494. Every one of the thirty-two sizes is above two. At 256 words, where the edge is fourteen, the picture is the same with slightly different numbers: 0.974, 0.936, 0.903 and 0.886 from three under to the edge, then 2.876 and 3.001 one and two over.

So the aligned cut’s saving is a sharp minimum with a gentle slope on one side and a cliff on the other. A code that guesses its edge and is unsure by a column should guess low: being one column short costs it about six hundredths of the pure recursion’s traffic, being one column long costs it a factor of two and a half.

The other stops of the dial change both sides in opposite directions. At 64 words, where the edge is six, a column under the edge costs more — the median moves from 0.799 to 0.923, twelve hundredths, because one column is a sixth of a leaf — and a column over costs less, 1.791 times the pure recursion’s words. At 400 words, where the edge is eighteen, the median barely moves under the edge, since the cut was saving nothing there, and one column over costs 3.495 times. The cliff grows with the memory: 1.8 at 64 words, 2.5 at 144, 2.9 at 256, 3.5 at 400.

Halving was insurance #

Halving to the same base case barely notices a misjudged edge. At 144 words its median size is at 1.001 of the pure recursion’s traffic with the base case anywhere from two under the edge to two over, because its leaves on these sizes are six to eight columns wide whatever the base case between eight and twelve is: leaves cut to the edge on purpose found that halving cannot produce widths between its halvings, and the same fact that denies it the saving denies it the cliff. Only at two over, base case twelve, do some sizes halve to leaves past the edge, and its worst size reaches 2.552.

At 256 words the same thing happens one column sooner. One column past the edge, halving’s median size is unchanged at 0.917, and eight of the thirty-two sizes — 117 to 124 columns, whose halvings produce fifteen-column leaves — jump above one and a half times the pure recursion’s words, to 3.146 at the worst. The aligned cut puts every size there, at 2.63 to 3.17. Halving’s risk is the share of sizes whose halvings happen to land past the edge; the aligned cut’s is all of them.

That is the trade the earlier essay could only describe, now with numbers. At the edge the aligned cut saves 14 to 21 per cent on every size and halving saves it on a coincidence of sizes. One column past the edge the aligned cut loses a factor of two and a half on every size and halving loses it on a quarter of them. Which is the better recursion depends on how well the edge is known, and the answer is asymmetric: an edge known to within a column on the low side makes the aligned cut strictly better, and an edge that might be one too high makes it a gamble whose loss is ten times its win.

The figure also shows the one place the leftover-first cut does better than leftover-last: past the edge, by up to 0.37 of the pure recursion’s words on sizes with a leftover of several columns, and by nothing where there is none. With every full leaf on the cliff, the leftover is the one leaf off it, and where it goes then matters in the opposite direction; why is not measured here. The traffic is still more than twice the pure recursion’s at best, a smaller loss in a regime nobody should be in.

What this changes in the rule #

The rule the recursion that was never told the memory started from was that a recursion needs no block size, and the rule these essays have arrived at is that it does, and that the block size should be cut to on purpose. The two measurements here add a clause to each half of that.

The short leaf goes last. Of the two places one leaf per dimension can be short, the bottom of the recursion is cheaper, by up to three hundredths of the pure recursion’s traffic on one-column leftovers. The cut the earlier essay built was already the better one.

The edge is an upper bound, not a target. A base case at the edge is the cheapest; one under it is nearly as cheap; one over it is the most expensive thing measured in these essays. A code that estimates its edge from a cache size it reads from the hardware, where line size and associativity move the true edge by a constant a block size is a property of the machine did not measure, should round down and subtract one, and pay six hundredths for the safety.

What the counter does not see #

One idealised cache: fully associative, least recently used, a line of one word. A real cache’s lines and limited associativity shift the edge by a constant, and they also soften the cliff — a line of several words means a leaf one column too wide evicts a fraction of a leaf’s worth of lines rather than all of it — so the factor of two and a half one column over is the model’s and a real machine’s would be smaller, by an amount not measured here. One test matrix, diagonally dominant so that every cut pivots identically; a matrix that pivots would make the three cuts’ traffic differ by the swaps as well. And sizes from 96 to 127 only, one period of the pattern each memory produces.

Still open: a cut that knows its leftover, and a softer cliff #

A leftover folded into a full leaf. The leftover’s cost is its narrowness. A cut that absorbs a one-column leftover into its neighbour makes one leaf a column wider than the edge — one leaf on the cliff instead of a narrow one off it. The width sweep’s cliff is a factor of two for a leaf one column too wide, but one leaf of eight is an eighth of the traffic, and the prediction with a sign is that folding loses at 256 words and wins only where the leftover is one column and the leaf count is large.

The cliff with a line size. A cache that moves lines of eight words would let a leaf one column too wide keep most of its operands, and the cliff the aligned cut sits next to would be a slope. Whether the asymmetry above survives a line size — whether one column over is still ten times worse than one column under — is the measurement that would turn the rule “round down and subtract one” into a number for a real machine.