Sharing our stack with others

Ok so I’ve wrapped up the third chapter from Too Many Lists. Here’s what I learned:

1. Taking note of the memory footprint of a shared list.
2. Making a single-threaded shared list by switching from Box to Rc.
3. Updating Drop impl to handle the new Rc type.
4. Understanding marker traits, Send and Sync.

Taking note of the memory footprint

Here are some not-so-uncommon operations when working with lists:

list1 = A → B → C → D
list2 = tail(list1) = B → C → D
list3 = push(list2, X) = X → B → C → D

For this, we want our memory to look something like:

                list2
                  ↓
        ╭───╮   ╭───╮   ╭───╮   ╭───╮
list1 → │ A │ → │ B │ → │ C │ → │ D │
        ╰───╯   ╰───╯   ╰───╯   ╰───╯
                  ↑
                ╭───╮
                │ X │
                ╰───╯
                  ↑
                list3

Now, the Box type from previous chapters won’t work coz it can only have one owner.

Here’s the definition of Box<T> from Rust docs:

A pointer type that uniquely owns a heap allocation of type T.

If we want to create list2 from the tail of list1, with Box, the only thing we can do is copy the entire chain B → C → D from list1 to list2.

Switching to Rc

Rc is a single-threaded reference-counting pointer. It counts how many references of the data exist and when the count hits 0, memory is freed. It’s like a lightweight garbage collector.

Multiple lists can point to the same node, and it’s only freed when the last reference is dropped.

Our layout now looks like this:

use std::rc::Rc;

struct List<T> {
    head: Link<T>,
}

type Link<T> = Option<Rc<Node<T>>>;

struct Node<T> {
    element: T,
    next: Link<T>,
}

impl<T> List<T> {
    fn new() -> Self {
        Self { head: None }
    }

    fn prepend(&self, element: T) -> Self {
        Self {
            head: Some(Rc::new(Node {
                element,
                next: self.head.clone(),
            })),
        }
    }
}

Compared to the previous chapter:

• Node<T> is now wrapped in Rc instead of Box.
• We’ve added a prepend() method.

In prepend(), when we’re cloning self.head it doesn’t actually create a copy but only increments the internal reference count. It still points to the same underlying node.

Updating Drop impl

We don’t wanna drop a node when other lists might still be referencing it.

That’s why we’re using Rc::try_unwrap(). It returns the inner value of Rc if it has exactly one strong reference, otherwise it returns an Err.

Err means there are more than one references to the node, so we break out of the loop and let the other list handle the clean up.

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut head = self.head.take();

        while let Some(node) = head {
            if let Ok(mut n) = Rc::try_unwrap(node) {
                // We're the only owner of this node
                // So it is safe to move to the next node
                head = n.next.take();
            } else {
                // Someone else still has a reference!
                // They'll clean it up
                break;
            }
        }
    }
}

Send and Sync traits

These are the two marker traits that control how types can be safely used across threads.

• A type is Send if it is safe to move to another thread.
• A type is Sync if it is safe to share between threads.

For a reference-counted type to be thread-safe, its count needs to be updated atomically. Otherwise, two threads could try to increment the reference count and only one would happen. Then our list could get freed too soon.

Rc uses non-atomic reference counting, so it cannot be sent between threads and consequently it’s neither Send nor Sync. Let’s see what happens if we try to share it between threads.

#[test]
fn thread_safety_test() {
    let mut list = List::new();
    list = list.prepend(1).prepend(2).prepend(3);

    let handle = thread::spawn(move || {
        assert_eq!(list.head(), Some(&3));
    });

    handle.join().unwrap();
}

❯ cargo test
   Compiling too-many-lists v0.1.0 (/Users/mayank/github.com/projects/too-many-lists)
error[E0277]: `Rc<third::Node<i32>>` cannot be sent between threads safely
   --> src/third.rs:90:36
    |
90  |           let handle = thread::spawn(move || {
    |                        ------------- ^------
    |                        |             |
    |  ______________________|_____________within this `{closure@src/third.rs:90:36: 90:43}`
    | |                      |
    | |                      required by a bound introduced by this call
91  | |             assert_eq!(list.head(), Some(&3));
92  | |         });
    | |_________^ `Rc<third::Node<i32>>` cannot be sent between threads safely
    |

It won’t compile!

In Rust we can’t accidentally mess up using a thread-unsafe type across threads.

To make this thread-safe we can replace Rc with Arc.

Arc is similar to Rc except that the reference counts are modified atomically. The disadvantage is that atomic operations are more expensive than ordinary memory accesses.

I’m curious how Arc works under the hood, maybe I’ll write about it in a separate post.

Next, we’re gonna implement A Bad Safe Deque.