Add a smart pointer with only strong references count

In some cases, weak reference counting is not needed, Weak count field waste extra memory, This does not satisfy the zero-cost abstraction. Expect additional addition strong reference count smart pointer for stdlib: Sc(Strong count),Asc(Atomic strong count).

2 Likes

This would likely be best done in a third-party crate first; if the crate is very popular, then uplifting to the standard library can be discussed.

2 Likes

Several crate have implemented their own Asc Sc

Examples of such crates would be appreciated.

1 Like

https://crates.io/crates/asc

A better example would probably be triomphe which provides a bunch of Arc based types and doesn't allow for weak references.

4 Likes

(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

Observation: if you care about memory usage enough to care about weak, you probably also want the reference count to be 32 bit number, not 64 bit one.

7 Likes

That's very interesting. I've got to admit, I've never considered that compilation time regressions would be a blocker for improving Rc/Arc. I know that more than a few crates would definitely benefit from being more generic in this area (im is one that comes to mind).

1 Like

To be clear: it's not an unsurpassable blocker. A regression in compile time can be justified if improvements elsewhere compensate for the extra compile time. It's that it's very hard to justify 4% regressions on code using Rc to make Rc marginally better.

I kinda hate to keep saying it, but this kind of falls into "MIR opt fixes this," in that the MIR inliner should be able to reduce the amount of extra IR sent to LLVM. (Investigation in the PR showed that's where all the regression came from.) Now that we've since upgraded LLVM versions and the MIR inliner has gotten better (is it on by default in opt mode yet? I don't recall), it's perhaps worth trying again.

Yeah, that's about what I figured. There is some good news though, as MIR optimizations are coming to 1.65, at least for optimized builds.

Would that make a significant difference, though? There would most likely still be padding to align what follows at 64-bits. However, making both strong and weak counters 32 bits would yield the same memory savings as dropping the weak counter (except on 32-bits targets).

1 Like

I think it is worth mentioning that the folks working with Rust in linux have made some changes to Arc, including getting rid of weak reference counting, and changing the behavior on overflow from abort to saturating the refcount.

1 Like

This is probably a reasonable decision in the kernel (where it's considered better to limp along no matter what rather than crash), but just to explicitly note, this is an unsound change.

Of course, actually triggering the overflow condition is a degenerate case (actually creating the Arc to own the reference would fill up the address space first). But it is theoretically sound to create and then drop usize::MAX Arc (and allocation elision may theoretically make it possible to do so) which if the ref count saturates would lead to UAF.

I believe that once the count gets to usize::MAX, it does not longer get decremented, so essentially the Arc is leaked for soundness.

9 Likes