Two searches, one comparison count

The cleanest experiment in this field takes one algorithm and changes nothing about it.

A complete binary search tree over a million keys is searched by walking from the root to a leaf, comparing at each node and going left or right. Twenty comparisons, twenty nodes, one path. The algorithm is fixed, the input is fixed, the path is fixed, and the sequence of comparisons is byte for byte identical.

The only free variable is which memory address each node is stored at — a question the algorithm never asks and every complexity analysis treats as beneath notice.

The three arrangements #

In order. Node addresses follow the sorted order of the keys, which is to say the tree is a sorted array and the search is binary search. This is what every implementation of binary search does and what nobody thinks of as a layout at all.

Level order. The root at 0, its children at 1 and 2, its grandchildren at 3 to 6: the arrangement an implicit binary heap uses, and the one most people draw when asked to store a tree in an array.

Van Emde Boas. Cut the tree at half its height. Lay out the top half contiguously; then lay out each of its bottom subtrees, in order, by the same rule applied recursively. It is defined in two sentences, it mentions no hardware parameter of any kind, and it was published as a way of storing priority queues in 1977.

At a million keys, B = 64, and memory holding 4,096 elements, the measured transfers per search are 13, 15 and 3.

Why the sorted array loses #

Binary search’s probes are at n/2, then n/4 or 3n/4, then eighths. The first ⌊log₂(n/B)⌋ of them are more than a block apart, so each one lands in a block of its own and costs a transfer. Only the last log₂ B probes — the ones inside a single block — are free.

So binary search costs about log₂ n − log₂ B = log₂(n/B) transfers. At a million keys and B = 64 that is 20 − 6 = 14, and the measurement says 13, the difference being one probe that happened to share a block with its neighbour.

The important part of that expression is what it is not. It is not log_B n. Subtracting a constant number of levels is not the same as changing the base of the logarithm, and the difference between the two is the difference between an algorithm that scales with the hierarchy and one that does not. Double the keys and binary search costs one more transfer, forever.

Level order is worse than the sorted array, which is the result in this figure that surprises people, including the author. The reason is that the first few levels of a level-order tree are indeed packed together — nodes 0, 1, 2, 3, 4, 5, 6 sit in one block — but as soon as the level exceeds a block, consecutive levels are far apart, and the path’s last dozen nodes are each in a fresh block. The top of the path is nearly free and the bottom of it is fully priced. Since the bottom is most of a path, the arrangement helps least where a path spends most of its length.

The layout that looks natural is the one that optimises the cheap part of the problem, which is a specific and recurring kind of design error, and it has appeared on this site before under a different name: minimising the count that is easy to see rather than the one that is being paid.

Why van Emde Boas wins #

The recursive cut is doing one thing, and it is worth stating in the form that makes it obvious.

Consider the recursion at the level where its subtrees are about the size of a block. At that level, the layout has placed each subtree contiguously — that is what “lay out each bottom subtree by the same rule” means when the subtree is small enough — so a subtree of about B nodes occupies about one block. A root-to-leaf path passes through log₂ n nodes and therefore crosses about log₂ n / log₂ B = log_B n such subtrees, each costing one transfer.

That is the B-tree’s bound, obtained without the algorithm knowing B.

The recursion cannot be told where to cut for a particular block size, so it cuts everywhere: there is a level of the recursion whose subtrees are the right size for any B one might name, and the path pays about one transfer per subtree at whichever level that happens to be. It is a layout that is simultaneously right for a cache line, a disk page and a network fetch, and it is why the property is called cache-oblivious rather than cache-friendly. The layout that is told nothing is the essay about what that buys, and about what it costs.

What makes this the site’s cleanest two-counter result #

Four times now an essay here has found two things that one counter calls identical and another separates. It is worth setting them beside each other, because this one is different in kind and the difference says something about what a controlled comparison is.

• Two merge sorts with identical comparison counts and total allocation differing by a factor of n. The algorithms differ.
• Two reservoir samplers with identical output distributions spending 1,356,399 and 9,380 random bits. The algorithms differ.
• Insertion sort and merge sort, 176× the comparisons and a sixth of the branch mispredictions. The algorithms differ enormously.
• Three tree layouts, identical comparison counts, transfers of 13, 15 and 3. The algorithm is the same algorithm.

In the first three cases the counter separated two different procedures that happened to agree on one quantity. Here nothing about the procedure differs at all — the same comparisons in the same order on the same keys — and the cost differs by a factor of five. The independent variable is not the algorithm; it is a decision that is not part of the algorithm and that no notation for algorithms can express.

