Reducing per-allocation overhead: CHUNK_UNIT layout options and tradeoffs

[jlucaso1]

Following up on your note about revisiting the chunk layout to reduce per-allocation overhead. I dug into where the overhead actually comes from and what it would take to cut it, so this is a writeup to gauge the appetite before anyone writes code. No change proposed here yet.

The heap-corruption fix raised the trailing reservation from size_of::<Tag>() (1 byte) to a full word, and v5.0.4 made that explicit. Measured, that costs on average TAIL_SIZE - 1 bytes per allocation, so +7 B on 64-bit and +3 B on wasm32. It's bimodal: most allocations pay nothing, but the ones whose size mod CHUNK_UNIT lands in the top TAIL_SIZE - 1 residues (about 21.9% on 64-bit, 18.75% on wasm32) jump a whole CHUNK_UNIT (+32 B / +16 B). On a small-biased size distribution that's roughly +0.14% / +0.06% overall, so the trailing word itself is small in aggregate.

The dominant overhead for small allocations isn't that word, it's CHUNK_UNIT: a 1-byte allocation occupies a full 32 B (64-bit) / 16 B (wasm32). CHUNK_UNIT is 4 words because a free chunk needs the intrusive Node (2 words), a bin index (1 word), and its size (1 word). So cutting real overhead means shrinking that free-chunk record.

The routes I looked at, with the catches:

• 4 to 3 words (drop the stored bin, recompute from size): 24 B / 12 B isn't a power of two, so the & !(CHUNK_UNIT - 1) mask and the align helpers break and would need real div/mod on the hot path. That trades away the CPU-neutrality the fix just kept. Not worth it on its own.
• 4 to 2 words (singly-linked free list plus dropping the bin): 16 B / 8 B stays a power of two, so the mask survives, and it would roughly halve small-alloc overhead. Two snags though: at 8-byte alignment on wasm32, END_FLAG (bit 3) collides with a now-significant bit of the gap size and would need relocating to a bit that's still always zero; and a singly-linked list makes deregister O(k), which undoes the deallocate speedup. Doable, but a real redesign with a free-path cost.
• Safe building block: dropping the stored bin word alone (recompute via size_to_bin, which is cheap) is a clean, behavior-preserving change. It doesn't shrink the unit by itself (still rounds to the power-of-two 4-word unit), but it frees a word for a future compact layout.

One trick that would recover the full +7 B on 64-bit native is keeping the discriminator at end - 1 there, since a gap size's most-significant byte is zero for any gap below 2^56. But that's a single-byte read again, which is exactly the endianness assumption you removed in v5.0.4, so I don't think it's worth reintroducing for ~0.14% of native memory.

So my read is that the trailing word is about optimal for the current footer-discriminator design, and the meaningful win is a 2-word unit, which means committing to an END_FLAG relocation and a different free-list scheme (or accepting O(k) frees). Worth deciding whether that's appetite-worthy before anyone starts. I can prototype the bin-word removal as a standalone step if you'd like the word freed up first.

[SFBdragon]

(Please flag AI output clearly. I'm aiming to write a CONTRIBUTORS.md file to put some guidelines in place for LLM-heavy contributions.)

Just noting some thoughts down for now:

There's at least one better way to halve CHUNK_UNIT. The free-chunks' Node's next and next_of_prev pointers always point to free-chunk bases, which are always well-aligned. They also are sign-extended at the end. So there's bits to use for flags. Flags can be placed in these pointers for discrimination and to mark tiny chunks, reducing the minimum chunk size and allowing CHUNK_UNIT to be reduced. I don't expect zeroing out the low bits of pointers to impact pointer-chasing performance significantly. I think this should be seriously considered.

This would make it harder to avoid a pointer-size discriminator, but ultimately do a lot more to reduce average per-allocation overhead than a byte-size discriminator solution that required keeping CHUNK_SIZE at 4.

Achieving a sub-usize discriminator with a CHUNK_SIZE of two requires forcing the endianness of pointers or not having two full pointers per free chunk, which I don't really see how to make that work without invalid assumptions or introducing O(n) frees which I don't consider acceptable. bswap is common and fast nowadays, but I forget if it's in the baseline for generic x86_64 builds.

I think we could have a CHUNK_SIZE of 2 and a 1-byte discriminator with O(1) operations and low overhead.

• Small free chunk format: | Node::next: usize [native endianness] | Node::next_of_prev: usize [big endian so low byte is at highest address, lowest bit of highest byte is the "allocated" bit] |
• Normal free chunk format: | Node::next: usize [native endianness] | Node::next_of_prev: usize [big endian] | bucket: u8 | size: usize | ... | size: usize [and flags, big endian to force the low byte to the top] |
• Allocated chunk format: | ... | flags: u8 |
• (Normal free chunks can set the next_of_prev low bit, for an example of how to discrinimate the small and normal format. next_of_prev isn't used for critical pointer-chasing, so requiring an extra zeroing step for de-referencing shouldn't significantly impact performance.)

I'll give this some more thought and check whether bswap is baseline before committing to anything.

Edit: there are some snags. The small format must be detectable from "above" and "below" the gap. I haven't solved that in the above. I think it's doable though.