Каковы накладные расходы по типу Rust Option?

В Rust ссылки никогда не могут быть нулевыми, поэтому в случае, когда вам действительно нужен нуль, например связанный список, вы используете тип Option:

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

Сколько издержек связано с этим с точки зрения распределения памяти и шагов для разыменования по сравнению с простым указателем? Есть ли какая-то "магия" в компиляторе/времени выполнения, чтобы сделать Option без затрат или менее дорогостоящим, чем если бы один из них реализовал Option самостоятельно в неосновной библиотеке, используя ту же конструкцию enum, или обертывание указателя в вектор?

Ответ 1

Да, есть некоторая магия компилятора, которая оптимизирует Option<ptr> для одного указателя (большую часть времени).

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

Печатаются следующие размеры (на 64-битной машине, поэтому указатели составляют 8 байтов):

// 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

Обратите внимание, что &i32, Box, &[i32], Vec<i32> все используют оптимизацию указателей с нулевым значением внутри Option!

Ответ 2

Этот ответ устарел; дискриминант в Option<T> теперь оптимизирован, где это возможно. (Остальная часть предоставленной информации все же интересна.)

В настоящее время тип Option занимает столько же места, сколько и любой другой тип enum. Я не знаю специфики, но это определенно представляется как своего рода дискриминационный союз.

Возможность настройки внутреннего представления для оптимизации рассматривается разработчиками Rust.

Ниже приведено соответствующее обсуждение в списке рассылки Dev, размещенном Патриком Уолтоном:

Я немного сомневаюсь в том, чтобы передать конкретное представление бит enums, так как здесь есть много возможностей для оптимизации компилятора. Для Например, нам может потребоваться свернуть Option<~int> в значение NULL указатель, мы могли бы свернуть Result<(),~str> в значение с нулевым значением строка, или мы можем захотеть свернуть Either<u8,~str> на 1 слово, предполагая, что строки никогда не могут занимать верхние 256 байтов адресное пространство. Некоторое время я думал, что, возможно, лучше всего просто скажите, что битовая диаграмма перечислений ржавчины не определена, чтобы дать нам как можно больше возможностей для игр с оптимизацией.