Leaves cut to the edge on purpose

The leaf that sits on the edge measured a recursive LU factorisation’s base case at every leaf width and found no trade inside the edge. On a matrix of $8w$ columns, which halves to leaves of exactly w, the words moved across a fast memory of M words fall as the leaf widens, reach their lowest at exactly $\sqrt{M} - 2$ columns — 0.81, 0.80 and 0.84 of the pure recursion’s traffic at 64, 144 and 256 words — and jump by a factor of two to three one column later. The cheapest leaf is the widest one that still fits.

The rule the essay drew from that was short: set the base case to $\sqrt{M} - 2$ 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 essay then noticed the flaw in its own rule. Most matrices do not have $8w$ columns. A matrix of 100 columns halves to 50, 25, 12 and 13, 6 and 7 — with a base case of 10 its leaves are six and seven columns wide, three or four short of the edge, and the leaves at the top of the band, which are the cheapest, never occur. Its last section proposed the fix: a recursion that cuts to the edge on purpose, so that every leaf is exactly the edge wide whatever n is.

This essay builds that recursion and measures it on every size from 96 to 127 columns. The fix works, the flaw was larger than the rule allowed for, and the one leaf the fix cannot make full turns out to have a price of its own.

Two ways to cut a dimension #

The recursive factorisation cuts three kinds of problem: the factorisation of a block of columns, the triangular solve with its left half, and the product that updates its right half. Each is cut along its largest dimension until every dimension fits the base case, and then done by plain loops. Everything about it — the counted memory, a single fully associative cache of M words with least-recently-used replacement, the pivot search over the full column, the test matrix — is the previous essays’. The only change is where a dimension of x columns is cut:

• halving cuts at $\lfloor x/2 \rfloor$, which is what every earlier measurement did;
• aligned cuts at the multiple of the base case b nearest the middle — at $b \lfloor \lceil x/b \rceil / 2 \rfloor$, or at b itself once x is at most $2b$ — so that every leaf is exactly b wide except one leftover per dimension.

On 100 columns with $b = 10$ the aligned cut goes 50 and 50, then 20 and 30, then 10, 10, 10 and 20, and ends in ten leaves of ten. Every product and every solve has the same set of multiply-adds in both versions, associated differently, and the permutation is the same, because by the time a column is searched it has received every update from its left in either order; both are checked on every run, and on every run both are equal.

Sixteen sizes past the pure recursion #

The curve the rule was read from dips to 0.80 at ten columns and sits at or above one for narrow leaves: 1.06 at six, 1.03 at seven, 0.95 at eight. A leaf of six or seven columns at 144 words is a leaf that costs the pure recursion’s traffic or a little more. That was known. What was not measured is how often a halving recursion lands there.

At 144 words — the dial’s middle stop — halving to a base case of ten moves more words than the pure recursion on every size from 96 to 111 columns: 1.03 at 96, up to 1.07 at 104, back to 1.003 at 111. On all sixteen of those sizes its leaves are six and seven columns wide. Only from 112, where the halvings begin to produce leaves of seven and eight, does it fall below one, and it reaches 0.91 at 127 columns. The aligned cut moves between 0.79 and 0.86 of the pure recursion’s words on every one of the thirty-two sizes, and is below halving on all of them.

At 64 words, where the edge is six, the picture is the same with the roles of the sizes shuffled. Halving lands exactly on the edge at 96 columns, which halves to leaves of six, and at 96 and 97 it is 0.02 better than the aligned cut; everywhere else its leaves run down to three columns — three to six up to 111, three and four from 112 — and from 107 to 114 it moves up to 1.03 times the pure recursion’s words. The aligned cut stays between 0.78 and 0.82 on every size. At 256 words, where the edge is fourteen, halving is good from 96 to 113 — its leaves there are twelve to fourteen wide, at or just under the edge — and bad from 114 on, where they fall to seven and eight: 1.02 to 1.08. The aligned cut is between 0.84 and 0.95.

The rule’s band was not at or below one #

