🎓 A1Learner
🔍
0 of 149 lessons completed

Rust Niche Optimization

Niche optimization is a trick where Option hides its tag in a bit pattern its payload can never hold. Option<&T> therefore costs no extra bytes.

The tag hides in the address 0

A reference can never hold the address 0. Option spends that dead pattern on its None case:

println!("&u32 = {}, Option<&u32> = {}", std::mem::size_of::<&u32>(), std::mem::size_of::<Option<&u32>>>());

A number that promises it is never zero

A plain u32 uses every pattern, so its Option pays for a tag. NonZeroU32 frees the 0 pattern, and the tag moves in:

use std::num::NonZeroU32;
println!("plain = {}, nonzero = {}", std::mem::size_of::<Option<u32>>(), std::mem::size_of::<Option<NonZeroU32>>());

A bool leaves 254 spare patterns

A bool stores its answer in one byte. Only two patterns are real answers. Option needs just one spare pattern for its tag. A u8 has no spare patterns at all, so its Option pays a full extra byte:

println!("bool option = {}, byte option = {}", std::mem::size_of::<Option<bool>>(), std::mem::size_of::<Option<u8>>>());

A char leaves gaps too

A char takes 4 bytes, but many numbers in its range are not real characters. Option uses one of those dead numbers as its tag:

println!("char = {}, Option<char> = {}", std::mem::size_of::<char>(), std::mem::size_of::<Option<char>>());

Enums take the same deal

Give a variant a NonZero payload and the whole enum shrinks. The tag rides in the freed 0 pattern:

use std::num::NonZeroU32;
enum Door { Open, Locked(NonZeroU32) }
enum DoorPlain { Open, Locked(u32) }
println!("with niche = {}, plain = {}", std::mem::size_of::<Door>(), std::mem::size_of::<DoorPlain>());

Example

use std::mem::size_of;
use std::num::NonZeroU32;

enum Door { Open, Locked(NonZeroU32) }
enum DoorPlain { Open, Locked(u32) }

fn main() {
    println!("u32 = {}, Option<u32> = {}", size_of::<u32>(), size_of::<Option<u32>>());
    println!("&u32 = {}, Option<&u32> = {}", size_of::<&u32>(), size_of::<Option<&u32>>());
    println!("NonZeroU32 = {}, Option<NonZeroU32> = {}", size_of::<NonZeroU32>(), size_of::<Option<NonZeroU32>>());
    println!("bool = {}, Option<bool> = {}", size_of::<bool>(), size_of::<Option<bool>>());
    println!("u8 = {}, Option<u8> = {}", size_of::<u8>(), size_of::<Option<u8>>());
    println!("char = {}, Option<char> = {}", size_of::<char>(), size_of::<Option<char>>());
    println!("door with niche = {}, door plain = {}", size_of::<Door>(), size_of::<DoorPlain>());
    println!("Rc = {}, Option<Rc> = {}", size_of::<std::rc::Rc<u8>>(), size_of::<Option<std::rc::Rc<u8>>>());
}

Key points

  • Niche: a bit pattern a type can never hold, such as the address 0 for a reference
  • Option looks for a niche in its payload before it pays for a separate tag
  • The NonZero types exist to offer a niche: they promise their value is never 0
  • References, Box, Rc and function pointers all carry the same niche: none of them can be null
  • Check with size_of before you trust the saving: the trick only fires where a niche truly exists

In this example, eight pairs are weighed side by side. The first pair shows the cost with no niche. A u32 uses every pattern. So Option pays 4 more bytes for its tag. The next two pairs show the trick working. A reference can never be null, so its Option stays at 8. A NonZeroU32 can never be 0, so its Option stays at 4. The bool pair stays at 1, because a bool leaves almost every pattern spare. The u8 pair grows to 2, because a byte leaves nothing spare. The char pair stays at 4, because whole ranges of char values are invalid. The two Door enums repeat the lesson at enum scale: 4 bytes with a niche, 8 without. The last pair shows Rc taking the same deal as every other pointer.

Note

A niche is a promise the type system keeps for you

You never write the tag trick by hand

You only choose types that offer a niche, such as NonZero for ids that start at 1

Try it Yourself

Edit the code, then press Run.

Running is simulated · Rust Playground

Exercise

Option<NonZeroU64> weighs 8 bytes, exactly like NonZeroU64 alone. Why?