The block size a recursion still has

The recursion that was never told the memory measured a recursive LU factorisation against the best blocked elimination a scan could tune, on a counted memory, and found it within 10 to 28 per cent at six memories of eight and ahead at the other two, without reading the memory’s size. Its recursion halved all the way down: the only base case of the whole factorisation was a panel of one column, and the triangular solves and the updates split until they were single multiply-adds.

That essay ended on a caveat it did not measure. No recursive code halves to one entry. The overhead of a call — entering a function, working out which half is which, returning — is free on a counted memory and not free on a processor, and so every implementation switches to plain loops below some width. The caveat said that the switch “is a block size again, chosen for the processor’s arithmetic rather than its cache”. The measurement here is whether the second half of that sentence is true. It is not: the switch is chosen for arithmetic and it lands on the cache, with the cliff and the rule the blocked elimination has.

The figure at the head of the page is the whole finding on one memory. Every other figure asks where it comes from and whether it survives a machine with more than one cache.

A parameter the recursion rounds #

A base case of b columns means: when a panel is at most b columns wide, factor it by the ordinary right-looking loop — search each column for its pivot, swap whole rows, scale, update the rest of the panel — and when a triangular solve or an update has every dimension at most b, do it by three nested loops. Wider problems split in half as before. The panel’s loop updates only the panel’s own columns, and everything to its right is left to the recursive solve and update exactly as at a base of one, so each column is still searched only after every update from its left has reached it. The pivots are therefore the unblocked elimination’s, and they are checked rather than argued: at every base case measured the permutation is identical, the operation count is the same 585,200 multiply-adds and divisions as an integer, and the residual is 2.9·10⁻¹⁶.

What changes is the width of the panels the recursion actually factors, and that is not b. A matrix of 96 columns halves to 48, 24, 12, 6, 3, and then to panels of 1 and 2. A base case stops the halving at the first width that fits it, so every base from 3 to 5 produces panels of 3, every base from 6 to 11 panels of 6, and every base from 12 to 23 panels of 12. The recursion rounds its one parameter to a halving of n. Bases that round to the same panels move exactly the same number of words — not approximately; the counts are integers and they are equal — and the curve in the figure at the head is a staircase with its risers at 3, 6, 12 and 24.

That rounding is a property worth having. A base case set anywhere between 6 and 11 is the same program as far as the memory can tell, so a library that gets its base case wrong by a factor of less than two has not got it wrong at all.

What the switch buys #

The reason to switch is in the call count, and the call count is enormous. Halving to single entries, the recursion makes 581,542 calls on a 96-by-96 matrix, nearly one call for every one of its 585,200 operations, since most of the calls end in a single multiply-add. Panels of 3 cut that to 23,562, twenty-five times fewer. Panels of 6 cut it to 2,932, two hundred times fewer, and panels of 12 to 356, sixteen hundred times fewer.

None of that appears in the words moved, because the model counts words and not calls. It is the one cost the model sets aside, and it is real: each of those calls is an entry and a return and a handful of index calculations, which on hardware can outweigh a single multiply-add many times over. So the pressure from the processor runs one way, towards a large base case, and it is steep — every doubling of the panel width divides the calls by about eight, 23,562 to 2,932 to 356 to 42, which is what an update whose leaves number (n/b)³ should do.

If the switch were only about overhead, the right base case would be as large as the recursion’s advantage allows, which is to say as large as possible. The next figure is why it is not.

And what it costs: a cliff at $\sqrt{M} - 2$ #

On 144 words of fast memory the pure recursion moves 126,742 words, 1.16 times the best blocked elimination’s 109,202 at a block of 10. A base case up to 10 columns — panels of 3 or 6 — moves at most 130,739, three per cent more. A base case of 12 moves 323,422: 2.55 times the pure recursion, and 2.96 times the tuned block. One halving separates a base case that costs three per cent from one that costs a factor of two and a half.

The edge sits between 10 and 12, and the number to set beside it is the one a block size is a property of the machine measured for the blocked elimination: its best block is exactly $\sqrt{M} - 2$, which at 144 words is 10, and a block one column wider than the best sits on the far side of a cliff. The recursion’s panels meet the same cliff at the same place.

