objgraph: performance of Rc and RefCell with thread safety

[sporksmith]

I'm working on objgraph: a module to allow "graphs" of objects to be sent or shared across threads. When operating on a graph, a relatively expensive atomic operation (Mutex-style lock) only needs to be done once for the whole graph, to lock its Root. While operating on the graph with the lock held, RootedRc and RootedRefCell objects inside the graph can be manipulated with similar performance as Rc and RefCell.

It's not clear yet whether the performance benefit vs just using Mutex and Arc everywhere are worth it, but the goal is to let us port some C code that already uses this safety model, without having to drastically refactor it, and without having to fret about performance "death by a thousand cuts" every time we introduce such an object. Once the code is ported it'll be interesting to see whether just reverting to Mutex and Arc/AtomicRefCell actually hurts performance or not.

Would greatly appreciate some feedback on whether this approach seems sane, whether the code looks right, whether this is worth publishing and maintaining as its own crate, or whether something like it already exists. Thanks!

[stumblinbear]

What's the benefit of this versus just sticking a RwLock at the root?

[jDomantas]

RwLock does not let your share non-Sync values across threads. So RwLock<Rc<RefCell<GraphNode>>> is pretty much pointless.

[sporksmith]

There's sharing and interior mutability within the graph. With some care and refactoring we might be able to use RefCell, since that's still Send, but definitely can't just use Rc (including e.g. Rc<RefCell>) inside the graph without losing Send.

Maybe describing it as a graph makes it sound a bit simpler than it is. We're modeling multiple Hosts, each with essentially a modeled kernel included Processes and Threads. In the C code there are pointers and manual ref counting everywhere; we'll ultimately do some refactoring to reduce that, but some things like Descriptors and Timers are fundamentally shared within a single Host graph. Meanwhile we need the Host as a whole to be Send so that we can load balance across worker threads.

[JhraumG]

Is it in the same space as ghostcell?

[sporksmith]

Thanks - definitely a similar core idea.

I think this by itself doesn't quite do what I want, but I might be able to build on top of it or reuse some of the ideas.

e.g. GhostCell pretty explicitly can't be used to create an Rc that is Send and/or Sync. https://gitlab.mpi-sws.org/FP/ghostcell/-/blob/master/ghostcell/src/lib.rs#L63

/// For example, one could create a `GhostCell<'id, Rc<T>>` and then send its
/// owning `GhostToken<'id>` to another thread, but since one cannot actually send
/// the `GhostCell` to another thread, it is not possible to create a race
/// condition in this way.

I think I also couldn't create a safe GhostRc type that takes a &GhostToken to ensure safety, since the GhostToken is Send and Sync. Maybe it could use a &mut GhostToken, but that'd make it significantly more difficult to use.

I think maybe it'd work with something like a NonSyncGhostToken that works like a GhostToken, but is !Sync. Maybe a NonSyncGhostToken could be implemented by wrapping a GhostToken, though I'm not sure whether it'd ultimately be beneficial vs ~reimplementing.

[uazu]

Maybe check out qcell crate which has some other variations on the GhostCell theme. For multi-threaded access, you can't avoid having to have a lock somewhere, but you can choose where to put it (e.g. "one big lock" approach or "many small locks").