A heap that keeps its levels in a line

A buffer that does not shift its tail replaced the read-only family’s sorted buffer with a max-heap. The family scans its input once for each batch of output, keeping in the buffer the smallest values greater than the last one written; a sorted buffer takes each new value by shifting every larger entry one place, and below the memory that holds the buffer each shifted line goes back to slow memory dirty. A heap takes the same value by replacing its root and sifting down one path. On the replay used since the memory a product does not charge — LRU over lines of eight cells, a transfer for each line fetched and another for each dirty line evicted — the heap cut the family’s least transfers × fast memory, write-backs included, from 1.87 to 1.71 of $n^2/B$ at a 64-cell buffer, and from 2.39 to 1.62 at 256 cells.

It stopped short for a reason the plates located: at its best memory, 32 cells, the heap still wrote back a third of the lines it fetched, and the lines were the deep levels. An array heap puts the children of cell $i$ at $2i + 1$ and $2i + 2$, so its first line holds the root and the two levels under it, and from there each level of a path lands in a different line. A sift that runs to the bottom of a 64-cell heap crosses four lines, and with four lines of fast memory in all, most of them are evicted dirty before the next sift comes back.

The proposal was a layout, not an algorithm. Keep the comparisons and the moves exactly as they are, and change only where each node lives: put every subtree of three levels — seven nodes — in one aligned line of eight, the eighth cell spare. A path then crosses a line boundary once every three levels. The prediction was a write-back share at 32 cells falling from 33% to about 15%, and a least product falling from 1.71 to about 1.5. Two risks were named: the heapsort that ends each scan, whose extractions sift through every level, and the arithmetic of the blocked layout, which the replay does not charge.

Seven nodes and a spare cell #

The layout is built by walking the heap’s subtrees in breadth-first order. The root’s three-level subtree is block 0: the root, its two children and its four grandchildren, in heap order inside the block, occupying cells 0 to 6 of the first line. The eight great-grandchildren are the roots of the next eight blocks, numbered in the order they are reached, and each of those holds its own three levels. A node’s cell is eight times its block’s number plus its place inside the block. The buffer’s first cell sits at a multiple of eight, so every block is exactly one line.

The heap itself is untouched. The trace records the same root reads, the same pairs of child reads, the same swaps, in the same order; only the addresses those accesses name are different. The replay confirms that: at every buffer the blocked family makes the same number of accesses and the same number of writes as the array-heap family, and both output 0 to 8,191 in order.

What a sift’s path crosses #

A sift that reaches depth 5 of a 64-cell heap crosses 3.88 lines laid out as an array and 2.00 laid out in blocks of three levels. The two layouts agree for the first three levels, which in both cases are the first seven cells of the first line. They part at depth 3. The array heap’s depth-3 nodes are cells 7 to 14: the first sits in line 0 with the root and the other seven in line 1, so a path to depth 3 crosses 1.88 lines on average. From there the array heap doubles its cell index at every level and lands in a new line each time. The blocked heap’s depth-3 node is the root of a fresh block, and its own two levels beneath it are in the same line.

This is the arithmetic the proposal relied on, and it is exact for the levels the blocks fill. It says nothing yet about how often a sift goes deep, and the answer to that is the thing a heap buffer is good at: once the buffer has filled with small values, most input values are larger than the root and are turned away after one comparison, and the values that do enter sift down only as far as their size requires. The lines a path crosses matter in proportion to how many paths are long.

The share the deep levels were costing #

At 32 cells of fast memory, the blocked heap writes back 18% of the lines it brings in, against the array heap’s 33% and the sorted buffer’s 45%. The prediction was about 15%, and it was close to right in kind. At this memory four lines of fast memory hold the input’s current line, the bookkeeping cell and the output’s current line, and leave about one line for the buffer. The array heap’s sifts below the root’s line each dirtied a line that was evicted before it was used again; the blocked heap’s sifts dirty half as many lines, and the share of the traffic that is a buffer line going home dirty falls with them.

At 64 cells of fast memory the two heaps are six points apart rather than fifteen. That memory holds the array heap’s eight lines and most of the blocked heap’s ten, and the array heap’s deep levels, which were the problem at 32 cells, now stay resident between the sifts that reach them. By 128 cells the layouts write back almost the same share, and at the largest memories the blocked heap’s share is a point higher, for a reason that comes up below: it occupies more lines, and the output flush at the end counts them.

