What is the null pointer optimization in Rust?

In Learning Rust With Entirely Too Many Linked Lists, the author mentions:


However, if we have a special kind of enum:

enum Foo {
    A,
    B(ContainsANonNullPtr),
}

the null pointer optimization kicks in, which eliminates the space needed for the tag. If the variant is A, the whole enum is set to all 0's. Otherwise, the variant is B. This works because B can never be all 0's, since it contains a non-zero pointer.

I guess that the author is saying that (assuming A is 4 bits, and B is 4 bits)

let test = Foo::A

the memory layout is

0000 0000


but

let test = Foo::B

the memory layout is

some 8 bit non 0 value


What exactly is optimized here? Aren't both representation always 8 bits What does it mean when the author claims


It means &, &mut, Box, Rc, Arc, Vec, and several other important types in Rust have no overhead when put in an Option

The null pointer optimization basically means that if you have an enum with two variants, where one variant has no associated data, and the other variant has associated data where the bit pattern of all zeros isn't a valid value, then the enum itself will take exactly the same amount of space as that associated value, using the all zeroes bit pattern to indicate that it's the other variant.

In other words, this means that Option is exactly the same size as &T instead of requiring an extra word.

Stack Overflow Q#46557608, score: 86