Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Need holistic explanation about Rust's cell and reference counted types

Tags:

rust

There are several wrapper types in the Rust standard library:

  • The cells in the std::cell module: Cell and RefCell
  • The reference-counted wrappers, like Rc and Arc.
  • The types in the std::sync module: Mutex or AtomicBool for example

As I understand it, these are wrappers which provide further possibilities than a simple reference. While I understand some basics, I cannot see the whole picture.

What do they do exactly? Do cells and reference-counted families provide orthogonal or similar features?

like image 482
Boiethios Avatar asked Aug 14 '17 12:08

Boiethios


2 Answers

There are two essential concepts in Rust:

  • Ownership,
  • Mutability.

The various pointer types (Box, Rc, Arc) are concerned with Ownership: they allow controlling whether there is a single or multiple owners for a single object.

On the other hand, the various cells (Cell, RefCell, Mutex, RwLock, AtomicXXX) are concerned with Mutability.


The founding rule of Rust's safety is Aliasing XOR Mutability. That is, an object can only be safely mutated if there is no outstanding reference to its interior.

This rule is generally enforced at compile time by the borrow checker:

  • if you have a &T, you cannot also have a &mut T to the same object in scope,
  • if you have a &mut T, you cannot also have any reference to the same object in scope.

However, sometimes, this is not flexible enough. Sometimes you DO need (or want) the ability to have multiple references to the same object and yet mutate it. Enter the cells.

The idea of Cell and RefCell is to permit mutability in the presence of aliasing in a controlled manner:

  • Cell prevents the formation of reference to its interior, avoiding dangling references,
  • RefCell shifts the enforcement of Aliasing XOR Mutability from compile time to runtime.

This functionality is sometimes described as providing interior mutability, that is where an object which otherwise looks immutable from the outside (&T) can actually be mutated.

When this mutability extends across multiple threads, you will instead use Mutex, RwLock or AtomicXXX; they provide the same functionality:

  • AtomicXXX are just Cell: no reference to the interior, just moving in/out,
  • RwLock is just RefCell: can obtain references to the interior through guards,
  • Mutex is a simplified version of RwLock which does not distinguish between a read-only guard and write guard; so conceptually similar to a RefCell with only a borrow_mut method.

If you come from a C++ background:

  • Box is unique_ptr,
  • Arc is shared_ptr,
  • Rc is a non thread-safe version of shared_ptr.

And the cells provide a similar functionality as mutable, except with additional guarantees to avoid aliasing issues; think of Cell as std::atomic and RefCell as a non thread-safe version of std::shared_mutex (which throws instead of blocking if the lock is taken).

like image 173
Matthieu M. Avatar answered Oct 07 '22 01:10

Matthieu M.


Thanks to Matthieu's good answer, here is a diagram to help people to find the wrapper they need:

+-----------+ | Ownership | +--+--------+                              +================+    |                         +-Static----->| T              |(1)    |                         |             +================+    |                         |    |                         |             +================+    |          +-----------+  | Local    Val| Cell<T>        |(1)    +-Unique-->| Borrowing +--+-Dynamic---->|----------------|    |          +-----------+  |          Ref| RefCell<T>     |(1)    |                         |             +================+    |                         |    |                         |             +================+    |                         | Threaded    | AtomicT        |(2)    |                         +-Dynamic---->|----------------|    |                                       | Mutex<T>       |(1)    |                                       | RwLock<T>      |(1)    |                                       +================+    |    |    |                                       +================+    |                         +-No--------->| Rc<T>          |    |                         |             +================+    | Locally  +-----------+  |    +-Shared-->| Mutable?  +--+             +================+    |          +-----------+  |          Val| Rc<Cell<T>>    |    |                         +-Yes-------->|----------------|    |                                    Ref| Rc<RefCell<T>> |    |                                       +================+    |    |    |                                       +================+    |                         +-No--------->| Arc<T>         |    |                         |             +================+    | Shared   +-----------+  |    +-Between->| Mutable?  +--+             +================+      Threads  +-----------+  |             | Arc<AtomicT>   |(2)                              +-Yes-------->|----------------|                                            | Arc<Mutex<T>>  |                                            | Arc<RwLock<T>> |                                            +================+ 
  1. In those cases, T can be replaced with Box<T>
  2. Use AtomicT when T is a bool or a number

To know if you should use Mutex or RwLock, see this related question.

like image 22
Boiethios Avatar answered Oct 07 '22 02:10

Boiethios