Comparing `&`, `Box`, and `Rc`

help
1

The book characterises Rc<T> as:

  • A way to share ownership of T, which is different conceptually to sharing access (through a reference),
  • A way to store data in the heap, just as a Box does. However, Box is the only owner. They both implement Drop and Deref.

With that context, I still struggle to see the benefit of using Rc.

Are there examples of practical value where Rc is preferred (beyond the cleaner signature) to &? I first thought there may be cases with DSTs that made a difference, but I think this would affect both cases (& or Rc) equally.

I suppose the references' path could become an obstacle if we have very nested graph structures, although I don't see exactly how. I did write a tiny example, and that was okay.

There is a short Rc tutorial besides the book, but it does not seem to add much either.

2

In your example, try making a function that returns a List.

As-is, your example relies on stack ownership, and the List is only borrowing from that. If you want to be able to move that around, Rc lets the List own its own data, even when shared in multiple places.

3

As usual the question contains an answerr: no, Rc is extremely rarely a good function paramater.

But not all data in your program exist solely to be passed into function.

Kind kinda ssumes that you know about existence of data structures before you start reading it, thus it doesn't provide examples in place where Rc is intorduced. But many complicated data structure couldn't be implemented neither with Box nor with &. There you used Rc for you have no other choice.

4

The important thing to realize here is that types should rarely have associated lifetimes, they make things clunky and unusable (instances have a literal lifetime), so they should be reserved for short lived special purpose types. Most types will want to own rather than borrow their fields.

For example, the list type you provided can't be built and returned from a function (unless the caller itself provides every node as an argument). The structure is recursive so we can't have Cons(i32, List). The next choice is Cons(i32, Box<List>), but this makes cloning the list expensive, every Box requires a new memory allocation and every drop requires freeing the memory, and this is done recursively on each clone.

When Rc is used cloning the list is cheap. Only the Rc owner count needs to be incremented, and even better, only the one on the last node needs updated.

So instead of

// Our Lisp-like, recursive list.
#[derive(Debug)]
enum List<'a> {
    Cons(i32, &'a List<'a>), // indirection to helps define the enum's stack size
    Nil,
}

// Shortcut
use List::{Cons, Nil};

fn make_list<'a>() -> List<'a> {
    let nil = Nil;
    let shared = Cons(10, &nil);
    let a = Cons(5, &shared);
    let b = Cons(3, &a);
    let c = Cons(4, &a);
    c
}

It might look something like this:

use std::rc::Rc;

// Our Lisp-like, recursive list.
#[derive(Clone, Debug)]
enum List {
    Cons(i32, Rc<List>),
    Nil,
}

// Shortcut
use List::{Cons, Nil};

fn make_list() -> List {
    let nil = Nil;
    let shared = Cons(10, Rc::from(nil));
    let a = Cons(5, Rc::from(shared));
    let b = Cons(3, Rc::from(a));
    let c = Cons(4, Rc::from(b));
    c
}
5

The simplest way to think about Rc vs Box is what happens when you clone it. For Box there's no choice: you have to also clone the contained T. But Rc only needs to clone the pointer itself (a no-op) and increment a count.

By itself this only means you save a bit of memory, and in exchange you're not allowed to mutate the contained T (making Rc the & to Box's &mut) - but there's a few cases where this can still be useful. Firstly, some objects like Socket can't be cloned (there's a bit of an asterisk there for handle cloning but it's true enough for this) so you simply need to use something like Rc if you want to share access to it in a persistent data structure, but also you can get back that mutation by adding (for example) a Cell or RefCell to the contained data, meaning this let's you share not just data but state without needing high level synchronization.

On the other hand, it instead needs low level synchronization which makes things really messy, so yes, in general you should prefer the first of &mut, &, Box, or Rc that you can get working.

6

Lets take vector for example. Vector in Rust is equivalent to

struct Vec {
    ptr: NonNull<u8>,
    allocator: Allocator,
    capacity: usize,
    len: usize
}

Then to create it and reference to it is

let vec = Vec::with_capacity(1024)
let reference = &vec

