The thread: Space is the other axis — page 5
A spacing priced by what it saves
A two-level select directory spaces each chunk's select samples so that a select steps through about one rank block, whatever that costs in bits, while the path that cuts the chunks makes the bits least, whatever that costs in reads. Charging each chunk its stored bits plus its expected reads at an exchange rate lets the path choose among a spacing of t₀, 2t₀ and 4t₀ chunk by chunk, and sweeping the rate draws points neither fixed spacing reached: on exact copies 3.824 bits a value for 56.8 bits read, where the best before at 60 bits read was 3.875. The prediction's 3.80 for under 60 is missed by a fortieth of a bit. Across the eight sets the priced path lowers the fewest bits at 60 bits read on five; it changes the scattered marks too, which the prediction said one density would leave alone; and at its highest rate it gives up the directory for many small chunks, a point the plain select samples already beat.
What a bound isA heap that keeps its levels in a line
The read-only family of sorts keeps the smallest values not yet output in a buffer, and kept as a max-heap that buffer brought the family's least transfers × fast memory, write-backs charged, to 1.71 of n²/B. A heap laid out so that every three-level subtree sits in one line of eight cells was predicted to write back about 15% of what it reads at its best memory and to bring the product to about 1.5. At a 64-cell buffer it writes back 18% and its product falls to 1.25 — under the 1.29 the sorted buffer reached with no write-backs charged at all, because the blocked layout cuts the reads as well. At 256 cells it reaches 1.13. At 16 cells it is the worst buffer measured, 2.92, because a heap whose last level only begins a block spreads sixteen nodes across nine lines.
What a bound isA heap whose last node is a level
A heap blocked three levels to a line wasted cells at the bottom, and the proposal was to cut the tiers from the leaves instead, so that the partial block sits at the root. Measured on the same buffers, that changes nothing at 256 nodes and makes 16 and 64 worse — 40 and 152 cells where blocking from the root used 72 and 80 — because every buffer measured holds a power of two, which is a complete heap and one node more, and a rule that counts levels counts that one node as a whole level. Cutting the tiers over the complete levels only, and putting the stray node in the spare eighth cell its parent's line always had, brings 256 nodes from 584 cells to 296 and the memories from 128 to 1,024 cells within reach of the array heap. At 16 nodes no layout helps: a heap of two lines has no path to shorten.