The spread is the finding. Halving to the edge runs from 0.77 to 1.03 at 64 words, 0.91 to 1.07 at 144 and 0.83 to 1.08 at 256; the aligned cut runs from 0.78 to 0.82, 0.79 to 0.86 and 0.84 to 0.95. The median size is at the pure recursion’s traffic under halving at 64 and 144 words — 0.99 and 1.00 — and 0.92 at 256; under the aligned cut it is 0.80, 0.82 and 0.89.

So the rule “set the base case to the edge and let the halvings do the rest” is wrong in a specific way. The halvings do put every leaf between half the base case and the base case; it is the claim that everything in that band is at or below one that fails. The width sweep at 144 words is below one only from eight columns to ten — 0.95, 0.87, 0.80 — and at 1.05, 1.06 and 1.03 for leaves of five, six and seven: narrow leaves re-read their operands a little more often than single columns do. A halving recursion with a base case of ten spends every size from 96 to 127 in leaves of six to eight. A base case sets an upper bound on the leaf. It says nothing about the lower one, and the lower one is where the leaves fall on sixteen sizes of thirty-two.

The rule’s other half survives. Halving never goes past the edge, so it never falls off the cliff, and its worst case, 1.08, is the pure recursion’s traffic plus eight per cent — against the factor of two to three that one column too many costs. As the recursion that was never told the memory put it, a recursion is safe without the number; what the number buys is the saving, and halving does not reliably collect it.

Why no base case can repair halving #

It is tempting to rescue halving by choosing the base case per matrix rather than per machine: on 100 columns, pick whatever base case puts the leaves nearest the edge. The arithmetic of halving forbids it. The widths a halving recursion can produce from n columns are the numbers $\lfloor n/2^k \rfloor$ and $\lceil n/2^k \rceil$ for some depth k, and nothing in between. From 100 they are 50, 25, 12 and 13, 6 and 7, 3 and 4. Every base case from 7 to 11 gives the same leaves, six and seven columns, because there is no width between 7 and 12 for it to stop at. Twelve and thirteen are past an edge of ten, on the cliff. The base case is a choice of k; it cannot choose the width at depth k.

That is why halving’s good and bad sizes fall where they do. At 144 words the widths the halvings reach on 96 to 127 columns are six to eight, and eight is the best of them, two short of the edge; no size in the range halves to nine or ten, and no size in the range gets the saving. At 256 words the edge is fourteen, and 96 to 112 columns halve to twelve, thirteen and fourteen — within two of the edge — while from 113 upwards some or all of the leaves drop to seven and eight, because the next width up, fifteen, is past it. At 64 words the edge is six and only 96 halves to it exactly. The share of sizes on which halving collects the saving is the share of sizes whose halvings happen to land within a column or two of the edge, and it is set by where the edge sits relative to a power of two, which is a coincidence of the machine and the problem.

Cutting at multiples of the edge removes the coincidence. It is also the reason the operations do not change: any cut of a dimension into two pieces gives a valid recursive factorisation, because the recursion’s correctness never depended on the halves being equal — only its balance did, and a cut at a multiple of the edge is never further from the middle than one leaf. Its pivots are the pivots of the unblocked elimination for the same reason the swap that is not optional requires them to be: each column is searched after every update from its left has reached it, in whatever order those updates were grouped.

The leaf that cannot be full #

At 256 words the aligned cut has a wider band, 0.84 to 0.95, and on fifteen sizes halving beats it by up to 0.033. The reason is the one leaf per dimension that the aligned cut leaves over.

Cutting 99 columns into leaves of fourteen leaves seven full leaves and one of a single column. That one-column leaf is a panel of one column updating everything to its right with a triangular solve and a product whose inner dimension is one — the pure recursion’s most expensive shape, placed at the bottom of a recursion that is otherwise all full leaves. At 256 words the sizes with a remainder of one column, 99, 113 and 127, move 0.90 to 0.95 of the pure recursion’s words, the worst of the aligned cut; the sizes with a remainder of none, 98, 112 and 126, move 0.85 to 0.90. As the remainder grows towards a full leaf the cost falls, and at a remainder of twelve or thirteen it is back to 0.84 to 0.89. At 144 words the effect is weaker and has the same sign — the three largest values, 0.856, 0.855 and 0.850, are at remainders of one, two and three columns — and at 64 words, where the edge is only six, a leftover leaf is never far from a full one and the effect is lost in the spread.