The variable vec contains metadata/the struct above that is saved in stack. The pointer inside the metadata / the first field of the struct above points to a heap memory. The reference contains memory address to vector's stack metadata, not to the heap directly. As a result, the heap can realloc without invalidating the reference because the reference only point to the stack metadata. But as another result, when the reference is shared to other thread, then the current function finish firdt before said thread, the vector's stack metadata will be dropped because stack memory that is dropped after a function exit. Thus, it makes the thread holding a zombie memory addrees aka invalid memory address. Thus it is use after free bug

Box is a way to move the stack metadata above to heap, so it will not be dropped by stack deallocation. But Box also has deallocation. Every heap deallocator is called at the end of the scope, unless it is leaked explicitely with Box::leak or std::mem::forget. So it stills will be dropped at the end of the scope. Comeback to the previous use after free problem

Now Rc is like Box, it moves the stack metadata to heap, then it adds integer counter. Everytime new reference is obtained via clone, it adds the counter. Everytime the reference is dropped, it decrease the counter. It removes the drop at the end of the scope to drop when counter = 0. Because the metadata now in heap and undropped by end of scope, the current function can exit safely without making removing the data. As a result you carry it around to cross function

Now Arc is like Rc, it moves the stack metadata to heap, then it changes from integer counter to atomic counter. If there is new reference that is registered to point to it using clone, the counter increase. If the is registered reference to it that is dropped, the counter decrease. If the counter goes to 0, the memory the Arc hold, the metadata and the heap buffer are dropped, in order to make it works it deactivate the normal dropping memory after the end of the scope, it is moved to dropping memory after the counter touch 0. When the new reference obtained from Arc using clone is created, the counter becomes +1, then said reference is sent to other thread. As a resultz the current function can exit safely without dropping the metadata that is still being pointed by the other thread, because now the metadata is saved in heap and not dropped at the end of the scope. After the other thread is done using the reference, it drops the reference that makes the counter become -1. 0 + 1 - 1 = 0, the counter hits 0, giving signal to Arc that now none point to this data, thus it is safe to drop this data, then the Arc drops the data from heap

Which one is faster?
Pure reference and pointer, &, &mut, *const, *mut

Why Box, Rc, and Arc are slower?

  • It does heap allocation to save the metadata, heap allocation is incredibly slower than atomic. It happens 1 time at the creation, so avoid creating them inside a loop if possible
  • It needs integer counter, but this one is cheap but still additional overhead compared to no counter at all

Edit: I just reread the discussion and realized I misstyped Rc and Arc :< how to think the root problem and the flow is still same :

All heap data structure has metadata saved in stack -> every reference to it only point to this stack metadata's address not to the heap buffer directly otherwise the heap buffer can not dynamically grow safely -> thus makes when the stack exit, they point to invalid address -> comes Box that moves the metadata to heap -> Box still has drop functioning at the end of scope -> comes Rc and Arc that also move the metadata to heap and adds counter as a toggle of when to drop the data

7

I recommend this article on the topic:

8

You use Rc, often in conjunction with RefCell, where plain references don't work.

Here is an example I have been working on recently:

pub fn load_table(&mut self, tid: i64, dt: &Arc<DataType>) -> RTable {...

Here RTable is defined as

pub type RTable = LRc<RefCell<Table>>;

( LRc is basically an Rc, but allocated from thread-local storage rather than global storage ).

9

Rc advantage is that you can use it when you have several users of it and you don't know who is going to end last. this way all of them can access it and the last user clears it up

10

Thanks, this article is helping me understand both questions I asked. I quite liked this sentence:

If there are no other pointers to the value, then you don’t need to worry about invalidating them.

11

Ditto, this article gives a great framing.

I've heard the "unique vs shared" viewpoint a few times, but tying it neatly into Send (UniqueThreadSafe) and Sync (SharedThreadSafe) helped the idea click for me.

Also nice ordering to mention Arc/RwLock first, then give the single threaded version (as opposed to the order I'm used to seeing it presented as: 1. single thread then 2. multi thread)