Ticket map?

Oh, it's that if the type T doesn't have an unused bit pattern that the compiler can choose to represent the nil value, then Optional<T> needs to add an extra byte to its layout, which often results in padding bytes getting added to accommodate the type's alignment.

MemoryLayout<Int>.stride      // ⟹ 8
MemoryLayout<Int?>.stride     // ⟹ 16

By replacing the buffer of optionals with a (partially initialized) unsafe buffer, and a separate bitmap indicating which slots are initialized, we can considerably reduce allocation sizes, often without significantly impacting performance. The bitmap is very compact, so it doesn't take up much space in the CPU cache. (Of course, cold lookups suffer two memory accesses rather than just one.)

For example, a 1024-item buffer of Optional<Int>s needs 16,384 bytes, while an unsafe buffer of 1024 Ints plus a same-sized bitmap only takes 8,192 + 128 = 8,320 bytes -- a mere 50.78% of the space. (Of course, we may need a constant amount of additional metadata to keep track of the bitmap's position etc.)

An example where this is currently used is in the Set implementation -- it uses this exact mechanism to represent its hash table, with both the bitmap and the unsafe elements buffer located in tail-allocated storage of an internal class instance.

5 Likes