The layout that is told nothing

A B-tree is excellent and it is excellent at one block size. Its node holds as many keys as fit in a page, its height is log_B n, and every one of those statements is about a B that somebody typed into a constant.

Which raises a question the previous two essays set up and did not answer: what can an algorithm achieve if it is told neither B nor M?

The naive expectation is nothing much. A structure that does not know the block size cannot align anything to it, cannot size a node, and cannot decide how much to read at once. Every intuition says the tuned structure should win comfortably.

What “cache-oblivious” actually claims #

The term is due to Frigo, Leiserson, Prokop and Ramachandran in 1999, and it is more precise than it sounds. A cache-oblivious algorithm is one whose code contains no reference to B or M, analysed in a model where an optimal replacement policy manages an ideal cache of unknown parameters. The claim made for such an algorithm is that it is within a constant factor of the optimal cache-aware algorithm for every value of B and M simultaneously.

That “simultaneously” is the whole content. A tuned algorithm is optimal at the parameters it was tuned for and is ordinary elsewhere. An oblivious one is within a constant everywhere, and since a real machine is a hierarchy — registers, three levels of cache, memory, an SSD, a network — with a different (B, M) at every level, everywhere is what a real machine actually presents.

A tuned structure optimises one level of a hierarchy and is at the mercy of the rest. A B-tree with 4-kilobyte nodes moves the right amount between disk and memory and treats the three levels of cache above it as somebody else’s problem. It is not wrong to do that — the disk transfer dominates by four orders of magnitude — but it is a choice about which level matters, and the choice was made by whoever picked the node size, possibly decades ago.

The measurement, and where it stops flattering #

The figure holds the tree, the keys and the query fixed, and sweeps B. Three curves.

The sorted array is the control and behaves exactly as two searches, one comparison count predicted: its cost is log₂(n/B), so it improves by one transfer every time B doubles. Seven block sizes, six transfers saved, from 14 down to 8. Slow, steady, and asymptotically nothing.

The B-tree built for B = 64 is the interesting one. At B = 64 it is what it was designed to be. Below that, its 64-element nodes span several blocks each, so one node access costs several transfers and the height advantage is spent immediately. Above it, its nodes are a fraction of a block, so each transfer brings in several nodes’ worth of data and most of it is wasted — the tree is fine here, just no longer using what it was given.

The van Emde Boas layout is told nothing and falls from 9 transfers to 3, reaching 4 by B = 32 and staying at 3 or 4 for the rest of the sweep. Its curve is the only one of the three whose shape is log_B n rather than log₂ n minus a constant, and the shape is what the claim is about.

The honest reading of that figure is not that the oblivious layout wins. It is that the oblivious layout is never much worse than the best available, which is a different and more useful property. At B = 64, where the tuned structure is at its best, they are close. Away from it, the oblivious one is better because the tuned one has stopped being tuned.

The constant factor is real and is the price #

Cache-oblivious results are usually stated as “within a constant factor”, and this site’s whole habit is that the constant is the content. So: what is it?

The recursion places subtrees contiguously at every scale, and at exactly one of those scales the subtrees are about the size of a block. But “about” is doing work. The cut is at half the height, so the subtree sizes go 2^h, 2^{h/2}, 2^{h/4} — the available sizes are sparse, and for a given B the relevant level has subtrees of somewhere between √B and B nodes. A path therefore crosses somewhere between log_B n and 2·log_B n of them, and the constant is up to two, before any effects of alignment.

Alignment costs more. A subtree of the right size is contiguous, and contiguous is not the same as aligned: a run of B nodes that starts halfway through a block spans two blocks. Averaged over the tree, that is close to a further factor of two in the worst case and nearer 1.5 in practice.

The measured version of that arithmetic is visible in the numbers already quoted, and it is worth taking seriously rather than rounding away. At a million keys, B = 64, the van Emde Boas layout costs 3 transfers and a B-tree of fanout 64 over the same keys costs 4 — the oblivious layout is ahead, which is the opposite of the theory’s prediction and needs an explanation rather than a celebration.

The explanation is memory. Both structures keep their top levels resident, and the oblivious layout’s top is smaller, because the top half of the tree is laid out contiguously by construction and the B-tree’s top level is a scattering of nodes. The theoretical constant is a statement about transfers with a cold cache; with a warm one, the layout that packs its top wins the part of the path that is free.

