What is the null pointer optimization in Rust?

Question

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

Answer 1

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<&T> is exactly the same size as &T instead of requiring an extra word.

Answer 2

enum is a tagged union. Without optimization it looks like

Foo::A;    // tag 0x00 data 0xXX
Foo::B(2); // tag 0x01 data 0x02

The null pointer optimization removes the separate tag field.

Foo::A;    // tag+data 0x00
Foo::B(2); // tag+data 0x02