That is the strongest form the argument can take, and it is only available because the comparison count could be held exactly fixed. assertLayoutChangesTransfersNotComparisons requires precisely that: the three layouts must agree on comparisons at every size, and must disagree on transfers. If they ever agreed on both, the counter would be measuring nothing; if they disagreed on comparisons, the experiment would be confounded and every number in it worthless.

The same argument, one dimension up #

The experiment generalises immediately and the generalisation is the one every numerical programmer has met, usually as folklore rather than as a measurement.

Take an n × n matrix stored row by row, and add it to its transpose. Walking the result in row order touches the first matrix sequentially and the second by column — a stride of n between consecutive accesses. If n is larger than a block, every access to the second matrix is a transfer, and the loop costs n² transfers instead of 2n²/B.

Swapping the two loops changes which matrix is walked badly and changes nothing else. The comparison count, the arithmetic count, the number of additions, the number of loads and stores in the source are all identical; the transfer count differs by B. That is the same experiment as the tree layouts with a different object in it, and it is the reason “loop interchange” is a compiler optimisation with a name.

The fix that actually gets used is tiling: process the matrix in b × b squares chosen so that a square of each matrix fits in memory at once, so each block is fetched once and used b times. That is a cache-aware transformation — it needs to know M — and the cache-oblivious alternative is the recursive one, splitting the matrix into quadrants until the quadrants are small, which needs to know nothing and is within a constant.

The recursive layout of a tree and the recursive decomposition of a matrix are the same idea: cut the problem in half repeatedly, and somewhere in the recursion is a level at which the pieces are the size of a block, whatever the block turns out to be.

What a layout costs to compute #

An arrangement is only free if the address arithmetic is free, and the van Emde Boas layout’s is not.

The in-order and level-order layouts have trivial addressing. In level order the children of node i are at 2i and 2i+1: one shift and an add, which is why implicit heaps are laid out that way and have been since 1964. In sorted order the address is the midpoint of the current range, which is a shift.

The van Emde Boas position is a recursive decomposition of the node’s index and costs considerably more — several multiplications and a loop over the levels of the recursion, or a precomputed table, which is memory. The layout that minimises transfers maximises the arithmetic needed to find them, and in a model where computation is free that is invisible by construction.

At the level of a disk page this does not matter at all: a few dozen instructions against a transfer costing fifty microseconds is nothing. At the level of a cache line it matters a great deal, because a cache line fill is eighty nanoseconds and a few dozen dependent instructions is a comparable number. So the layout’s advantage is real at the bottom of the hierarchy and can be eaten entirely at the top, which is the reverse of where the theory’s attention usually is, and it is one of the main practical reasons the technique is rarer than its bounds suggest.

The measurements in this essay charge nothing for the addressing, exactly as the model says to, and a reader taking the factor of five to a real implementation should expect to lose some of it here.

Why the comparison count was ever the right thing to count #

It would be easy to read this essay as an argument that the comparison count was a mistake, and that is not the argument.

A comparison count is exact, reproducible on every machine, and independent of every implementation decision — which is precisely why the first three phases of this site were built on it. The transfer counts above are none of those things: they depend on B, on M, on the replacement policy, and on the layout, and every figure in this field has to print two parameters to mean anything at all.

Both properties are worth having and they are in tension. A quantity robust enough to be quoted without context is, for that reason, unable to distinguish things that context makes different. The comparison count cannot see the factor of five in this essay; the transfer count can see it and cannot be quoted without a paragraph of setup.

The resolution the site has arrived at over six counters is not to prefer one but to name what each one is blind to at the point it is used — which is why every figure in this field carries its B and its M on the plate, and why the caption of every comparison-count figure says what it counted.

Where this does and does not apply #

Two honest boundaries, because a result this clean invites over-reading.

The trees here are complete and static. Every node is present, the shape is fixed, and the addresses can therefore be computed rather than stored. A tree that grows has to allocate, and an allocator that hands out nodes in the order they are created produces neither of the good layouts — it produces roughly the order of insertion, which for random insertions is roughly random. Most binary search trees in most programs have no layout at all in this sense, and their transfer cost is the pointer-chasing worst case: one transfer per level, with no sharing.

That is not a small caveat, it is most of the practical story, and it is why the structures that actually get used for large data are the ones that allocate in blocks by construction. A B-tree cannot have a bad layout, because its node is the unit of allocation.

The measurement is of a search, not of a workload. Each figure here walks one path into a cold or warm memory and reports what it cost. A structure serving millions of queries has a very different profile, because the top of the tree is shared by every query and stays resident — which is measured in a tree with nodes the size of a block and is worth a factor of two there. Under that workload the layouts converge somewhat, because all three keep their roots.