Across six memories from 36 to 576 words the rule holds without exception. Measured against the pure recursion on the same memory, every base case whose panels are no wider than $\sqrt{M} - 2$ moves at most 1.16 times the words, and the first panel width past $\sqrt{M} - 2$ moves 1.53, 1.71, 2.22, 3.18, 4.00 and 4.47 times as many on memories of 36, 64, 100, 256, 400 and 576 words. The three-line model the earlier essay started from, $\sqrt{M/3}$, would put the edge below panels that measure safe on 64, 100 and 256 words — at 4.6 against a safe panel of 6, 5.8 against 6, and 9.2 against 12 — which is the same factor by which that model was found to be low for the block itself.

The 64-word memory has a surprise in it. There $\sqrt{M} - 2$ is exactly 6, a halving of 96, and a base case of 6 lands the recursion’s panels on the edge from the safe side. The traffic falls to 0.77 times the pure recursion’s — below the best tuned block’s 158,119 words, at about 155,700. A recursion with its base case set by the blocked rule beats the blocked elimination tuned by that rule, because it has the block’s efficiency at the leaves and the recursion’s safety above them.

The 576-word memory has the opposite lesson. The pure recursion was already ahead of the tuned block there, at 0.94, and panels of 12 — safely under the edge of 22 — cost it 16 per cent, which spends that lead and more. Panels of 24 move 4.47 times as many words. So “at most 1.16 on the safe side” is a real cost at some memories rather than a rounding: the safe side of the cliff is not free, it is only not catastrophic.

Why the blocked rule: a leaf is a block #

The rule transfers because the object is the same. Below its base case the recursion is the blocked elimination’s kernel: a panel of w columns factored in place, a w-by-w triangular solve done by loops, a w-by-w-by-w product done by loops. Its working set is a few tiles of width w plus the column being searched, and whether that fits the fast memory is the question the scan over block sizes answered, with the answer $\sqrt{M} - 2$. Above the base case, the recursion never has more than one leaf’s worth of data in its hands at once, so nothing it does above the leaves can rescue a leaf that does not fit.

That is also why the rounding matters in both directions. It protects a base case from small errors, and it cannot protect it from a large one: the step from 6 to 12 is a doubling, and on a memory whose edge sits between them the doubling carries the recursion over the cliff in one move, with no intermediate width to warn anyone. The same arithmetic at a different price found that every ordering of these operations is the same factorisation to the last bit; this is the sharpest case of it, since two base cases that differ by one column can be the same program or a program moving three times the words, and the arithmetic cannot tell which.

On three caches, the innermost decides #

The recursion’s case for having no block size was strongest on a machine with several caches, where no single block can be right for all of them. A base case is a single block. So the question on such a machine is which cache it has to be right for.

On caches of 36, 256 and 1,024 words, panels of 3 leave all three boundaries where the pure recursion put them: 1.211, 1.099 and 0.928 times each boundary’s best block, against 1.215, 1.097 and 0.928. Panels of 6 go over the inner cache’s edge — $\sqrt{36} - 2$ is 4 — and the inner boundary jumps to 1.861 while the middle moves to 1.153 and the outer does not move. Panels of 12 are safe for the middle cache and better than the pure recursion there, 1.017 against 1.097, while the inner boundary stays at 1.663. Panels of 24 go over the middle cache’s edge as well, and every boundary is at more than 1.3.

So the base case, like a block, can be right for one cache at a time, and the only choice that costs nothing anywhere is the one sized for the innermost. That is the smallest cache, which means the smallest panels and the most calls: on this machine, panels of 3 and 23,562 calls rather than panels of 12 and 356. The trade the recursion was supposed to escape comes back one level down — the processor wants wide leaves, the innermost cache wants narrow ones — and it is decided by the innermost cache’s $\sqrt{M} - 2$ alone.

A third cache, measured against the blocks #

The earlier essay predicted that the recursion’s advantage over tuned blocks should grow with the number of caches, since every added level is another memory a single block can be wrong about. The prediction is measurable directly: take a machine with two caches, add a middle one between them, and see what changes.

