A heap whose last node is a level

The read-only family of sorts — the sorts that never write to their input, and pay for it in scans — keeps a buffer of the smallest values not yet output, and the strand that has been pricing it in cache lines has been arguing about how to lay that buffer out. The lines a sort writes back found that a sorted buffer writes back most of the lines it brings in, because inserting near the front shifts everything after. A buffer that does not shift its tail replaced it with a max-heap, which touches one path of about $\log_2 S$ cells an insertion, and the family’s least product of transfers and fast memory fell from 1.87 to 1.71 of $n^2/B$ at a 64-cell buffer.

A heap that keeps its levels in a line then laid the heap out so that a path crosses fewer lines: every three-level subtree, seven nodes, in one aligned line of eight cells, so that a sift moves to a new line once every three levels instead of at every level past the third. At 64 cells the least product fell to 1.25, and at 256 to 1.13. At 16 it rose to 2.92, worse than every other buffer kept any other way, and the essay traced that to the layout’s fill: its 16 nodes occupied 72 cells, nine lines, and its 256 nodes occupied 584.

Its closing section proposed cutting the tiers from the other end. Let every tier below the root’s block be a full three levels, so that the root’s block takes whatever the depth leaves over — one level or two — and the partial block is the one at the top, read by every sift and always resident. The prediction was that 16 cells would fall to about the array heap’s 2.35, that 256 nodes would occupy under 300 cells, and that the memories from 128 to 512 cells, where the root-blocked heap had been worse than the array heap, would stop being worse. It named a risk at the last level: a heap fills that level from the left and almost never completes it, and a 256-node heap’s ninth level has one node.

Four layouts #

The family and the replay are the earlier essays’: 8,192 random keys, the buffer at 16, 64 or 256 cells, every input read, bookkeeping cell, sift step, heapsort step and output write traced in order, replayed through a least-recently-used cache of $M$ cells in lines of eight, with every dirty line written back when evicted. The comparisons and moves are the array heap’s in every layout; only the addresses change, and the measurement checks that each layout gives every node its own cell inside its extent.

Array: children of node $i$ at $2i+1$ and $2i+2$, one cell a node. Blocked from the root: the earlier essay’s — the root’s block holds three levels, every block below it three more. Cut from the bottom: the proposal’s — count the heap’s depth, give every tier below the root a full three levels, and give the root’s block the remainder. Cut over the full levels: a fourth layout, which the first measurement of the third made necessary and which the sections below explain — count only the levels the heap holds completely, cut those into tiers from the bottom, and put each node of the incomplete last level into the spare eighth cell of its parent’s line, or into an overflow line opened for that block when the spare is taken.

The plate is the whole story of the essay in one curve each. Cut from the bottom, the proposal’s layout occupies 40 cells at 16 nodes, against 72 blocked from the root; 152 at 64 nodes, against 80; and 584 at 256, exactly what it was. Better at one buffer, nearly twice as bad at another, unchanged at the third.

The node that is a level #

The cause is in the buffer sizes and in the word “depth”. Every buffer measured holds a power of two: 16, 64 and 256 nodes. A heap of $2^j$ nodes is a complete heap of $2^j - 1$ — every level full, $j$ levels — and one node more, alone on level $j+1$. Its depth is $j + 1$, and the one extra node is the whole of the last level.

A rule that cuts tiers by depth treats that node as a level that must be housed like any other. Blocked from the root, 256 nodes are nine levels, three tiers of three; the bottom tier’s 64 blocks were meant to hold levels seven to nine, and hold only levels seven and eight, three nodes a line, because level nine has a single node — the earlier essay’s “root and its two children, with five of the eight cells empty”. Cut from the bottom, nine levels are still three tiers of three, so the layout is the same layout. At 64 nodes the depth is seven, so the bottom-cut layout gives the root a block alone and two full tiers below it — and the bottom tier’s sixteen blocks again hold two real levels and the lone node, three nodes a line: 152 cells. At 16 nodes, depth five, it gives the root two levels and one tier below of four blocks, three nodes a line: 40 cells.