A constant factor derived for the worst case does not predict the ordering in the average one, which is the same lesson on average is not a number drew about running times, appearing here about a bound rather than about a measurement.

The oblivious curve is a staircase too, and its treads are the squares #

“Reaching 4 by B = 32 and staying at 3 or 4 for the rest of the sweep” is the shape of the curve, and it is not the curve of a structure whose cost is $\log_B n$ in any smooth sense. It is a staircase, its treads are computable in advance from the recursion alone, and the sweep lands on them exactly.

The layout cuts a tree of height $h$ into a top half and bottom halves of height $h/2$, and recurses. Starting from $h = 18$, the heights it produces are 18, 9, 5, 4, 3 and 2 — and nothing else. Those are the only scales that exist, so the only contiguous subtree sizes available are $2^h - 1$ nodes: 262,143, 511, 31, 15, 7 and 3.

A block of $B$ elements is therefore matched by the largest of those that fits inside it, and the path’s cost is the number of such subtrees it crosses. At $B = 32$ the biggest that fits is the 31-node subtree of height 5, so a path of eighteen levels crosses $\lceil 18/5 \rceil = 4$ of them — four transfers. At $B = 64$, 128 and 256 the answer is the same subtree, because the next size up is 511 and does not fit, so those three block sizes buy the layout nothing at all. At $B = 512$ the 511-node subtree fits, the path crosses $18/9 = 2$ of them, and the measured cost drops to three with alignment accounting for the difference.

That is the whole flat region explained, and it explains the theoretical constant at the same time. Within a tread the layout is using a subtree of about $\sqrt{B}$ nodes where $B$ were available, so it crosses about twice as many as it needed to — the factor of two in the bound and the flatness of the curve are one phenomenon, not a worst case and a measurement that happen to agree. The bound is tight at the top of each tread and slack at the bottom, and a sweep that stops at $B = 256$ is reporting the slack end.

Two things worth carrying.

The treads widen by squaring, because the heights halve: 3, 7, 15, 31, 511, 262,143 nodes. So the block sizes at which the layout improves are sparse and get sparser, and past a certain point a machine’s whole hierarchy sits inside one tread. That is a genuine limit on the technique rather than a constant to be engineered away — the staircase in external sorting has treads a factor of $M/B$ wide and this one has treads that square, and in both cases the useful reading is where the next step is rather than what the curve does between them.

And it says what a tuned structure is actually buying. A B-tree’s fanout can be any integer, so it sits exactly on its block at every block size — which is what a tree with nodes the size of a block means by the fanout being read off the hardware. The oblivious layout’s scales are fixed by the recursion before any hardware is consulted, and the price of asking nothing is being able to use only the sizes the recursion happened to produce.

Why nobody ships one #

Cache-oblivious structures are twenty-five years old, are provably good, and are almost absent from production systems. That is a fact worth an explanation rather than a lament, and the explanation is not that engineers have not heard of them.

The layout is only free when it is static. Computing the van Emde Boas position of a node is not free — it is a recursive decomposition of the index, more arithmetic than a shift — and worse, inserting a key changes the tree’s shape and therefore the layout of everything after it. The dynamic versions exist (packed-memory arrays and their relatives) and their amortised bounds are good and their constants are considerably worse.

A real system knows B. The argument for obliviousness is strongest when the parameters are unknown, and a database on a machine it controls can simply read the page size. The property being paid for is one the deployment does not need.

The constants compete with tuned code that is decades old. A B-tree implementation has had thirty years of attention paid to its node format, its prefetching and its search-within-node. An oblivious layout with a factor of two in the bound is starting two factors behind.

Where the idea has landed is in the algorithms nobody has to store: cache-oblivious matrix multiplication and transposition, and the recursive layouts inside numerical libraries. Those are one-shot computations over data that is already laid out, the recursion is over the computation rather than over a structure, and there is nothing to insert into. That is exactly the case where the property is free — and it is why the technique is far better known in numerical computing than in databases.

The other results in the family #

The layout is the easiest cache-oblivious result to draw and it is not the important one. Three others are worth naming, because together they show that the technique is a general method rather than a trick that happens to suit trees.

