What is the overhead of Rust's Option type?

Question

In Rust, references can never be null, so in case where you actually need null, such as a linked list, you use the Option type:

struct Element {     value: i32,     next: Option<Box<Element>>, } 

How much overhead is involved in this in terms of memory allocation and steps to dereference compared to a simple pointer? Is there some "magic" in the compiler/runtime to make Option cost-free, or less costly than if one were to implement Option by oneself in a non-core library using the same enum construct, or by wrapping the pointer in a vector?

Answer 1

Yes, there is some compiler magic that optimises Option<ptr> to a single pointer (most of the time).

use std::mem::size_of;  macro_rules! show_size {     (header) => (         println!("{:<22} {:>4}    {}", "Type", "T", "Option<T>");     );     ($t:ty) => (         println!("{:<22} {:4} {:4}", stringify!($t), size_of::<$t>(), size_of::<Option<$t>>())     ) }  fn main() {     show_size!(header);     show_size!(i32);     show_size!(&i32);     show_size!(Box<i32>);     show_size!(&[i32]);     show_size!(Vec<i32>);     show_size!(Result<(), Box<i32>>); } 

The following sizes are printed (on a 64-bit machine, so pointers are 8 bytes):

// As of Rust 1.22.1 Type                      T    Option<T> i32                       4    8 &i32                      8    8 Box<i32>                  8    8 &[i32]                   16   16 Vec<i32>                 24   24 Result<(), Box<i32>>      8   16 

Note that &i32, Box, &[i32], Vec<i32> all use the non-nullable pointer optimization inside an Option!