A third written back at the best memory had looked like a property of a buffer that changes during the scan. A buffer that does not shift its tail asked whether such a buffer always pays some fixed share to the memory that cannot hold it, and the answer is that it pays the share of lines its writes touch, which its layout sets. A third was the array heap’s number, not the heap’s.

Under the floor that was a measurement #

With write-backs charged, the blocked heap’s least transfers × fast memory is 1.25 of $n^2/B$ at 32 cells, against the array heap’s 1.71 — and under the 1.29 the sorted buffer reached with no write-backs charged at all. The prediction said about 1.5, reasoning that the product scales with one plus the write-back share: 1.29 times 1.15. That reasoning held the reads fixed at the sorted family’s figure, which the two earlier essays had both measured as 1.29. It assumed the layout could change only the writes.

It changes the reads as well. At 32 cells of fast memory the array-heap family misses 337,552 times and the blocked family 278,436 times, about a sixth fewer, and the whole difference is in the buffer’s lines, since the input, the bookkeeping cell and the output are read and written identically by both. A sift-down reads both children at each level before deciding which way to go; in the array layout each level below the first line is a new line and a miss, and in the blocked layout two levels out of three are in a line already fetched. The blocked family’s reads alone come to 1.06 of $n^2/B$, and its write-backs add 18% to that, giving 1.25.

So the number the two earlier essays called the family’s floor on this product — 1.29, the best the sorted family reached on reads — was a measurement of the sorted buffer and the array heap at one memory, not a property of reading the input once a scan. A floor under a product derived the bound such products cannot go below; this family has now been measured at three heights above it, and each time the change was where the buffer’s cells were.

The plate also shows where the gain stops. At 64 cells of fast memory the blocked heap’s product is 1.68 against the array heap’s 1.80, a smaller gap; at 128 cells it is 2.75 against 2.71, the first memory where it is behind. Once the array heap’s whole buffer fits, the blocked heap’s two extra lines are only cost.

Three buffers, and one that got worse #

By buffer, the blocked heap’s least product is 2.92, 1.25 and 1.13 of $n^2/B$ at 16, 64 and 256 cells: best at the two larger buffers and worst of every buffer measured at the smallest, where its 16 nodes occupy 72 cells. The failure was not either of the two the proposal named. It is the layout’s fill. A 16-cell heap has five levels: the first three fill block 0, and the fourth level’s eight nodes are the roots of eight new blocks, each of which holds its root and, for the first of them, a single node below. Sixteen nodes, nine lines. The array heap packs the same sixteen nodes into two.

At 32 cells of fast memory — four lines, the least memory for every 16-cell buffer — the array heap’s two lines of buffer mostly stay resident beside the input’s line and the line shared by the bookkeeping cell and the output, and a sift rarely costs a transfer. The blocked heap’s nine lines cannot all stay, and a sift into the fourth level is a miss whatever line it lands in. Its reads alone rise to 2.71 of $n^2/B$ against the array heap’s 2.23. The blocking that saved lines on long paths spent them on short ones, because at this size there are no long paths.

The 256-cell buffer shows the same fault in a milder form. Its first six levels are nine full blocks; its seventh, eighth and ninth levels are 64 blocks of three nodes each, a root and its two children, with five of the eight cells in each line empty. The heap occupies 584 cells for 256 nodes. Below the buffer that costs nothing, because the deep blocks are each visited by a few sifts and the saving on the full blocks above dominates; the blocked family’s reads alone reach 0.81 of $n^2/B$ at 32 cells, the lowest any version of this family has reached, and its product with write-backs 1.13. Above the buffer the empty cells come due.

A memory that holds one layout and not the other #

With a buffer of 256, the blocked heap moves fewer lines at every fast memory up to 64 cells and more from 128 up — 86,862 transfers against 47,330 at 512 cells, nearly twice as many: its nodes occupy 584 cells, and a memory that holds the array heap does not hold it. At 512 cells of fast memory the array heap’s 32 lines all fit, with room for the input and the output, and the family’s transfers are almost all the input read once a scan. The blocked heap’s 73 lines do not fit, and every scan’s sifts and every end-of-scan heapsort refetch some of them. Only at 4,096 cells, where both layouts and much else fit, do the two meet again.

This is the risk the proposal half named and half missed. It worried about the extraction step, the heapsort at the end of each scan, which sifts from the root through every level and touches every block. That cost is real, but it is the same number of accesses in both layouts; what makes it dear is that the blocked heap’s blocks are spread over more lines. The heapsort and the output pass both visit all 584 cells, and at memories between the heap’s node count and its extent, every visit is a miss that the array heap does not have.