On caches of 36, 256 and 1,024 words the three boundaries want blocks of 3, 14 and 16. The block tuned to the outer cache alone costs 3.34 times the best at its worst boundary; the one tuned to the inner costs 2.16; the one tuned to the middle, 1.61. The best compromise a scan told all three sizes can find is the middle cache’s own block of 14, at 1.61 at its worst boundary. The recursion, told none of them, is at 1.21, 1.10 and 0.93. The compromise is better at the middle boundary, where it is that cache’s own best and so exactly 1; the recursion is better at its worst, 1.21 against 1.61, which is the comparison a machine with all three caches actually pays.

The machine that tests the recursion hardest is the one with the smallest inner cache. On 16, 64 and 400 words the best blocks are 2, 6 and 10, the compromise is 6 at 1.34, and the recursion is at 1.35, 1.28 and 0.96 — within one per cent of the compromise, and limited by the inner boundary, where its factor-of-two quantisation is a factor of two on a very small size.

Across five machines, adding the middle cache moves the best compromise from 1.340 to 1.340, 1.168 to 1.188, 1.578 to 1.610, 1.242 to 1.341 and 1.422 to 1.622 — never better, since a block now has one more boundary to be measured at, and up to 14 per cent worse. The block tuned to the outer cache alone suffers far more: its worst ratio goes from 2.00, 1.94, 1.58, 2.02 and 1.61 to 2.57, 2.83, 3.34, 2.13 and 3.23, because it is now also measured at a middle cache it was never tuned for.

The recursion’s worst ratio with all three caches is 1.348, 1.161, 1.215, 1.348 and 1.215. It is never more than one per cent behind the three-cache compromise and ahead of it on three machines of five. The prediction was right in direction and modest in size, and the mechanism is worth stating precisely: the recursion’s advantage grows because the blocks get worse, not because the recursion gets better. On four machines of five its worst boundary is the innermost — 1.348 whenever that cache is 16 words, 1.215 whenever it is 36 — and the middle cache leaves it exactly where it was. On the fifth, with an inner cache of 25 words, the middle cache becomes the recursion’s worst boundary too, moving it from 0.985 to 1.161, and the compromise still moves further. On the 16-and-400-word machine the effect is the difference between losing to the compromise by 8.5 per cent with two caches, 1.348 against 1.242, and drawing with it, 1.348 against 1.341, with three.

What a recursive code should do with its base case #

The practical rule is short and it comes from two measurements that agree. Set the base case by the innermost cache’s $\sqrt{M} - 2$, and let the recursion round it. Below that width the switch removes most of the calls — twenty-five times fewer at panels of 3, two hundred at panels of 6 — for at most sixteen per cent in words and usually nothing. At one halving past it the recursion moves one and a half to four and a half times the words, on every memory measured, and on a machine with several caches it does so at the innermost boundary first.

The recursion’s claim to need no knowledge of the machine survives in a weaker and more accurate form. It needs one number, the size of the smallest cache, and only to within a factor of two, because the halving rounds everything in between. Every other memory on the machine it serves without being told — which is the property the order the products are taken in found for contractions and the order decides the memory for sparse fill, applied to the traffic of one dense factorisation: the cost is decided by the ordering, and the ordering here needs one fact about the hardware rather than one per cache.

It also says what the model’s silence about calls was hiding. On the counted memory a base case of one looked like the purest form of the idea, and in the words it is: nothing below $\sqrt{M} - 2$ moves fewer. But the counted memory is exactly the instrument that cannot see why no one ships it, and a model that costs everything except the thing a design is responding to will recommend the design no one uses. The calls figure is on the page for that reason.

Still open: recursion for QR, and matrices that do not halve evenly #

The matrix measured here has 96 columns, which is 3 times a power of two, so every halving is exact and the panel widths form a clean sequence of 3, 6, 12, 24. 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, one of which may sit on the far side of an edge the other does not reach. Whether that blurs the cliff or doubles it is measurable with the same sweep and is not measured here.

The larger open question is the one the recursion’s first measurement named. Householder QR has a recursive formulation, with the same halving of columns and a compact representation of the reflections accumulated at each level, and a blocked formulation that is what libraries ship. Doing it twice and a reduction that changes the order measured QR’s traffic between processors; its traffic between caches, and whether its base case obeys the same $\sqrt{M} - 2$ when the kernel is a block reflector rather than an elimination, is the next measurement to make. And tall matrices bring back the panel, where the swap that is not optional searches a whole column at every step — the one part of an elimination neither blocking nor recursion has yet been allowed to change.