¿Cuál es la sobrecarga del tipo de opción de Rust?

En Rust, las referencias nunca pueden ser nulas, por lo que en caso de que realmente necesite un valor nulo, como una lista vinculada, use el Optiontipo:

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

¿Cuánta sobrecarga implica esto en términos de asignación de memoria y pasos para desreferenciar en comparación con un puntero simple? ¿Hay algo de "magia" en el compilador / tiempo de ejecución para hacer que Optionsea ​​gratis o menos costoso que si uno lo implementara Optionuno mismo en una biblioteca no central usando la misma enumconstrucción o envolviendo el puntero en un vector?

Sí, hay algo de magia del compilador que optimiza Option<ptr>a un solo puntero (la mayoría de las veces).

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>>);
}

Se imprimen los siguientes tamaños (en una máquina de 64 bits, por lo que los punteros son de 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

Tenga en cuenta que &i32, Box, &[i32], Vec<i32>todo el uso de la optimización no anulable puntero dentro de una Option!