[解決済み] RustのOption型のオーバーヘッドとは？

質問

Rustでは、参照は絶対にNULLにできないので、リンクリストのように実際にNULLが必要な場合は Option 型を使用します。

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

単純なポインタと比較して、メモリ割り当てや参照解除のステップなど、どれくらいのオーバーヘッドがあるのでしょうか？コンパイラやランタイムに何らかのマジックがあるのでしょうか？ Option を実装するよりもコストがかからない、あるいはかからないようにするためのマジックがコンパイラやランタイムにあるのでしょうか？ Option を非中核的なライブラリで実装する場合よりもコストがかかりません。 enum を使うか、ポインタをベクターで包むか？

どのように解決するのですか？

そうです、コンパイラのマジックで 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>>);
}

以下のようなサイズが出力されます（64bitマシンなのでポインタは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 !