What is the overhead of type Rust Option?

Question

In Rust, links can never be null, so in the case when you really need null, for example a linked list, you use the Option type:

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

How much overhead is there in terms of memory allocation and dereferencing steps compared to a simple pointer? Is there some kind of “magic” in the compiler / runtime to make Option cost-effective or less expensive than if one of them implemented Option its own in a non-core library using the same enum construct, or wrapping a pointer in a vector?

Answer 1

Yes, there is some compiler magic that optimizes Option<ptr> for 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 zero-pointer optimization within Option !

Answer 2

This answer is outdated; the discriminant in Option<T> now optimized where possible. (The rest of the information provided is still interesting.)

The Option type currently takes up as much space as any other enum type. I don’t know the specifics, but it definitely seems like a kind of discriminatory union.

The ability to customize the internal representation for optimization is being considered by Rust developers.

The following is a relevant discussion on the Dev mailing list hosted by Patrick Walton:

I have little doubt about passing a specific representation of the enums bit, since there are many possibilities for optimizing the compiler. For example, we might need to collapse Option<~int> into a NULL pointer, we could fold Result<(),~str> into a value with a null string, or we might want to roll Either<u8,~str> by 1 word, suggesting that strings can never occupy the top 256 bytes of address space. For a while, I thought it might be best to just say that the rust enumeration bitmap is not defined to give us as many opportunities as possible for optimized games.