None of these memories is where the family is cheapest — its least product is at 32 cells for every heap — so the loss above the buffer does not touch the headline figure. It matters for a buffer chosen to fit a given memory, which is how a buffer would be chosen in practice. Two searches, one comparison count found the same shape for search trees: three arrangements of one tree making the same comparisons and costing fifteen, thirteen and three block transfers, the best of them only for the block size it was built for.

What the layout is really choosing #

The blocked layout is a choice about which pairs of nodes share a line. The array layout puts siblings and their whole level together: a line holds eight consecutive cells, and below the root’s line that is eight nodes of one level, siblings and cousins, of which a sift touches two. The blocked layout puts a node with its children and grandchildren: a line holds the part of a path a sift is about to walk. A sift reads two siblings at each level, so the array layout is not wasteful at every level — it serves each comparison’s pair in one line — but it serves only one level per line, and the blocked layout serves three.

What the blocked layout gives up is density at the ragged bottom. A heap’s last level is almost never full; with blocks of three levels, any level count that is not a multiple of three leaves the last tier of blocks holding one or two levels each, in lines sized for three. The waste is worst when the heap has one level past a multiple of three — sixteen nodes, five levels, nine lines — and smallest when its depth is a multiple of three, which none of the three buffers here is. The layout that is told nothing took the recursive form of the same idea, the van Emde Boas layout, which splits a tree by halving its height rather than in fixed tiers, and found it tracking the best block-aware layout across seven block sizes; it was measured there on complete trees, where the ragged bottom does not arise.

Where an algorithm looks drew heapsort’s accesses as a spray with a descending upper edge, a shape none of the sweeping sorts makes. The spray was the array layout’s: a path that doubles its index each level. The heap inside this buffer makes the same comparisons as that heapsort, and on the replay its spray has become three tiers of local work.

The model under the numbers #

Every number above is an LRU replay with write-allocate and write-back, in lines of eight cells. The model a bound was quoted in is the warning that applies: a fully associative memory with perfect recency is kinder to scattered access than real caches, and a machine that prefetches the next line would charge the array heap’s in-order sweeps less. The block that is not a block listed the further differences — several levels, queued requests, a clock. The comparison here is between two layouts under one model, and what it measures is which lines each makes the memory hold.

The address arithmetic is not charged. The blocked layout computes a node’s cell from its block number and its place in the block, which costs a table lookup or a few shifts per access, and the array heap’s $2i + 1$ costs one. Here the mapping is a precomputed table of 256 entries at most, read as if it were free. On a real machine that table would itself occupy cache.

What the replay does not count #

One input. 8,192 random keys, one seed. A sorted or nearly sorted input would rarely enter the buffer after its first fill, and the sift paths, which are where the layouts differ, would be short.

One line size and one block shape. Lines of eight cells, blocks of seven nodes. A line of sixteen would fit four levels with one spare, and the ragged-bottom waste would move with it.

The family’s own scans. The buffer changes the transfers inside each scan and not the number of scans, $n/S$; the trade between buffer size and scan count is the earlier essays’ and is unchanged.

Still open: a heap blocked from its leaves #

The plates leave one fault in the layout, and it is the fill. Blocks are cut in tiers of three levels from the root down, so the bottom tier is whatever the heap’s depth leaves over: a single node per block at 16 cells, three nodes per block at 256. A heap could be blocked from the other end. Let the root’s block take only as many levels as the depth leaves over after the full tiers — one or two — and let every tier below it be a full three levels, so that the partial block is the one at the top, read by every sift and always resident, and the many blocks at the bottom are full lines.

The measurement that follows cuts the tiers that way and replays the same buffers and memories. The prediction is that at 16 cells the blocked heap’s least product falls from 2.92 to about the array heap’s 2.35, since the heap then occupies three or four lines rather than nine, and that at 256 cells its extent falls from 584 cells to under 300 and the memories from 128 to 512 stop being worse than the array heap’s, while its least product stays near 1.13. It could fail on the last level, which a heap fills from the left and almost never completes: a 256-cell heap’s ninth level has one node, and no way of cutting tiers puts a level of one node in a full line. The question is whether a heap’s layout can be matched to its depth at every size, or whether a structure that grows one node at a time always has a last tier the lines do not fit.