Matrix transposition and multiplication. Split the matrix into quadrants and recurse. At some level of the recursion the quadrants fit in memory, and from there down everything is free — without the code containing M anywhere. The tiled version of the same algorithm, which is what a tuned library ships, needs to know M and needs re-tuning for every machine. This is the result that made the technique famous and it is the one with the fewest objections to it, because a matrix multiplication has nothing to insert into.

Funnel sort. The cache-oblivious analogue of external merge sort: a recursively-built merger of √n inputs, itself made of smaller mergers, achieving the (n/B)log_{M/B}(n/B) bound without knowing either parameter. It is the direct competitor to the algorithm measured in sorting what will not fit, it is asymptotically as good, and its constant is worse by enough that no database uses it.

Static search trees, which is what this essay measures, and their dynamic relatives built on packed-memory arrays.

The pattern in all four is the same, and it is worth extracting because it is the actual idea: recurse, and let the recursion do the tuning. A structure cut in half repeatedly passes through every scale on its way down, so whatever scale the hardware cares about is one of the levels — and the algorithm reaches it without being told which one it is.

What this says about parameters #

The pattern here is not confined to memory layouts, and it is worth stating in general because the site has now met it three times.

A tuned algorithm makes a claim conditional on a parameter, and the claim is strong where the parameter is right. Timsort’s minrun of 32 is right for a particular ratio of comparison cost to move cost. A B-tree’s fanout is right for a particular page size. Both degrade away from their point, gracefully or otherwise, and neither degradation appears in the complexity class.

An oblivious algorithm makes a weaker claim over a wider range, and the trade is a constant factor for robustness — which is a trade the notation cannot express at all, because the constant is exactly what it discards.

So a claim of optimality has a domain, and stating it without the domain is the error. That is this phase’s second theme, arriving at its most general: the model has parameters, an algorithm may or may not be told them, and “optimal” without them named is not a statement about anything. The graph field reached the same place from the other direction, where a bound in V and E means nothing until the density regime is stated.

Three more settings, because tracks the best of the others across the range is a claim that has to survive the range being changed.

Neither of those widens the axis, though, and across the range is a claim about the axis. The last of the three stretches it: nine block sizes rather than seven, from four elements to a thousand and twenty-four, which is a factor of two hundred and fifty-six either side of the tuned value.

Measuring an algorithm that is defined by what it does not know #

There is a methodological oddity here that is worth naming, because it is the reason this essay’s figures are shaped as they are.

Every other claim on this site is measured by running something and counting. A cache-oblivious claim cannot be measured that way, because it is a claim about all values of two parameters, and running something gives one value of each. No finite set of measurements establishes it, in exactly the way no finite set of measurements establishes an asymptotic class — which is a limit is not a prediction’s argument, met again in a second dimension.

What a sweep can do is what it has always done here: refuse the claim if it is false, and measure the constant if it is not. A layout that was excellent at one block size and poor at another would show it immediately in a seven-point sweep, and the sweep is therefore worth running even though it proves nothing. The claim survives it, and the surviving is worth exactly what a survived falsification test is worth — which is more than an unmeasured assertion and less than a proof.

The figures also hold something fixed that is easy to forget: the memory size. Every point in the sweep uses M = 16,384, so what has been measured is obliviousness in B alone. The full claim is about both parameters, and sweeping M as well would need a surface rather than a curve. That is a gap in this essay’s evidence rather than in the theory, and it is named rather than papered over.

The one thing an oblivious algorithm cannot do #

It cannot beat the aware one at its own point, and no argument here suggests otherwise. The theory says within a constant, the constant is at least 1, and every measurement in this essay is consistent with that.

What it can do is be within that constant at a level of the hierarchy nobody analysed. A B-tree tuned for a disk page is, at the level of the L2 cache, an arbitrary arrangement of nodes with no locality argument behind it at all — and a query served entirely from memory, which is what a query against a warm index is, spends its whole time at that level. The tuned structure’s advantage is at the level it was tuned for, and the level it was tuned for is the one that stops mattering as memory gets larger.

That is the argument for taking the idea seriously in a world where the working set of most databases fits in RAM, and it is a prediction rather than a measurement — which is worth saying plainly, because this site’s whole discipline is the difference between the two. What has been measured here is one layout against one tuned structure over seven block sizes at one memory size. Whether that generalises to a five-level hierarchy under a real workload is a question this instrument cannot answer, and the block that is not a block is where the instrument’s limits are set out in full.