Option<Box<T>> 与 Box<Option<T>> 的内存布局。哪一个更好？

Question

假设我有这两个结构

struct Node<T> {
    value: T,
    next: Box<Option<Node<T>>>
}

struct Node2<T> {
    value: T,
    next: Option<Box<Node2<T>>>
}

内存布局有什么区别？哪一个更好？

Answer 1

TL;DR：最好使用它，因为它可以避免在 case isNode2时进行堆分配。nextNone

为了进一步解释，让我们将问题简化为：是Option<Box>还是Box<Option>更好？

首先要注意的是，这两种变体都只存储一个指针：

type VoidPtr = *const ();
let pointer_size = mem::size_of::<VoidPtr>();
assert_eq!(mem::size_of::<Option<Box<i32>>>(), pointer_size);
assert_eq!(mem::size_of::<Box<Option<i32>>>(), pointer_size);

这并不奇怪Box<Option>，因为它实际上是一个指向Option. 但使用的缺点Box<Option>是，即使值为None，Box 也会进行堆分配。

// Although the Option is None, the pointer is not null,
// so a heap allocation is done to store None.
let none_box_option: Box<Option<i32>> = Box::new(None);
let pointer = &*none_box_option as *const Option<i32>;
assert!(pointer.is_null().not());

然而，令人惊讶的是，Option<Box>也只使用一个指针，而不是例如一个指针加一个布尔值来指示所包含的值是否为Some或None。这里使用的技巧（至少在发布模式下）称为空指针优化。空指针用于指示None。每个其他值都是Some指定内存地址处的 a。这导致在值为 None 的情况下不必进行堆分配。相反，该指针将被设置为空。

// A Option<Box> indicates None through a null pointer.
let none_option_box: Option<Box<i32>> = None;
assert!(as_bytes(&none_option_box).iter().all(|&byte| byte == 0));

// A Some Option<Box> simply holds the pointer to the inner value.
let some_option_box: Option<Box<i32>> = Some(Box::new(42));
let inner_bytes = as_bytes(&some_option_box);
let pointer = some_option_box.as_ref().unwrap().as_ref() as *const i32;
let pointer_bytes = as_bytes(&pointer);
assert_eq!(inner_bytes, pointer_bytes);

回到最初的问题：观察到的行为转移到Node和Node2。两者都需要相同数量的内存。

// Although the Option is None, the pointer is not null,
// so a heap allocation is done to store None.
let none_box_option: Box<Option<i32>> = Box::new(None);
let pointer = &*none_box_option as *const Option<i32>;
assert!(pointer.is_null().not());

但是，如果next是None，则将Node进行堆分配，但Node2不会。因此我建议使用Node2.

完整代码示例