too-many-lists/bad-stack/layout

[giscus[bot]]

too-many-lists/bad-stack/layout

https://course.rs/too-many-lists/bad-stack/layout.html

[meilin96]

pub enum List {
Empty,
Elem(i32, Box),
}
为什么这里编译器不会进行null指针优化呢,根绝下文的说法,Empty是0,那么非0就是Elem了

[aln8]

你说的对, 这里实际上是有空指针优化的
https://doc.rust-lang.org/std/option/#representation 说明了, 当存在编译器认为0不是一个有效值时, 就会进行null ptr 优化, (i32, Box)这个类型由于Box是一个指针, 不可能为0, 所以会被优化

println!("{} {}", std::mem::size_of::<List>(), std::mem::size_of::<(i32, Box<List>)>());

这个会打印出来 16 16, 表示enum List只占16个bytes

pub enum ListI32 {
    Empty,
    Elem(i32),
}

println!("{} {}", std::mem::size_of::<ListI32>(), std::mem::size_of::<i32>());

这个会打印出来 8 4, 表示enum ListI32占8个bytes, 然而 i32只占 4个bytes, 剩下4个bytes 被ListI32::Empty占用了

[ax7e]

不对啊，8，4不是因为对齐的原因吗，8+max (4,8)=16。

[aln8]

不是的, 是由于ListI32里面的Elem(i32)这个类型有可能为0, 所以无法与Empty的0区分, 所以这里没有空指针优化, 从而有内存对齐给ListI32::Empty分配了4bytes的空间. 内存对齐是Empty向Elem(i32)对齐 4 + max(4) = 8

[ax7e]

谢谢你的回复，我做了一些小的实验，我认为Rust里面是这样计算enum的大小的：

1. 如果可以空指针优化，enum大小等于最大的元素
2. 如果不可以空指针优化， enum大小等于Round(最大的元素+1), 其中Round将大小向上取整到最接近的2的幂次。
3. 我认为enum的实现方式类似于用一个1btype的标记来标记是哪种类型。

‘

pub enum A1 {
    C(u8),
    D(u32),
}
pub enum WithNullPtrOptimization {
    A,
    B(String),
}
pub enum A2 {
    C(u8),
    D(u8),
}
pub enum A3 {
    C(u8),
    D(u16),
}
pub enum A4 {
    C(u16),
    D(u32),
}
pub enum A5 {
    C(u16),
    D(u32),
}
pub enum A6 {
    C(u64, u64),
    D(u64, u64, u64, u64, u64),
}

#[test]
fn test_null_opt() {
    println!(
        "{} {}",
        std::mem::size_of::<WithNullPtrOptimization>(),
        std::mem::size_of::<String>()
    ); // 24 24
    println!(
        "{} {} {} {} {} {}",
        std::mem::size_of::<A1>(),
        std::mem::size_of::<A2>(),
        std::mem::size_of::<A3>(),
        std::mem::size_of::<A4>(),
        std::mem::size_of::<A5>(),
        std::mem::size_of::<A6>(),
    ); //8 2 4 8 8 48
}‘

[Lixuhuilll]

简单测试一下，这样的 Empty 占用的空间是 Empty 和 Elem 中最大的那个

use crate::List::{Elem, Empty};

#[derive(Debug)]
pub enum List {
    Empty,
    Elem(i32, Box<List>),
}

fn main() {
    assert_eq!(
        std::mem::size_of::<List>(),
        std::mem::size_of::<(i32, Box<List>)>()
    );

    println!(
        "Stack Empty runtime size: {}",
        std::mem::size_of_val(&Empty)
    );
    println!(
        "Heap Empty runtime size: {}",
        std::mem::size_of_val(&*Box::new(Empty))
    );

    let end = Box::new(Elem(30, Box::new(Empty)));
    let middle = Box::new(Elem(20, end));
    let head = Box::new(Elem(10, middle));

    println!("{head:?}");
}

[xchrix]

那个null指针优化用Option也可以做：

pub struct List {
    head: Link,
}

enum Link {
    Empty,
    More(Box<Node>),
}

struct Node {
    elem: i32,
    next: Link,
}

换成

pub struct List {
    head: Option<Box<Node>>,
}

struct Node {
    elem: i32,
    next: Option<Box<Node>>,
}

use std::mem::size_of;
assert_eq!(size_of::<Option<Box<Node>>>(), size_of::<Box<Node>>());

这个断言亲测可以过

[SlowSlicing]

这个确实可以，相当于把文中的 enum Link 换成了 Rust 自带的 Option，这两个在结构上是一样的，所以都支持 null 指针优化。

[ARCJ137442]

再提取出个

type NodePtr = Option<Box<Node>>;

就更简洁了：

pub struct List {
    head: NodePtr,
}

struct Node {
    elem: i32,
    next: NodePtr,
}
type NodePtr = Option<Box<Node>>;

use std::mem::size_of;
assert_eq!(size_of::<NodePtr>(), size_of::<Box<Node>>());

[Ryu2u]

pub struct Node{
    elem: i32,
    next: List,
}

enum List{
    Empty,
    More(Box<Node>)
}

我这里没有报error
rust版本 1.66.1

[Jisu-Woniu]

加 pub 的应该是 List，你加错了

[Kev1n3zz]

为什么开头需要举例一个stack -> tuple的例子呢？

[tmtbe]

这里我很诧异，为什么要用枚举而不是直接Option<>,另外使用Option::take比 mem::replace 更清晰些

[minminm]

确实用Option感觉更好，作者用enum可能是为了更清晰的语义吧

[minminm]

而且13.3中“还可以的单向链表”优化为了用option实现

[nihaoqingtuan]

直接看这个给我看懵了