Misleading example of niche optimization in Day 3: Morning / Smart Pointers / Box / More to Explore

[DmitryMilk]

In the example of niche optimization

#[derive(Debug)]
enum List<T> {
    Element(T, Box<List<T>>),
    Nil,
}

fn main() {
    let list: List<i32> =
        List::Element(1, Box::new(List::Element(2, Box::new(List::Nil))));
    println!("{list:?}");
}

an image of memory layout

 Stack                           Heap
.- - - - - - - - - - - - - - .     .- - - - - - - - - - - - - -.
:                            :     :                           :
:    list                    :     :                           :
:   +---------+----+----+    :     :    +---------+----+----+  :
:   | Element | 1  | o--+----+-----+--->| Element | 2  | // |  :
:   +---------+----+----+    :     :    +---------+----+----+  :
:                            :     :                           :
:                            :     :                           :
'- - - - - - - - - - - - - - '     '- - - - - - - - - - - - - -'

doesn't match real memory layout.

Though niche optimization occurs in this example (enum tag elimination), List::Nil is not represented by "null pointer behind a curtains", but is a full-sized object on a heap, pointed by non-null pointer in a second field of Element(2). So, we still have layout

 Stack                           Heap
.- - - - - - - - - - - - - - .     .- - - - - - - - - - - - - - - - - - - - - - - - -.
:                            :     :                                                 :
:    list                    :     :                                                 :
:   +---------+----+----+    :     :    +---------+----+----+    +------+----+----+  :
:   | Element | 1  | o--+----+-----+--->| Element | 2  | o--+--->| Nil  | // | // |  :
:   +---------+----+----+    :     :    +---------+----+----+    +------+----+----+  :
:                            :     :                                                 :
:                            :     :                                                 :
'- - - - - - - - - - - - - - '     '- - - - - - - - - - - - - - - - - - - - - - - - -'

You can see this if you change the example like this:

#[derive(Debug)]
enum List<T> {
    /// A non-empty list: first element and the rest of the list.
    Element(T, Box<List<T>>),
    /// An empty list.
    Nil,
}

fn main() {
    let list: List<i32> =
        List::Element(1, Box::new(List::Element(2, Box::new(List::Nil))));
    
    let mut iterator = &list;
    loop {
        let addr: *const List<i32> = iterator;
        let size = std::mem::size_of_val(iterator); // size of object, referenced by iterator. not size of reference
        iterator = if let List::Element(value, next) = iterator {
            println!("Element({}) of size {} at {:?}", value, size, addr);
            next
        } else {
            println!("Nil of size {} at {:?}", size, addr);
            break
        }
    }
}

Element(1) of size 16 at 0x7ffcdd2a8c70
Element(2) of size 16 at 0x55a03e5189f0
Nil of size 16 at 0x55a03e5189d0

To reduce memory consumption to only two objects and get a real advantage of niche optimization, example must be like this:

type List<T> = Option<Box<ListItem<T>>>; // niche optimization here

#[derive(Debug)]
struct ListItem<T>(T, List<T>);

fn main() {
    let list: List<i32> =
        Some(Box::new(ListItem(1, Some(Box::new(ListItem(2, None))))));
    println!("{list:?}");
    
    /*
    let mut iterator = list.as_deref();
    while let Some(item) = iterator {
        let addr: *const ListItem<i32> = item;
        let size = std::mem::size_of_val(item);
        println!("iterator points to Element({}) of size {} at {:?}", item.0, size, addr);
        iterator = item.1.as_deref()
    }
    assert!(iterator.is_none());
    println!("iterator is None");
    */
}

Some(ListItem(1, Some(ListItem(2, None))))
/*
iterator points to Element(1) of size 16 at 0x55b4ce6159f0
iterator points to Element(2) of size 16 at 0x55b4ce6159d0
iterator is None
*/

In this example list and iterator are actually just a nullable pointer, where null pointer means None, non-null pointer means Some<Box> or Some<&ListItem>, and memory layout is

 Stack                           Heap
.- - - - - - - .     .- - - - - - - - - - - - - - - - - - - - - - - - - - -.
:              :     :                                                     :
:    list      :     :                                                     :
:   +-----+    :     :    +---------+----+----+    +---------+---+------+  :
:   |  o--+----+-----+--->| Element | 1  | o--+--->| Element | 2 | null |  :
:   +-----+    :     :    +---------+----+----+    +---------+---+------+  :
:              :     :                                                     :
:              :     :                                                     :
'- - - - - - - '     '- - - - - - - - - - - - - - - - - - - - - - - - - - -'

[djmitche]

I agree this in accurate! I wonder if we should simplify the explanation a little by leaving out the linked-list aspect altogether. The crux of the optimization is what you say about the list iterator: Option<Box<T>> is in fact implemented "smart" way: as a nullable pointer, rather than a boolean + pointer. From this perspective, I think the idea is a bit more accessible to a C++ programmer: std::unique_ptr and Box differ because unique_ptr allows null.

Do you want to make a PR to update and simplify this? I am leaning toward leaving it in the speaker notes, but could be convinced to make this a sub-slide of the Box slide ("sub-slide" means something like for and loop under https://google.github.io/comprehensive-rust/control-flow-basics/loops.html).

[DmitryMilk]

Actually this optimization is not a feature of Box, but a feature of enum. And it is already mentioned in a chapter "User-defined Types / Enums / More to Explore".

So, may be like this:

Though Box looks like std::unique_ptr in C++, it cannot be empty/null. This makes Box one of the types that allow the compiler to optimize storage of enums (See '../user-defined-types/enums.html#speaker-notes' "User-defined Types / Enums")

For example, Option<Box<T>> has the same size, as just Box<T>, because compiler uses nullptr-value to discriminate variants instead of using explicit tag.

#[cfg(test)]
mod test {
    use std::mem::size_of_val;

    struct Item(String);

    #[test]
    fn niche_optimization() {
        let a: Box<Item> = Box::new(Item("Just box".into()));
        let b: Option<Box<Item>> = Some(Box::new(Item("Optional box".into())));
        let c: Option<Box<Item>> = None;
        assert_eq!(size_of_val(&a), size_of_val(&b));
        assert_eq!(size_of_val(&a), size_of_val(&c));
    }
}

If all is correct, i'll make PR

[djmitche]

Yeah, that's great. I didn't mean to imply this was a feature of Box :)