What a bound is

A heap whose children share a line

Every layout tried for the read-only family's heap buffer moved a binary heap's nodes; the other way to fit a heap to its cache lines is to change the heap. A heap of fanout eight puts a node's eight children together in one aligned line, so a sift reads one line a level, at the array's density of a cell a node. At a 256-cell buffer it brings the family's least transfers × fast memory to 0.885 of n²/B, under the best binary blocking's 1.126 and the array heap's 1.621, as predicted. The predicted cost of the work did not arrive: it reads 45% more buffer cells and writes half as many, 3.6% more in all. But the heap's root sits alone in a line of its own, which every sift reads, and that one line is why it loses to a binary blocking at 64 cells, 1.42 against 1.24, and to the plain array at 16.

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 SS cells costs about n/Sn/S 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 log⁡2S\log_2 S 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 n2/Bn^2/B 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 ii’s children sit at 8i+18i+1 to 8i+88i+8 and that run is aligned to a line, a sift reads exactly one line a level and descends log⁡8S\log_8 S 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 dd-ary heap with one offset. Node jj sits at cell j+d−1j + d - 1 of the buffer, so that the children of node ii, at di+1d i + 1 to di+dd i + d, fill cells d(i+1)d(i+1) to d(i+1)+d−1d(i+1) + d - 1: at d=8d = 8 that is exactly one aligned line, at d=4d = 4 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 M/8M/8 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

A heap of fanout eight reaches a least transfers × fast memory of 0.88 of n²/B with a 256-cell buffer, under the best binary blocking's 1.13 and the array heap's 1.62; at 64 cells it is 1.42 against the blocking's 1.24, and at 16 2.43 against the array heap's 2.35The read-only family on 8,192 random keys, its buffer a max-heap, replayed through LRU with write-back in lines of eight cells: the least transfers times fast memory over n²/B across memories from 16 to 8,192 cells. 16 cells: array heap 2.348 at 32, best binary blocking 2.916 at 32 (blocked from the root), fanout four 2.323 at 32, fanout eight 2.425 at 32; 64 cells: array heap 1.714 at 32, best binary blocking 1.241 at 32 (cut over the complete levels), fanout four 1.390 at 32, fanout eight 1.423 at 32; 256 cells: array heap 1.621 at 32, best binary blocking 1.126 at 32 (blocked from the root), fanout four 1.049 at 64, fanout eight 0.885 at 64.array heapbest binary blockingfanout fourfanout eight16 cells2.352.922.322.4364 cells1.711.241.391.42256 cells1.621.131.050.888,192 keys, lines of 8 cellsleast transfers × memory, n²/B
Fig. 1 The least transfers × fast memory, in n2/Bn^2/B, at buffers of 16, 64 and 256 cells, for the array heap, the best binary blocking, fanout four and fanout eight. At 256 cells: 1.62, 1.13, 1.05 and 0.88.

