Does anybody tried merge Rc and Arc?

Now we know Rc and Arc split for performance boost, we totally do not have to use Arc in single threads. But what if in a case where we have a bunch of Arc, most of which stay on single threads, only a few possibly cross threads in the future? We have to use Arc uniformly rather than Rc just for that few.
I have an opinion. By reading the source code of stdlib we know inside Rc and Arc is a pointer of RcBox and ArcInner, respectively.

struct RcBox<T: ?Sized> {
    strong: Cell<usize>,
    weak: Cell<usize>,
    value: T,
}

and

struct ArcInner<T: ?Sized> {
    strong: atomic::AtomicUsize,
    weak: atomic::AtomicUsize,
    data: T,
}

so how about merge them into one?

enum Counter {
    Local {
        strong: Cell<usize>,
        weak: Cell<usize>,
    },
    Atomic {
        strong: AtomicUsize,
        weak: AtomicUsize,
    },
}

struct Inner<T: ?Sized> {
    // mutates only when upgrading Rc to Arc.
    // upgrading can only happen in a single thread.
    counter: UnsafeCell<Counter>,

    data: T,
}

struct Rc<T: ?Sized>(NonNull<Inner<T>>);
struct Arc<T: ?Sized>(NonNull<InnerT>>);

unsafe impl<T: ?Sized + Send> Send for Arc<T> {}
unsafe impl<T: ?Sized + Sync> Sync for Arc<T> {}

The new defined Rc and Arc act similar, except Arc implements Send and Sync, Rc can upgrade to Arc.

When an Rc is asked to upgrade to Arc, it mutates Counter::Local to Counter::Atomic (if already is Counter::Atomic just simply act like cloning a Arc), strong count plus 1, weak count stay the same, leave original Rc unchanged, and return a new Arc, proved the counter has been changed to atomic types. This can be done because upgrading only happens in single thread, there is no data racing exists. After that we have Rc and Arc pointed to the same memory.

I haven't implemented such Rc and Arc because it is time-consuming, but it is theoretically feasible. Is there somebody who has done this, or is this unsound? Thanks.

1 Like

Interesting.

It incurs a cost to Rc at least (always checking which variant it is). Once you convert one Rc, all your Rc are slower than your Arc (act like Arc after branching on the variant).

Scenario Rc today Arc today Convertable hybrid
I never need Arc What you'd use today Slower than Rc, no benefit Slower than Rc, and no benefit
I always need Arc n/a What you'd use today No faster, maybe just as fast as Arc, but no benefit
I sometimes need Arc n/a What you'd use today Always slower than Rc; maybe faster than Arc until you convert one, at which point slower than Arc for all things that remain Rc

I'd say it doesn't really help for the scenario you presented ("I only convert a few Rc to Arc") but instead helps the scenarios "I don't know if I need Arc until runtime, but I usually don't" and "I need Arc, but only near the end of my runtime". It hurts the "I never need Arc" scenario.


If the idea was to do this in std, I doubt it's compelling enough. It would also be a breaking change to platforms without AtomicUsize.

7 Likes

Thanks for your reply.

My scenario is similar to this, maybe I explained unclear before. :sweat_smile:
I'm implementing a runtime, which has a method that makes a handle, cloning one preserved inside the runtime, one gives outside of the function, let the user use it. I'm sure users outside may fewly put it into other thread, but which is still expected.
So the only difference is I don't know if I need Arc, but the user does.

Of course. My scenario is in the minority.

Besides, if I tested correctly, AtomicUsize is much slower than usize, approximately five times or more. So I think making this automatic-converting Rc make sense.

1 Like