No rule that counts depth can fix this, because the problem is not where the partial tier goes but that a depth count includes a level holding one node. The proposal’s named risk was exactly right, and arrived not on the last level’s fill in general but on the buffer sizes the strand happened to use: a power of two is the worst size there is for a heap’s levels.

Cutting over the full levels #

The fourth layout stops counting the stray node as a level. It counts the levels a heap holds completely — four at 16 nodes, six at 64, eight at 256 — and cuts those from the bottom, so the root’s block holds one, three and two levels respectively and every tier below holds three full levels, seven nodes a line. The incomplete last level’s nodes go where the blocked layout always had room for them: each block’s eighth cell, left empty because seven nodes fill a line of eight with one to spare. A child on the incomplete level lives in its parent’s line.

On the plate it is the lowest curve at every size: 24 cells at 16 nodes, three lines; 72 at 64; 296 at 256 — the prediction’s “under 300”, reached by the layout the prediction did not describe. Away from the powers of two it is also the densest blocked layout: 112 cells at 100 nodes against 152 cut from the bottom and 368 from the root, 224 at 200 against 296 and 584.

The density costs a little in paths. A sift to the leaves of a 256-node heap crosses 5.88 lines laid out as an array and 3.00 in both blocked layouts. The full-level cut’s root block holds two levels rather than three, so its paths reach a new line one level earlier — two lines by depth 2, where the root-blocked layout is still in its first — and arrive at the leaves with the same three. The stray node at depth 8 costs no extra line in either, since it sits in its parent’s.

What the least product says #

By the strand’s headline number, the fourth layout changes little. At 64 cells its least product is 1.24 against 1.25 blocked from the root — eight cells fewer, a line, makes a hundredth. At 256 it is 1.15 against 1.13, slightly worse. The bottom cut is 1.84 at 64 cells and 1.13 at 256, the second because it is the same layout as the root cut there.

The least product is taken where it falls, and for every heap of 64 or 256 cells it falls at 32 cells of fast memory: four lines, too small to hold any layout of the buffer. There the cache holds the root’s line and little else, every sift misses on every line below the root, and what decides the cost is the number of lines a path crosses — which the full-level cut does not reduce. Density pays only where the heap can stay resident, and that is not where the product is least.

Where the density pays #

With a 256-cell buffer the root-blocked heap moved fewer lines than the array heap up to 64 cells of fast memory and more from 128 up, because its 584 cells do not fit where the array heap’s 256 do. The full-level cut keeps the first half of that and most of the second. At 128 cells of fast memory it moves 125,808 lines against the array heap’s 134,011 and the root-blocked heap’s 158,905 — fewer than either. At 256 cells it moves 87,477 against 75,607 and 120,595, at 512 cells 52,786 against 47,330 and 86,862, at 1,024 cells 38,935 against 37,197 and 51,590.

So the prediction’s third part holds at 128 cells and not above it. From 256 cells up, where fast memory holds the array heap entire, the full-level cut is still a little dearer — it keeps 26% of the root-blocked heap’s excess at 256 cells and 14% at 512 — because 296 cells is still more than 256, and at a memory that just holds the array heap beside the input and the output, forty cells are five lines the cache does not have.

Sixteen nodes in two lines #

The prediction’s first part fails under every layout. At 16 cells the full-level cut occupies three lines, a third of the root-blocked heap’s nine, and its least product is 2.97 — no better than 2.92, and well above the array heap’s 2.35. At 32 cells of fast memory, where every 16-cell family’s least falls, it moves 779,606 lines against the array heap’s 615,412.

The reason is that a 16-node heap laid out as an array is already two lines. The cache at 32 cells holds four, and the array heap’s two stay resident beside the input’s line and the line the bookkeeping cell and the output share, so a sift rarely misses at all; there is no path to shorten, because the whole heap is in memory. Any blocked layout puts the same sixteen nodes in more lines — three is the fewest, since seven nodes and a spare cannot hold more than eight — and the third line is one the cache cannot keep. Blocking exists to shorten paths through a heap larger than the cache, and a heap smaller than the cache is best laid out as densely as possible, which the array already is.

