A heap whose children share a line
The read-only family of sorts never writes to its input. It scans the input repeatedly, keeping in a small buffer the smallest values it has not yet output, and outputs the buffer at the end of each scan; a buffer of cells costs about scans. The strand of essays pricing that family in cache lines has spent four essays on the buffer. The lines a sort writes back found that a sorted buffer writes back most of the lines it reads, because each insertion near the front shifts everything after it. A buffer that does not shift its tail made the buffer a max-heap, which touches one path of about cells an insertion. A heap that keeps its levels in a line laid that heap out three levels to a line, and a heap whose last node is a level cut those blocks over the heap’s complete levels and gave the stray last node a spare cell.
All four kept a binary heap and moved its nodes. The measure throughout is the least product of transfers and fast memory over a grid of memories — the product a product paid for in blocks set its floor in, with the fast memory that the memory a product does not charge added to it — in units of for 8,192 keys in lines of eight cells, write-backs charged. At the end of the last essay the best binary layouts stood at 2.92, 1.24 and 1.13 for buffers of 16, 64 and 256 cells, against the array heap’s 2.35, 1.71 and 1.62. At 16 cells no blocking helped: a heap of two lines has no path to shorten.
That essay’s closing section proposed changing the heap rather than its addresses. In a heap of fanout eight every node has eight children, and if node ’s children sit at to and that run is aligned to a line, a sift reads exactly one line a level and descends levels — three for 256 nodes, the same number of lines a blocked binary path crosses — while the heap occupies one cell a node, as the array does. The predictions: at 256 cells a least product under the blocked heap’s 1.13; from 128 cells of memory up the array heap’s transfers; at 16 cells no worse than the array heap. The named risk was the work. A sift in a heap of fanout eight compares the value against all eight children at every level, so three levels read 24 cells where the binary heap’s eight levels read 16, and the replay charges every one of them.
Eight siblings in one line
The layout is the textbook -ary heap with one offset. Node sits at cell of the buffer, so that the children of node , at to , fill cells to : at that is exactly one aligned line, at exactly half of one. The root sits alone at the end of the buffer’s first line, and the seven cells before it are empty. A heap of 256 nodes occupies 263 cells, against 584 for the blocking from the root and 296 for the cut over the complete levels.
Everything else is the earlier essays’. The family scans 8,192 keys in random order; at every key it reads the input cell and a bookkeeping cell, compares the key with the root, and on a smaller key replaces the root and sifts down, reading every child of each node it passes and writing the two cells of every swap. At the end of a scan the buffer is heapsorted in place with the same sift, and output in order. The trace goes through an LRU cache of lines with write-allocate and write-back, and transfers are misses plus lines written back. The keys come out in order, the number of scans is the binary heap’s exactly — the buffer holds the same smallest values whatever its shape — and every family of siblings at fanout eight lies in one line; those three things are checked on every run.
The least product at three buffers
At 256 cells fanout eight brings the least product to 0.885 of , under the best binary blocking’s 1.126 by a fifth and under the array heap’s 1.621 by nearly half; at 64 cells it reaches 1.423, under the array heap’s 1.714 and over the complete-level cut’s 1.241; at 16 cells it is 2.425, over the array heap’s 2.348. Fanout four sits between them everywhere but at 16, where it is the best buffer of any shape measured, 2.323. The plate is the whole result in three rows, and the rest of this essay is about why each row comes out as it does: the first prediction holds at 256 cells, the third fails at 16, and the middle buffer is where the two kinds of layout trade places.
The prediction at 256 cells, and past it
With a 256-cell buffer the heap of fanout eight moves 115,977 lines at 64 cells of memory and 83,514 at 128, against the best binary blocking’s 190,025 and 158,905 and the array heap’s 271,392 and 134,011; at 1,024 cells the array heap and fanout eight are within 7% of each other, and the blocking is 39% above the array heap. The first prediction holds by a wide margin: the least product falls under the blocking’s 1.13 not by a little but to 0.885, and it is reached at 64 cells of memory, where the binary layouts reached theirs at 32.
The second prediction was wrong in the more useful direction. It expected the heap of fanout eight to match the array heap’s transfers from 128 cells of memory up, on the reasoning that a memory of sixteen lines holds most of a 33-line heap, as it holds most of the array heap’s 32. At 128 cells it moves 38% fewer lines than the array heap. The two meet only from 512 cells, where every layout’s heap is resident and what is left is the input, read once a scan, and the write-backs of the output; there fanout eight is 4.5% over the array heap at 512 and 6.7% over at 1,024, because its heapsort at the end of each scan reads eight children a level where the array reads two, and from 1,024 cells of memory reads are what remain.
The blocked layouts never caught the array heap at large memories either. A heap that takes 584 cells to hold 256 nodes needs more memory to keep resident than one that takes 256, and the blocking from the root moved 51,590 lines at 1,024 cells against the array’s 37,197. Fanout eight sits between them there, at 39,681 — it is dense, but it does more reading.
The work that did not arrive
The risk was the work, and it does not arrive: at 256 cells the heap of fanout eight reads 45% more buffer cells than the array heap and writes 51% fewer, so its buffer accesses come to 3.6% more in all; fanout four touches the fewest cells at every buffer. The proposal counted only reads. A sift in a binary heap reads two children a level and, on almost every level it passes, swaps — two writes. Over eight levels that is sixteen reads and sixteen writes. A sift in a heap of fanout eight reads eight children a level and swaps two cells, over three levels: 24 reads and six writes. Thirty-two accesses against thirty, close to even, and the replay’s total, 3.6% more for the wide heap, is close to even too. The binary heap’s sift is a long sequence of cheap decisions, each followed by a move; the wide heap’s is a short sequence of expensive decisions with few moves.
The same accounting runs at every buffer. At 64 cells fanout eight reads 25% more and writes 48% fewer, 3.4% more in all; at 16, where the heap is two levels deep at both fanouts and there are fewer levels to save, 5.6% more. Fanout four is the balance point the arithmetic predicts: four reads and two writes a level over four levels, 24 accesses a sift, and it touches the fewest cells at all three buffers — 827,674 at 256 against the array heap’s 929,935.
The writes matter more than their count suggests, because in this model a written line costs twice: once when it is brought in and once when it is evicted dirty. At 256 cells and 64 cells of memory, fanout eight writes back 39,871 lines and the blocking 54,371. Halving the swaps halves the dirty lines a sift leaves behind it, and a family that sends back fewer lines needs less memory to hold the ones it is still writing.
Almost every sift reaches the bottom
Almost every sift goes to the bottom: of 20,481 sifts during the scans of a 256-cell buffer, the array heap’s end in its last two levels half the time and in its last three three-quarters of the time; fanout eight’s end in its last level 72% of the time and in the level above it a quarter. The plate is why the arithmetic of the last section holds. A key that replaces the root is smaller than the root, the largest value in the buffer, and on random input it is usually smaller than most of the buffer, so it sinks nearly all the way. A sift’s cost is close to its heap’s full depth, and depth is what fanout buys down.
It also shows a detail of the layout that turns out to matter. A heap of fanout eight with 256 nodes is not three full levels: it has 1, 8, 64 and then 183 nodes, and the 183 hang from only 23 of the 64 nodes on the third level. The other 41 third-level nodes are leaves, which is why a quarter of sifts stop there. In lines, the heap’s first five lines — the root’s, the line of its eight children, and the three lines of grandchildren that have children of their own — are the whole of its interior. Every sift that goes on to the fourth level passes through those five and ends in one of the 23 lines below.
Five lines a memory can keep
At 64 cells of memory the 256-cell buffer misses 42,249 times on its own lines as a heap of fanout eight and 101,798 times blocked three levels a line from the root — the blocking’s eight second-tier lines alone miss 43,736 times, while fanout eight’s five interior lines miss 17,425. This is the mechanism the least products report. A memory of eight lines must hold the input’s current line, the bookkeeping cell’s line and whatever part of the heap every sift passes through. The binary blocking’s root line leads to eight second-tier lines, each three levels deep, and nine lines of interior do not fit in eight; the LRU evicts a second-tier line between the sifts that use it, and every sift pays for it again. Fanout eight’s interior is five lines, which fit beside the input and the bookkeeping; they miss about six times in ten sifts between them, and most of what a sift misses is the leaf line it ends in.
The bottom of each heap tells the density half of the story. The binary blocking spreads its last tier over 64 lines, three nodes and five empty cells in most of them, because blocks of a 256-node heap blocked from the root leave its incomplete last level almost empty; its misses there were 57,321. Fanout eight’s bottom is 28 lines, full but for the last, and missed 19,690 times. The prediction’s premise — the blocked layout’s paths at the array’s density — was right, and the plate shows each half doing its share.
What the plate also shows, at its far left, is the line that costs fanout eight elsewhere. Line 0 holds one node. At a 256-cell buffer that does not matter, because the root’s line is read by every sift and never leaves the cache; it occupies one of the eight lines of memory and earns it. At smaller buffers it is a whole line of a path that has very few.
A lone root at sixty-four cells
With a 64-cell buffer the order changes: at 32 cells of memory, where every layout reaches its least product, the complete-level cut moves the fewest lines, and fanout eight’s least product is 1.42 against the cut’s 1.24 — while from 64 to 256 cells of memory fanout eight moves the fewest, and from 512 the array heap does. A 64-node heap of fanout eight is a root, eight children and 55 grandchildren: three lines on every path to a leaf, one of them holding nothing but the root. The complete-level cut holds a 64-node binary heap as a seven-node top block and eight blocks of seven beneath it, two lines on every path, at 72 cells against 71. Same density, one line fewer a sift, and at a memory of four lines that one line is the difference between keeping the top of the heap and losing it.
At 16 cells the same arithmetic runs the other way round. The array heap’s 16 cells are two lines; fanout eight’s 16 nodes occupy 23 cells, three lines — the root’s, its children’s and the seven grandchildren’s — and its least product is 2.425 against the array heap’s 2.348. The prediction that it would be no worse there was wrong by three per cent, and wrong for a reason the proposal could have seen: alignment costs the root a line, and at sixteen nodes a line is a third of the heap. Fanout four, whose root shares its line with three empty cells and its first four children, holds 16 nodes in 19 cells, two lines on most paths, and is the best buffer of any shape at 16 cells, 2.323.
So the comparison the strand set out to settle has a shape rather than a winner. Below about four levels of binary heap no layout beats two lines and the array is as good as anything; at sixty-four cells a binary heap cut over its complete levels is shortest in lines; at 256 the wide heap’s narrow interior and its density both count, and it is best by a fifth.
What fanout moves and what it does not
Building a heap from the bottom counted comparisons and found that the textbook’s worst cases rarely describe what a heap does on random input; this strand has been counting lines, and the same caution applies to the folklore about wide heaps. The usual argument for a -ary heap is that it trades comparisons for levels, and is worth it when a level is expensive — a statement about the constant the notation drops, since every fanout is the same a sift. The plates here say the trade is not comparisons for levels but writes for reads: a wide sift makes the same number of decisions in fewer moves, and in a model that charges a dirty line twice, moves are what a level costs.
Permuting is the harder problem here made the general point about this model, that its unit is the block and that an algorithm’s fit to the block decides its cost more than its operation count does. A heap whose siblings fill exactly one block is the most literal version of that fit: the line is the unit of a sift’s decision, and every child a line holds is read for the price of one. What it does not change is the depth of the first level. Every rooted structure has one root, and at fanout eight a line built for eight siblings holds it alone.
What the measurement leaves out
One family, three buffers, one line size. 8,192 random keys, buffers of 16, 64 and 256, lines of eight cells. A line of sixteen cells would make the natural fanout sixteen and move every boundary above.
An LRU with write-back and nothing else. No prefetching, no associativity, and no account of the comparisons as time; the work plate counts cell accesses, which the cache sees, not instructions.
Fanouts two, four and eight only, each with its siblings aligned. A fanout that does not divide the line, or siblings deliberately split across lines, were not measured.
Still open: a root that shares its children’s line
The heap of fanout eight loses at 64 and 16 cells by one line: its root’s. The repair is to let the root be different from every other node. Give the root seven children instead of eight and put them in its own line, root first — a line of eight cells holding the root and its seven children — and below them keep fanout eight, each of the seven nodes’ eight children in a line of their own. A sift then reads one line for the top two levels and one line a level after that; a 64-node heap becomes a root, seven children and 56 grandchildren in eight lines, two lines on every path, at 64 cells exactly.
The measurement that follows replays the same family with that heap at the same buffers and memories, and the prediction is that it removes the loss without giving up the gain: at 64 cells a least product at or under the complete-level cut’s 1.24, at 16 cells at or under the array heap’s 2.35, and at 256 cells within a few per cent of fanout eight’s 0.885, since its interior shrinks by the root’s line. It could fail on the root’s fanout. A root with seven children shifts every node’s index, so the clean arithmetic of becomes an offset by one level, and the root’s line is now read for eight cells at every sift rather than one, which the replay charges. The question is whether the one node every path shares can be folded into the line below it, or whether a structure with a root always spends a line on it somewhere.
Named alongside this one
Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.
- The lines a constant-time query lands in cache line · constant factor · memory layout
- A cache the listings share cache line · memory layout
- A lookup that stops caring how wide an entry is cache line · memory layout
- Eight cells at once cache line · memory layout
- Runs twice as long as memory block transfer · heap
- The order with the best depth constant factor · memory layout
The objects this essay names
Each one links to every other essay that touches it.
Binary heapBlock transferCache lineConstant factorHeapMemory layout