At 256 cells fanout eight brings the least product to 0.885 of n2/Bn^2/B, 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 fast 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, occupying 584 cells, is 39% above the array heapThe read-only family on 8,192 keys with a 256-cell max-heap buffer: transfers (misses plus write-backs) at each fast memory. array heap: 16 857,390, 32 424,908, 64 271,392, 128 134,011, 256 75,607, 512 47,330, 1024 37,197, 2048 35,242; best binary blocking (blocked from the root): 16 797,013, 32 295,259, 64 190,025, 128 158,905, 256 120,595, 512 86,862, 1024 51,590, 2048 39,100; fanout eight: 16 697,082, 32 275,191, 64 115,977, 128 83,514, 256 63,587, 512 49,479, 1024 39,681, 2048 35,814.fast memory, cells (log scale)transfers, with write-backs (log scale)32,76865,536131,072262,144524,2881632641282565121,0242,048array heapbest binary blockingfanout eightbuffer of 256logarithmic scales
Fig. 2 Transfers against fast memory for the family with a 256-cell buffer kept as the array heap, the best binary blocking (blocked three levels a line from the root) and a heap of fanout eight. At 64 cells of memory: 271,392, 190,025 and 115,977 for the array, the blocking and fanout eight.

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 4% more in all; fanout four touches the fewest cells at every bufferReads and writes of buffer cells over the whole run of the read-only family on 8,192 keys, for max-heaps of fanout 2, 4 and 8: 16 cells, fanout 2: 2,392,552 reads, 302,192 writes; 16 cells, fanout 4: 2,465,058 reads, 225,500 writes; 16 cells, fanout 8: 2,648,584 reads, 197,732 writes; 64 cells, fanout 2: 904,543 reads, 384,092 writes; 64 cells, fanout 4: 972,778 reads, 256,340 writes; 64 cells, fanout 8: 1,134,293 reads, 198,408 writes; 256 cells, fanout 2: 528,364 reads, 401,571 writes; 256 cells, fanout 4: 577,727 reads, 249,947 writes; 256 cells, fanout 8: 767,003 reads, 196,371 writes. A sift in a heap of fanout d reads every child of each node it passes and writes two cells for each level it descends.reads of buffer cellswrites16 cells, fanout 22.69M16 cells, fanout 42.69M16 cells, fanout 82.85M64 cells, fanout 21.29M64 cells, fanout 41.23M64 cells, fanout 81.33M256 cells, fanout 20.93M256 cells, fanout 40.83M256 cells, fanout 80.96M8,192 keysbuffer cells read and written
Fig. 3 Reads and writes of buffer cells over the whole run, for heaps of fanout two, four and eight at each buffer. At 256 cells: fanout two 528,364 reads and 401,571 writes; fanout eight 767,003 and 196,371.

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 50% of the time, eight levels down; fanout eight's end in its last level 72% of the time and the one above it most of the rest, three levels downThe level at which each sift-down during the scans stops, for max-heaps of fanout 2, 4 and 8 with 256 cells, on 8,192 keys: fanout 2: level 0 71, level 1 153, level 2 331, level 3 661, level 4 1,257, level 5 2,570, level 6 5,101, level 7 10,299, level 8 38; fanout 4: level 0 71, level 1 311, level 2 1,271, level 3 5,120, level 4 13,708; fanout 8: level 0 71, level 1 658, level 2 5,064, level 3 14,688. Each sift starts at the root when a value smaller than the root replaces it.share of sifts stopping at each level, root on the leftfanout 2L5L6L7fanout 4L3L4fanout 8L2L3256-cell bufferlevels, root = L0
Fig. 4 The level at which each sift-down stops during the scans of a 256-cell buffer, for fanout two, four and eight. Fanout two: half the sifts end in its last two levels, eight levels down. Fanout eight: 72% in its last level and 25% in the one above.

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 fast memory the 256-cell buffer misses 42,249 times on its own lines as a heap of fanout eight and 101,798 times blocked as a binary heap — the blocking's four second-tier lines alone miss 22,138 times, while fanout eight's root, its eight children and the three lines of grandchildren that have children of their own miss 17,425Misses on each line of a 256-cell max-heap buffer, replayed through LRU at 64 cells (8 lines), the read-only family on 8,192 keys. best binary blocking (blocked from the root): line 0 741, line 1 5501, line 2 5657, line 3 5407, line 4 5573, line 5 5317, line 6 5488, line 7 5335, line 8 5458, line 9 1115, line 10 1022, line 11 954, line 12 955, line 13 927, line 14 929, line 15 947, line 16 950, line 17 878, line 18 881, line 19 934, line 20 933, line 21 913, line 22 911, line 23 931, line 24 934, line 25 885, line 26 885, line 27 934, line 28 935, line 29 905, line 30 903, line 31 892, line 32 898, line 33 872, line 34 873, line 35 935, line 36 940, line 37 932, line 38 933, line 39 848, line 40 849, line 41 870, line 42 873, line 43 888, line 44 886, line 45 884, line 46 884, line 47 876, line 48 875, line 49 845, line 50 849, line 51 878, line 52 877, line 53 854, line 54 856, line 55 892, line 56 891, line 57 853, line 58 855, line 59 862, line 60 862, line 61 861, line 62 862, line 63 859, line 64 861, line 65 878, line 66 875, line 67 866, line 68 867, line 69 839, line 70 841, line 71 886, line 72 883; misses elsewhere 33,856. Fanout eight: line 0 500, line 1 3228, line 2 4613, line 3 4757, line 4 4327, line 5 1024, line 6 1051, line 7 1036, line 8 1017, line 9 1006, line 10 1038, line 11 994, line 12 933, line 13 956, line 14 971, line 15 990, line 16 942, line 17 932, line 18 890, line 19 890, line 20 891, line 21 876, line 22 845, line 23 905, line 24 881, line 25 869, line 26 865, line 27 784, line 28 863, line 29 809, line 30 786, line 31 780, line 32 0; misses elsewhere 33,857. Shallowest heap level on each line, blocking: 0,3,3,3,3,3,3,3,3,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6; fanout eight: 0,1,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3.02e+34e+36e+308162432line of the buffer, from the root'smisses on that linebest binary blocking, blocked from the rootfanout eight256 cells, memory of 64misses a line
Fig. 5 Misses on each line of a 256-cell buffer at 64 cells of fast memory, eight lines, for the best binary blocking and for fanout eight. The blocking’s eight second-tier lines miss about 5,500 times each; fanout eight’s root, children and three interior grandchild lines miss 17,425 times in all.

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 heap of fanout eight moves 197,237 lines at 64 cells of fast memory and 168,518 at 128, against the best binary blocking's 218,027 and 177,459 and the array heap's 235,568 and 177,571; at 1,024 cells the array heap and fanout eight are within 1% of each other and the blocking, occupying 72 cells, is 1% above the array heapThe read-only family on 8,192 keys with a 64-cell max-heap buffer: transfers (misses plus write-backs) at each fast memory. array heap: 16 1,987,100, 32 449,279, 64 235,568, 128 177,571, 256 150,866, 512 138,893, 1024 134,541, 2048 133,490; best binary blocking (cut over the complete levels): 16 1,940,634, 32 325,330, 64 218,027, 128 177,459, 256 155,080, 512 141,854, 1024 135,424, 2048 133,562; fanout eight: 16 1,912,044, 32 373,097, 64 197,237, 128 168,518, 256 150,750, 512 141,572, 1024 136,189, 2048 133,878.fast memory, cells (log scale)transfers, with write-backs (log scale)131,072262,144524,2881,048,5761632641282565121,0242,048array heapbest binary blockingfanout eightbuffer of 64logarithmic scales
Fig. 6 Transfers against fast memory for the family with a 64-cell buffer, kept as the array heap, the best binary blocking (cut over the complete levels) and a heap of fanout eight. At 32 cells of memory the blocking moves the fewest lines; from 64 to 256 cells fanout eight does.

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 dd-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 O(log⁡S)O(\log S) 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 8i+18i + 1 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 objects this essay names

Each one links to every other essay that touches it.

Binary heapBlock transferCache lineConstant factorHeapMemory layout