The sizes where halving wins at 256 words are the sizes where its halvings produce twelve- to fourteen-column leaves by themselves, so that it is already on the edge and has no leftover leaf at all. It wins there by at most three hundredths. It is the only place it wins at 256 words, and at 144 words there is no such place.

Fewer calls as well as fewer words #

The width sweep found words and calls did not trade inside the edge, and the same holds here. The pure recursion makes between 581,542 and 1,350,874 calls; halving to a base case of ten makes 2,487 to 2,838; the aligned cut makes 648 to 1,433, in steps as n passes multiples of the edge. Full leaves are fewer leaves, and the aligned cut is the cheaper of the two in calls on every size at every memory. The same arithmetic at a different price showed two orderings of one elimination with identical operations and pivots and twice the traffic between them; this is a third ordering of the same kind, and in calls as well as words the cheapest of them.

What a recursive code should do with its base case, revised #

The previous essay’s rule, restated with what this measurement adds:

Know the edge, and cut to it. A base case of $\sqrt{M} - 2$ reached by halving collects the saving only on sizes whose halvings happen to land near the edge, and on most sizes it is the pure recursion’s traffic or slightly worse. Cutting every dimension at a multiple of the edge collects it on every size — 14 to 21 per cent at 144 words, 18 to 22 at 64 — and makes a third to a quarter of the calls.

Watch the leftover. The aligned cut’s one weakness is the one leaf per dimension that cannot be full, and a leftover of one or two columns costs up to five hundredths of the pure recursion’s traffic. The obvious repair — absorbing a small leftover into its neighbour, so that one leaf is a little wider than the edge rather than one leaf being very narrow — would put that leaf past the edge and on the cliff. The better one is to give the leftover a position in the recursion where it is not a panel: to cut it off at the top, where it is a thin slice of a large product, rather than at the bottom. Neither is measured here.

The cliff is still the thing to avoid. Everything above is a few tenths either way. One column too many is a factor of two to three. The block size a recursion still has found that on a machine with several caches the innermost decides; the aligned cut makes that decision exact, and it makes exactness more important, because a code that cuts every leaf to exactly the edge puts every leaf on the wrong side of it if the edge was misjudged by one.

That last point is the aligned cut’s real cost. Halving’s leaves are spread between half the base case and the base case, so an edge overestimated by one column pushes only the widest of them over. The aligned cut’s leaves are all the same width, so the same mistake pushes all of them over. The measurement here uses the exact edge of an idealised cache; a block size is a property of the machine is where that edge was found — $\sqrt{M} - 2$ exactly, where three lines of counting predicted $\sqrt{M/3}$ — and a real cache’s lines and associativity would move it by a constant nobody has measured here.

What the counter does not see #

One test matrix, diagonally dominant so 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, and both of which the aligned cut is more sensitive to than halving is, for the reason above. The claim is about this model.

The sizes run from 96 to 127, a factor of 1.3; the pattern of halving’s good and bad sizes repeats with every doubling of n, since it is set by where the halvings land relative to the edge, but only one period of it is measured at each memory. The leftover’s cost is read from thirty-two sizes at each memory, three to four per remainder, and the trend in the figure is clearer than any single point.

Still open: the leftover’s position, and an edge that is wrong by one #

Where the leftover goes. The aligned cut puts the one short leaf at the end of each dimension, where it becomes a narrow panel at the bottom of the recursion. 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. Whether that removes the remainder’s price, and whether it matters at 64 words where the price was never visible, is one more cut rule on the same counter. 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.

An edge misjudged by one. 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. Running both cut rules with a base case of $\sqrt{M} - 1$ — one column past — would put a number on how much of the aligned cut’s saving is insurance a code cannot afford to buy without knowing its cache exactly.

Recursive QR. The previous essay’s second open question stands, and it has a distributed relative: the message and the word found the method with the fewest communication rounds sending the most words — two costs that parted there, where here calls and words fall together. A recursive Householder QR cuts its columns the same way and carries a fourth operand, the triangular factor of the block reflector; whether its leaves want the same edge, and whether the aligned cut helps it in the same way, is the question doing it twice and a reduction that changes the order leave for the cache rather than the network.