What a layout is matched to #

The earlier essay asked 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. The plates give a sharper answer than either half.

A layout can be matched to every size, and the full-level cut is the match: it never wastes more than the incomplete level’s own share of a line, because the stray nodes ride in cells every block already reserves. What it cannot be matched to is the memory. The array layout is the densest possible and has the longest paths; a blocked layout has the shortest paths and pays in density; and which matters depends on whether the heap fits in the cache. The family’s least product falls at a memory far smaller than any of these heaps, so its winner is the layout with the shortest paths; at memories that hold the heap, the winner is the densest. No layout is best at both, and the full-level cut is the one that comes closest to both at once.

Two lines a superblock met the same divide in a range-minimum index, where packing a superblock’s parts into one record cut a query’s lines and enlarged the structure’s footprint. A layout trades a path for a footprint whenever it pads, and here the padding is a single spare cell a line.

The bound under the numbers #

A floor under a product began this strand with the published bound on sorting’s time times space, $\Omega(n^2)$, and a product paid for in blocks moved it into the cache’s units: counted in block transfers, the floor is about $n^2/B$, and the read-only family meets its shape at every block size because each scan reads the input once in lines. Every product in this essay is that floor’s multiple. The memory a product does not charge added the third quantity the product leaves out, the fast memory a sort needs to run at its transfers, which is why every plate here is drawn against $M$ rather than at one memory.

Read against that floor, the heap layouts move the constant and not the shape. Across the strand the least product has gone from 2.35 to 1.13 by changing only where the buffer’s cells sit, and in this essay by a hundredth or two either way. A family that reads its input $n/S$ times cannot get under the floor’s shape by laying out its buffer better; it can only stop wasting lines. The full-level cut wastes the fewest of any blocked layout measured, and the place it shows is not the headline product but the band of memories, 128 to 1,024 cells at a 256-cell buffer, where a heap either fits or does not.

That band is where a real buffer would usually be. A sort’s buffer is sized to fit the fast memory it is given, not to sit four times larger than it, so the memories at which density decides are the ordinary case and the memory at which the least product falls is the unusual one. By that reading the fourth layout is the better heap for the family even though its least product is not.

What these replays do not cover #

Three buffer sizes, all powers of two. The measured buffers are the earlier essays’, and they are the worst sizes for a heap’s levels. The extent plate runs every size from 8 to 512 and the transfers were replayed only at 16, 64 and 256; a buffer of 255 or 63, a complete heap, would occupy the full-level cut’s cells with no stray node at all.

One cache. Least-recently-used with write-back, lines of eight cells, no prefetching — the two-level model the floor under moving data set its floor in, with a replacement policy rather than the model’s ideal one. A prefetcher would favour the array heap’s sequential heapsort at the end of each scan and leave the sift paths, which are what blocking is for, unchanged.

The overflow lines unused. Every heap measured has a single stray node, so the overflow lines opened when a block’s spare is taken were exercised by the extent plate only.

Still open: a heap whose children share a line #

All four layouts keep a binary heap and move its nodes. The other way to fit a heap to its lines is to change the heap: a heap of fanout eight, whose eight children of a node sit together in one line, so that a sift reads one line a level and descends $\log_8 S$ levels — three for 256 nodes — with the array layout’s density, one cell a node.

The measurement that follows replays the same family with that heap, children of node $i$ at $8i+1$ to $8i+8$ aligned to a line, at the same buffers and memories. The prediction is that at 256 cells its least product falls under the blocked heap’s 1.13, since a path crosses three lines like the blocked layouts’ while the heap occupies 256 cells, and that from 128 cells of memory up it matches the array heap’s transfers; and that at 16 cells it is no worse than the array heap, since two lines hold it. It could fail on the work rather than the lines: a sift in a heap of fanout eight compares a value against all eight children at every level, so a sift of three levels reads 24 cells where the binary heap’s eight levels read 16, and the replay charges every one of them. The question is whether a heap can have the blocked layout’s paths and the array’s density at once, or whether fanout simply moves the cost from lines to the cells inside them.