Add a smart pointer with only strong references count

libs
7

(This apparently took me over 2h to collect and write... though I did take a significant break in the middle of doing so (and wrote a different post on urlo).)

From keywords:arc, the most notable crates with the primary purpose of providing Rc-ish functionality:

crate weak? librs rank released updated dl/month notable rdeps
ArcSwap :white_check_mark: #3 in Memory management 2018 2022 739,530 Redis, log4rs
Triomphe :x: #21 in Concurrency 2018 2022 283,795 Moka, SWC
arcstr :x: #18 in Concurrency 2020 2022 9,674
servo_arc :x: #218 in Rust patterns 2018 2018 94,581 selectors
hybrid-rc :white_check_mark: #85 in Memory management 2021 2022 - -
elysees :x: #381 in Concurrency 2020 2021 78
asc :x: #334 in Concurrency 2022 2022 21

This also easily misses many internal manual reference counting implementations — at a minimum, I know that rust-analyzer's syntax tree implementation, rowan, uses an internal reference counting implementation derived from triomphe.

I 101% agree with std's decision that having weak references available is the correct default. But there's clearly utility in reference counting without the weak support, especially where cycles are statically prevented by design (i.e. when not holding arbitrary data).

For a good while I've thought wouldn't it be nice to refactor std's Arc and Rc to both share more (any) of their implementation as well as make the weak reference support optional. In concept, it's not too difficult:

#[repr(C)]
struct GenericRcInner<S, T: ?Sized> {
    strategy: S,
    value: T,
}

struct GenericStrongRc<T: ?Sized, S> {
    ptr: NonNull<GenericRcInner<S, T>>,
}

struct GenericWeakRc<T: ?Sized, S> {
    ptr: NonNull<GenericRcInner<S, T>>,
}

// SAFETY: rust-lang/rust#55005
unsafe trait GenericStrongRcStrategy {
    // e.g.
    fn {load, {in,de}crement}_strong_count(&self, ordering: Ordering) -> usize;
    // etc...
}

unsafe trait GenericWeakRcStrategy: GenericStrongRcStrategy {
    // e.g.
    fn {load, {in,de}crement}_weak_count(&self, ordering: Ordering) -> usize;
    // etc...
}

unsafe impl GenericStrongRcStrategy for LocalRcStrategy { /* ... */ }
unsafe impl GenericWeakRcStrategy for LocalRcStrategy { /* ... */ }
struct LocalRcStrategy {
    strong: Cell<usize>,
    weak: Cell<usize>,
}

unsafe impl GenericStrongRcStrategy for SyncRcStrategy { /* ... */ }
unsafe impl GenericWeakRcStrategy for SyncRcStrategy { /* ... */ }
struct SyncRcStrategy {
    strong: AtomicUsize,
    weak: AtomicUsize,
}

type rc::Rc<T> = GenericStrongRc<LocalRcStrategy, T>;
type rc::Weak<T> = GenericWeakRc<LocalRcStrategy, T>;
type sync::Arc<T> = GenericStrongRc<SyncRcStrategy, T>;
type sync::Weak<T> = GenericWeakRc<SyncRcStrategy, T>;

(although std would likely use newtypes rather than type aliases.) I think have a partial draft on a drive somewhere... The interesting part is to how to handle the optional presence of the weak count; I don't recall if I've found a nice solution yet. (Every time I consider this[1] I come up with potential ideas, though.)

However, changing the implementation of Rc/Arc has a potentially surprisingly large impact on (measured) compiler performance, because it leads to a significant amount of more IR to process (and remember, generics are instantiated a lot of times, magnifying the cost). The most recent attempted change to Rc I recall was an attempt to use a prefix allocator, so you could use Box<T, RcAllocator> and have a zero-alloc conversion to Rc, providing "UniqueRc" functionality in a very clean way. Unfortunately, changing the allocation path like that had an outsized impact on compile time and so wasn't merged at that point, though roughly everyone agrees that it'd be a good idea in theory.

  1. Trying very hard not to get nerd sniped into making yet another lib that's not going to get used... ↩︎

12 Likes