They do not converge fully, and the reason is the same one as before: the top of a path is where every layout is cheap, and the bottom is where they differ.

What the oscillating constant is, and what it prices #

The constant oscillates with the height is the right diagnosis and it can be turned into a number, which is worth doing because the number is the price of obliviousness.

The recursion cuts at $\lceil h/2 \rceil$, so from a tree of height $h$ the only subtree heights it ever produces are the halving sequence of $h$: from 20 that is 20, 10, 5, 3, 2, 1, and from 16 it is 16, 8, 4, 2, 1. A subtree of height $j$ holds $2^j - 1$ nodes, so at $B = 64$ the largest one that fits a block has height six — and the layout can only use a cut-height that its halving sequence happens to contain.

Call that usable height $h^*$. A path crosses about $h/h^*$ subtrees, against the ideal $h/6$, so the constant factor the bound hides is $6/h^*$. Evaluate it down the sweep:

• $h = 8$ — sequence 8, 4, 2, 1; $h^* = 4$; factor 1.50
• $h = 10$ — 10, 5, 3, 2, 1; $h^* = 5$; factor 1.20
• $h = 12$ — 12, 6, 3, 2, 1; $h^* = 6$; factor 1.00
• $h = 14$ — 14, 7, 4, 2, 1; seven is too tall, so $h^* = 4$; factor 1.50
• $h = 16$ — $h^* = 4$; factor 1.50
• $h = 18$ and $h = 20$ — $h^* = 5$; factor 1.20

So the constant swings between 1.00 and 1.50, it is exactly one when a halving of the height lands on six, and it is worst at fourteen and sixteen — where the sequence steps straight past six from seven to four.

That is the whole of the non-monotonicity. It is not noise and it is not a measurement artefact: the cost depends on the binary structure of the height rather than on its size, so a taller tree whose sequence cooperates genuinely costs fewer transfers than a shorter one whose sequence does not. The $h^* = 5$ at twenty against $h^* = 4$ at sixteen is exactly the pair the sweep reports, and the measurement at twenty comes in one under even that, which is two subtrees of thirty-one nodes sharing a sixty-four-node block.

And it prices the property the technique is named for. A layout told $B$ would cut at six every time and pay the ideal. A layout told nothing cuts at halves and pays up to fifty per cent more — that fifty per cent is what obliviousness costs, on this block size, and it is a far more useful statement than within a constant factor, which is true of any constant at all.

Two consequences follow, and the second is the one that survives past this structure.

The waste is removable by padding rather than by telling. Growing a height-fourteen tree to sixteen does not help, because both have $h^* = 4$; growing either to twenty-four would, since 24, 12, 6 contains six exactly. That is a large amount of padding for a fifty per cent saving, so the honest answer is usually to accept the constant — but knowing which heights are the bad ones is knowing where the accepting hurts.

And a bound with an oscillating constant is a different object from one with a settling constant. The layout that is told nothing sweeps the block size and finds the advantage holding at every $B$, which is the strong claim; this is the fine structure underneath it, and it says the advantage arrives with a wobble of half its own size. Nothing in one access, eight kilobytes’s model forbids that, and nothing in the asymptotic statement reveals it.

Two more settings of the same picture say which of its numbers is fixed and which is not. Shrink the tree, or shrink the block: the comparisons stay equal across the three layouts every time, and the blocks touched do not.

One number to take away #

The three layouts are worth reducing to their forms, because the forms are what generalise and the measurements are what check them.

• Sorted array: log₂(n) − log₂(B) transfers. Subtracting a constant.
• Level order: about log₂(n) − log₂(B) at the top and one per level below it, which is worse than the array because its good part is where the array is already good.
• Van Emde Boas: about log_B(n). Changing the base.

Only the third is a different function of n, and the difference between subtracting a constant from a logarithm and dividing it is the entire content of this field. At a million keys and B = 64 that is 20 − 6 = 14 against 20/6 ≈ 3.3, and the measurements — 13 and 3 — say so.

A last observation about the measurements themselves. The van Emde Boas cost is not monotonic in the tree height: it is 4 transfers at 65,535 keys and 3 at 1,048,575. That looks like an error and is not. The recursion cuts at ⌈h/2⌉, so the subtree sizes available at a given height are a fixed sequence, and whether one of them lands near B is a property of h rather than a smooth function of it. A cost that improves as the problem grows is exactly the sort of result that ought to be checked before it is published, and what it says is that the constant in “within a constant factor” oscillates with the height rather than settling.