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

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

- Dulguun Otgon

---

简述：这是相同的事情。next 被转换为指向 Node 的指针：https://play.integer32.com/?version=stable&mode=debug&edition=2018&gist=d41d7d3ecea770280f3fadc2da0f170a - Boiethios

这两个定义之间确实存在差异。我认为这些差异并未被 https://dev59.com/PGQn5IYBdhLWcg3w36XV 明确覆盖。(例如，有明显的理由偏好 Node2（使用 Option<Box<...>> 的定义），但值得注意的是 Option<Node> 本身比 Option<Node2> 更小，因为前者有一个存储判别式的占位。) - pnkfelix

Answer 1

TL;DR：使用 Node2 更好，因为它避免了在 next 为空时进行堆分配。

为了进一步解释，让我们将问题简化为：哪种方式更好，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 值。这意味着在值为 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。它们都需要相同数量的内存。

assert_eq!(mem::size_of::<Node<()>>(), mem::size_of::<Node2<()>>());
assert_eq!(mem::size_of::<Node<u64>>(), mem::size_of::<Node2<u64>>());
assert_eq!(mem::size_of::<Node<String>>(), mem::size_of::<Node2<String>>());

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

---

完整的代码示例

- linuskmr