performance - ¿Cuál es la sobrecarga del tipo de Opción de Rust?

null-pointer

Question

En Rust, las referencias nunca pueden ser nulas, por lo que, en caso de que realmente necesite valores nulos, como una lista vinculada, use el tipo de Option :

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

¿Cuánta sobrecarga involucra esto en términos de asignación de memoria y pasos para la desreferencia en comparación con un simple puntero? ¿Existe alguna "magia" en el compilador / tiempo de ejecución para que la Option sea ​​gratuita o menos costosa que si uno fuera a implementar la Option por sí mismo en una biblioteca enum utilizando el mismo constructo enum , o envolviendo el puntero en un vector ?

Answer 1

Sí, hay alguna magia de compilación 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> usan la optimización del puntero que no se puede nulos dentro de una Option .

Answer 2

Esta respuesta ahora está obsoleta; el discriminante en Option<T> ahora está optimizado fuera donde sea posible. (El resto de la información proporcionada sigue siendo interesante, sin embargo).

Por ahora, un tipo de Option ocupa la misma cantidad de espacio que cualquier otro tipo de enum . No conozco los detalles, pero ciertamente se representa como una especie de unión discriminada.

Los desarrolladores de Rust están considerando la posibilidad de ajustar la representación interna para la optimización.

Aquí hay una discusión relevante sobre la lista de correo de dev , publicada por Patrick Walton:

Estoy un poco indeciso para comprometerme con una representación de enum en particular, ya que aquí hay mucho espacio para la optimización del compilador. Por ejemplo, podríamos colapsar la Option<~int> en un puntero que puede Either<u8,~str> podríamos colapsar el Result<(),~str> en una cadena anulable, o podríamos colapsar Either<u8,~str> en 1 palabra, suponiendo que las cadenas nunca ocupen los 256 bytes superiores del espacio de direcciones. He pensado por un tiempo que tal vez sea mejor decir que el patrón de bits de las enumeraciones de Rust no está especificado, para darnos el mayor espacio posible para jugar con las optimizaciones.