I wrote this: https://crates.io/crates/darc
(but haven't given it serious thought since then)

2 Likes

Note that there's a subtle difference between Rc and Arc beyond just thread safety: Arc aborts the process when surpassing isize::MAX clones, but Rc doesn't until overflowing usize::MAX.

What it sounds like you want isn't a runtime dynamic conversion between Rc and Arc, but to be generic between the choice of the two. One crate providing an approach for this is archery.

I've also considered using radium's approach to write a "strategy" generic Rc, but never really gotten around to it. (I would also want to make Weak support optional, which makes the task more involved.)

1 Like

My catchall go-to solution for these kinds of problems is delegating the decision to the user. It should be easy enough with generic parameters, at the minor cost of some boilerplate. A marker trait and some public type aliases can help, though. E.g.: Rust Playground [1]

This is obviously a contrived example, but hopefully it is illustrative of the point.


  1. I updated the example to use a marker trait to implement a generic getter method. With a more complete Foo type, other methods would make a whole lot more sense. ↩︎

Thanks. The idea is almost the same as I said, seems work.
But I don't understand what PhantomData here for? inner has already used type parameter T isn't it?

pub struct Rc<T: ?Sized> {
    inner: NonNull<Inner<T>>,
    phantom: PhantomData<T>,
}

Drop checking probably.

Note that while the reference currently says it's not necessary, part of RFC 1238 was reserving the right to require it again, and no team ratified the change to the reference (which is explicitly non-normative) nor promised not to require it, so the responsible thing to do is to follow the original text IMO.

2 Likes

Thanks for your suggestion.

Uh... partly no. Even though it's not dynamically decided, I need to preserve a copy of handle inside my runtime, in a vector if speak accurately, and it can stores many handles. No matter user choose Arc or Rc, the type of vector's element must be certain, enums is necessary.

I haven't read any of the surrounding discussion, but a plain reading of RFCs 1238 and 769 says that the requirement was never dropped. The relevant part of 1238 reads:

The Drop-Check Rule (both in its original form and as revised here) dictates when a lifetime 'a must strictly outlive some value v, where v owns data of type D; the rule gave two circumstances where 'a must strictly outlive the scope of v.

  • The first circumstance (D is directly instantiated at 'a) remains unchanged by this RFC.
  • The second circumstance (D has some type parameter with trait-provided methods, i.e. that could be invoked within Drop) is broadened by this RFC to simply say "D has some type parameter."

Unfortunately, this only specifies changes to the Drop-Check Rule, and the revised rule is never stated in full. So, we need to look at the original rule from RFC 769 as well:

Let v be some value (either temporary or named) and 'a be some lifetime (scope); if the type of v owns data of type D, where (1.) D has a lifetime- or type-parametric Drop implementation, and (2.) the structure of D can reach a reference of type &'a _, and (3.) either:

  • (A.) the Drop impl for D instantiates D at 'a directly, i.e. D<'a>, or,
  • (B.) the Drop impl for D has some type parameter with a trait bound T where T is a trait that has at least one method,

then 'a must strictly outlive the scope of v.

The only thing explicitly changed by RFC 1238 is clause (B), but this doesn't affect the ownership clause ("if the type of v owns data of type D, ...")— The PhantomData requirement arises from this ownership clause, and not anything changed by the later RFC.

This implies that, even today, leaving out the PhantomData can lead to soundness issues for certain self-referential parameter types T that would otherwise be prevented by dropck. Perhaps someone who understands this better can either construct such an example or point to something I've missed that means it's not actually necessary.


Edit: After digging into the commit that changed the reference (cc @Yandros), it's justified by this comment which says, in part:

However this unsafety has been temporarily resolved by the fact that the non-parametric dropck rfc moved to safe defaults, where the presence of a generic argument implies “owns T”. And there’s no way to sneak in interesting lifetimes without being generic over them!

But, as per my reading above, no such implication was added by the RFC— Being generic over <T> doesn't imply ownership of T to dropck; instead it means that if you own a T, dropck will assume that it's accessed in arbitrary ways within your Drop implementation.

1 Like

Little hard to understand.

The drop checker will generously determine that Vec does not own any values of type T. This will in turn make it conclude that it doesn't need to worry about Vec dropping any T's in its destructor for determining drop check soundness.

struct Vec<T> {
    data: *const T, // *const for variance!
    len: usize,
    cap: usize,
}

Doesn't it just contain no T? data is a pointer of a T, not a T itself, so if no Drop trait implemented, isn't no any destructor runs expected?

As indicated by

2015.09.18 -- This RFC was partially superseded by RFC 1238, which removed the parametricity-based reasoning in favor of an attribute.

in RFC 0769 this is an outdated rule. If a Drop impl exists dropck will now always check that type and lifetime parameters of the type are still alive when trying to drop a value of this type except for those generic parameters with a #[may_dangle] attribute.

The sole purpose of PhantomData nowadays is to determine the variance of type parameters which aren't otherwise used as type in any of it's fields. The variance determines if you can cast Foo<'short> to Foo<'long>, Foo<'long> to Foo<'short> or if the lifetime needs to stay identical.

1 Like

Additionally, PhantomData can influence auto traits (Send, Sync, …).

1 Like

Even though you mention that commit I think I will go and mention and even quote the rendered output resulting from it :slightly_smiling_face:


From that same documentation (emphasis mine):

So yeah, this is a more restrictive property than

unsafe impl<#[may_dangle] T> Drop for Vec<T>
// pseudo-code
where
    Vec<T> contains PhantomData<T> // thus Vec<T> : dropck<T>,

insofar the latter lets you implicitly drop a Vec<&'dangling str> whereas a "may use T for w/e reason" denies that (but both correctly deny the Vec<impl DropGlue<'dangling>> case).

3 Likes

I don't really feel like hashing it all out again, but here's a previous thread about it.

There's a recent related RFC PR. I'm not up-to-date on it. If it doesn't already, perhaps it could be updated to make the non-requirement in the absence of may_dangle officially permanent.

2 Likes

While the conversation here has been good, the less interesting answer on my part is that I probably just copied that from the standard library. :slight_smile: Here's how Arc and Rc looked around that time, and the only change since then was rust#66117, which I suppose darc could also follow.

(There are other things worth fixing too, like #[derive(Clone)] adding unnecessary T: Clone.)

2 Likes

Not exactly the same as your idea, but I once wrote hybrid-rc for the use case of having most references on one thread.

I solved it similar to this:

struct Inner<T: ?Sized> {
    owner_thread_id: atomic::AtomicUsize,
    strong_local: Cell<usize>,
    strong_shared: atomic::AtomicUsize,
    weak: atomic::AtomicUsize,
    data: T,
}

struct Rc<T: ?Sized>(NonNull<Inner<T>>);
struct Arc<T: ?Sized>(NonNull<Inner<T>>);

unsafe impl<T: ?Sized + Sync + Send> Send for Arc<T> {}
unsafe impl<T: ?Sized + Sync + Send> Sync for Arc<T> {}

One thread can use the fast strong_local counter with Rc, but references that are moved to other threads need to upgrade to Arc. The owner_thread_id ensures that only one thread can downgrade Arcs back to Rcs.

This solution has more memory overhead, but allows for better performance, as long as it's statically known which thread clones the reference most often.

1 Like

This implementation has potential safety problem. What should happens if an Arc on other thread found there is no strong counts? That Arc shouldn't check strong_local because it may cause data racing, shouldn't drop the value directly because the "owner thread" probably still have Rc remains, and shouldn't leave the value alone because it will cause memory leaking.

Only transforming a Arc to an Rc needs to check the thread id. Once you have an Rc it can be cloned by just incrementing the local counter.

The implementation guarantees that if the local counter is non-zero, the shared counter is at least 1, and only drops to zero once all Rcs and Arcs are dropped. I took inspiration from how the weak counter of std::rc::Rc and std::sync::Arc is always at least 1 as long as a strong reference exists.

1 Like

I see, it's a good idea! But you can also improve like this:

struct Inner<T: ?Sized> {
    owner_thread_id: usize,
    strong_local: Cell<usize>,
    strong_shared: Option<atomic::AtomicUsize>,
    weak: atomic::AtomicUsize,
    data: T,
}

Initialize an Rc doesn't initialize AtomicUsize, AtomicUsize will initialize only when first time upgrading to Arc. If no upgrading occurred, Rc nearly acts like std Rc, except a option check when last Rc dropped.
And owner_thread_id doesn't need to be atomic since it will never mutates after initializing.