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!

Answer 2

This answer is now obsolete; the discriminant in Option<T> is now optimised out where possible. (The rest of the information provided is still interesting, though.)

For now, an Option type occupies the same amount of space than any other enum type. I don't know the specifics, but it certainly is represented as some sort of discriminated union.

The possibility to tweak the internal representation for optimization is being considered by the Rust developpers.

Here is a relevant discussion on the dev mailing list, posted by Patrick Walton :

I'm a bit hesitant to commit to a particular bit representation of enums, since there's lots of room for compiler optimization here. For example, we might want to collapse Option<~int> into a nullable pointer, we might want to collapse Result<(),~str> into a nullable string, or we might want to collapse Either<u8,~str> into 1 word, assuming that strings can never occupy the top 256 bytes of the address space. I've thought for a while that perhaps it's best to just say that the bit pattern of Rust enums is unspecified, to give us as much room as possible to play with optimizations.