What is the null pointer optimization in Rust?

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

I m also learning too many linked list, perhaps this code snippet can deepen your understanding

pub enum WithNullPtrOptimization{
    A,
    B(String),
}

pub enum WithoutNullPtrOptimization{
    A,
    B(u32),
}

fn main()  {
    println!("{} {}", std::mem::size_of::<WithNullPtrOptimization>(), std::mem::size_of::<String>()); // 24 24
    println!("{} {}", std::mem::size_of::<WithoutNullPtrOptimization>(), std::mem::size_of::<u32>()); // 8 4
}

it outputs something along the lines of:

24 24
8 4

You can find an explanation and a list of types for which this optimization is applied in the module level documentation of std::option under Representation:

Rust guarantees to optimize the following types T such that [Option<T>] has the same size, alignment, and function call ABI as T. In some of these cases, Rust further guarantees that transmute::<_, Option<T>>([0u8; size_of::<T>()]) is sound and produces Option::<T>::None. These cases are identified by the second column:

T	transmute::<_, Option<T>>([0u8; size_of::<T>()]) sound?
Box<U> (specifically, only Box<U, Global>)	when U: Sized
&U	when U: Sized
&mut U	when U: Sized
fn, extern "C" fn1	always
num::NonZero*	always
ptr::NonNull<U>	when U: Sized
#[repr(transparent)] struct around one of the types in this list.	when it holds for the inner type

¹: this remains true for any argument/return types and any other ABI: extern "abi" fn (e.g., extern "system" fn)

Under some conditions the above types T are also null pointer optimized when wrapped in a Result.

This is called the "null pointer optimization" or NPO.

It is further guaranteed that, for the cases above, one can mem::transmute from all valid values of T to Option<T> and from Some::<T>(_) to T (but transmuting None::<T> to T is undefined behavior).

null pointer optimization is a special case of "niche optimisation". If the compiler knows a value has a "niche" (a known-invalid bit pattern or patterns), it can use that "niche" to avoid explicitly storing the discriminant of the enum.

Due to alignment requirements, this can lead to substantial memory savings. *const u8 has no niche, so on a typical 64-bit architecture Option<*const u8> is 16 bytes in size, 8 bytes for the *const u8, one byte for the discriminant and seven bytes of alignment padding. &u8 on the other hand has a niche, so Option<&u8> has niche optimisations applied and is only eight bytes in size.

I understand that. But how does the compiler know if all-zeros is an invalid value? I assume the optimization only kicks in for specific built-in types. If so, which ones?

Afaik there are basically three cases.

• For some types like &T the compiler just knows. The compiler just knows that references are never null.
• For some types, the compiler can work it out because it knows the set of valid values. This applies mostly to enums.
• for some types in the standard library, the niche is specified explicitly in the type defintion. Unfortunately it's not possible to do this for custom types in stable rust.