zu2: a scan plane node spends 8 bytes on a header that fits in 4, and pays for it twice

[tamnd]

Working out where the scan plane's 58.7 bytes a key go, on #767, turned up a layout that costs 8 bytes a key more than it needs to.

A node in crates/zu2/src/scan.rs is laid out by hand as key length, then height, then one forward pointer per level, then the key:

const KEY_LEN: usize = 0;
const HEIGHT: usize = 4;
const LINKS: usize = 8;

Both header fields are a u32. The height cannot exceed MAX_HEIGHT, which is 20, so it needs 5 bits and is using 32. That is the first four bytes.

The second four are the round up. Arena::alloc rounds every request to a multiple of 8, because the next node's base has to stay 8 aligned for its links to be. A height one node with a go-ycsb key is 8 + 8 + 33 = 49 bytes, which rounds to 56, so seven of those bytes are padding. Take the header down to 4 and the same node is 45 bytes rounding to 48, and the padding is three. Both the four bytes and most of the padding come back.

The header cannot simply shrink where it is, because LINKS would become 4 and the forward pointers would stop being 8 aligned. So the links move to the front:

[8 * height forward pointers][u32: height in 5 bits, key length in 27][key bytes]

The node base is 8 aligned, so link zero is at offset 0 and every link after it is 8 aligned by construction. The header lands at 8 * height, which is 8 aligned and so certainly 4 aligned. The key needs no alignment at all. height_of and key_of both have to read the header before they can find anything else, which they already do, and link gets simpler rather than harder.

Cost of the change: 27 bits of key length is 128 MiB, and a key that long is already past what Options will accept, but the encode should assert rather than truncate.

Effect, weighted by the geometric height distribution at one over four and a 32.9 byte go-ycsb key: the mean node goes from 57.8 bytes to 50.6, so the plane goes from 58.7 bytes a key to about 51.5, 14 percent off. On the server2 million key run that is 56.0 MiB down to about 49.

Worth doing because it is confined to four constants and three accessors, and it does not change the walk: same number of dereferences, same cache lines, one fewer word in front of the pointers the walk actually reads. If anything the walk gets slightly better, since at height one the links and the header now share the first cache line with the start of the key instead of being pushed along by the header.

• Move the links to the front and pack the header
• Assert on a key longer than 27 bits rather than truncating
• A test that the plane's bytes a key drops, measured rather than asserted from arithmetic
• Re-measure the four planes with the new layout and update zu2: what is left of the anonymous budget once the log pages are mapped #767

[tamnd]

Done in bb28e46, with one correction to what this issue proposed.

Links to the front does not work. The header would then sit at 8 * height, and there is no way to read the height without already knowing where the header is. Circular. The reason the old layout put both header fields in front of the links is that the links are the only part of the node whose position does not depend on anything.

So the links go last instead: [u32 header][key bytes][padding to eight][8 * height forward pointers]. The node base is eight aligned and the padding takes the links back to eight aligned from wherever the key ended, and the header stays at offset zero where the key length it holds is what says where that padding ends. Same saving, and link now costs one extra read of a header the walk was already going to read on the same cache line.

One thing this issue got wrong by leaving it out: the saving depends on the key length mod eight. Old size is 8 + round8(len), new is round8(4 + len) + 8h, so a key that is one to four bytes past a multiple of eight saves the whole eight bytes and a key that is five to seven past, or exactly on, saves nothing. Over key lengths in general that is four bytes a node. Over the go-ycsb key set it is more, because usertable:user plus nineteen digits is thirty three bytes and thirty three is one past thirty two: eighty nine percent of the keys save eight and the rest save nothing, so 7.1 bytes a key. The mean node goes 57.8 to 50.6 and the plane goes 58.7 bytes a key to about 51.5, which is what I claimed above, but for a reason narrower than "14 percent off".

• Move the links and pack the header, links to the back rather than the front
• Fail rather than truncate on a key past the twenty seven bits, as Error::KeyTooLong. It cannot fire from a commit, since a record has to fit in a page and a page is 4 MiB against this limit's 128 MiB, but packing two fields into one word without checking is how a wrong answer gets written instead of an error being returned
• A test that measures it. a_node_pays_for_its_key_and_its_links_and_four_bytes_of_header in crates/zu2/tests/scanplane.rs loads sixty thousand thirty three byte keys and asserts the arena holds them in three of its one megabyte chunks. Proved by widening HEADER_LEN back to eight, which reproduces the old arithmetic exactly: the plane holds 4194304 bytes for sixty thousand thirty three byte keys, which is more than the layout says it should
• Re-measure the four planes with the new layout and update zu2: what is left of the anonymous budget once the log pages are mapped #767

The last box waits on a host. Every machine is mid rival benchmark and nothing was built or run on one for this.

Also worth writing down, since it came out of reading the walk for this: nothing ever asks a node its height. A node reached at a level has more levels than that by construction, and find descends rather than counting. The height is still in the header because the length had bits to spare, and link now spends it on a debug assertion that the level is below the node's height, which is the first time that invariant has been checked instead of argued.