Rc<RefCell<T>> vs Arc<Mutex<T>>, and the arena that beats both

Compute the depth of every node in a rooted tree — twice, two different ways, and check that they agree.

pub fn tree_depths(edges: Vec<(usize, usize)>, threads: usize) -> Vec<usize>

edges are (parent, child) pairs; node 0 is the root and has depth 0; every node is reachable. Return depths indexed by node. No edges means a single node, so [0]. Treat threads == 0 as 1.

You must write both implementations:

1. An index arena. No smart pointers of any kind — a Vec<Vec<usize>> of children and a BFS. Single-threaded.
2. Shared, individually-locked nodes, walked level by level across threads workers.

Then assert_eq! the two before returning. The assertion is part of the required code: it is what turns “I read that the arena is better” into “I built both and they agree”.

Why this problem exists

Learners meet Rc<RefCell<T>> in the Book’s graph chapter, then meet strong opinions against it online with no framework for adjudicating. A course that takes a defensible position and shows the alternative side by side is worth more than either dogma.

The starter’s error

It uses Rc<RefCell<Node>>, exactly as taught, and the moment threads appear:

error[E0277]: `Rc<RefCell<Node>>` cannot be shared between threads safely
   = help: the trait `Sync` is not implemented for `Rc<RefCell<Node>>`

Two independent reasons, and it is worth naming both because they are different failures:

• Rc has a non-atomic refcount. Two threads cloning at once race on it: too low and the value is freed while alive, too high and it leaks.
• RefCell has a non-atomic borrow flag. Two threads calling borrow_mut() at once could both see “not borrowed” and both hand out a &mut. Aliased mutable references are instant undefined behaviour.

The mechanical fix is Arc<Mutex<Node>>, or here — since the nodes live in a Vec that outlives the scope — just Mutex<Node> shared by reference, which is cheaper.

Notice that this is not the compiler being awkward. Every one of those types is doing exactly what it advertises, and the type system is reporting a real difference in what they guarantee.

When each shape is right

Rc<RefCell<T>> is a perfectly good tool. Single-threaded graph-shaped data, a GUI widget tree, an interpreter’s environment chain, anything where the ownership genuinely is a DAG and the program has one thread. It is cheaper than the threaded version: a non-atomic increment beats an atomic one, and a borrow-flag check beats a lock.

Its real costs are not the ones people usually cite:

• borrow_mut() panics at runtime if the value is already borrowed. You have moved a compile-time check to a runtime one, and the failure appears under a code path you did not test.
• Cycles leak. Rc is reference counting with no cycle collector, so a parent holding children who hold parents never frees. Weak for back-edges is the fix, and remembering it is on you.
• It is infectious: once the data is behind Rc<RefCell<_>>, every function that touches it inherits the ceremony.

Arc<Mutex<T>> buys thread-safety and pays with an atomic refcount, a lock per access, poisoning, and a lock-ordering obligation the moment you need two nodes at once.

And the arena beats both

Which is why you wrote it first.

let mut children: Vec<Vec<usize>> = vec![Vec::new(); n];

Nodes are usize indices. Look at what simply stops being a problem:

• no reference counting — the arena owns everything, and it all drops at once;
• no cycles to leak — an index is not an owning edge, so a cyclic graph is just a normal Vec;
• indices are Copy, so passing a node around costs nothing and borrows nobody;
• cache locality — one contiguous allocation instead of n scattered ones, which for a traversal is often the whole performance story;
• and it parallelises trivially, because disjoint index ranges are disjoint, as the previous problems in this track kept demonstrating.

The cost is real and worth stating: an index carries no type safety. arena[i] where i came from a different arena is a silent bug — which is what generational indices exist to fix.

::: question Your tree needs parent pointers as well as child pointers. What happens with each of the three designs? Rc<RefCell<Node>> — a straight Rc parent pointer creates a cycle and leaks the entire tree. The fix is Weak<RefCell<Node>> for the parent edge, plus an upgrade() returning Option at every use. It works, and every traversal now carries a None case that cannot actually happen.

Arc<Mutex<Node>> — the same leak, the same Weak fix, plus a new hazard: walking down through a child while another thread walks up through a parent is two locks acquired in opposite orders. That is the deadlock from earlier in this course, arriving through a data-structure change nobody thought of as a concurrency decision.

The arena — add a parent: usize field. That is the whole change. There is no cycle, because an index is not an owning edge; there is nothing to upgrade; there is no second lock.

This is the strongest argument for the arena, and it is not about performance: the pointer-based designs make cyclic references a memory-management problem, and the arena makes them a non-event. :::

The lints in this neighbourhood

• clippy::rc_mutex flags Rc<Mutex<T>>, which is almost always a confusion — single-threaded ownership around a thread-safe lock. It is restriction, so off by default.
• clippy::arc_with_non_send_sync flags Arc::new(x) where x is neither Send nor Sync: such an Arc can never cross a thread boundary, so you paid for atomic refcounting for nothing. On by default.
• clippy::redundant_allocation catches Arc<Box<T>> and friends.
• clippy::type_complexity will eventually object to nested wrapper types. The fix is a type alias, not an #[allow] — and if the alias is hard to name, that is a signal about the design.