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

Question

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

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

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

Answer 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!

Answer 2

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

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

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

Вот relevant discussion on the dev mailing list, отправленный Патрик Уолтон:

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