Stabilizing (A)Rc layout?

Box is guaranteed to use the Global allocator and be manually allocateable.

We can turn a manually allocated Box into (A)Rc via From<Box<T>>, but that necessarily incurs a reallocation and copy to make space for the reference counters.

The layout of (A)Rc on the heap is quite simple:

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

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

Is there concrete utility in allowing the compiler to reorder the strong/weak/data triple? If not, I think it would be beneficial to stabilize the heap representation of (A)Rc as

#[repr(C)]
pub struct OnHeapReferenceCounted<T: ?Sized> {
    pub strong_count: UnsafeCell<usize>,
    pub weak_count: UnsafeCell<usize>,
    pub item: T,
}

This would allow for allocating and placing unsized types directly into a reference counted allocation rather than proxying through a Box. (Note that just exposing and stabilizing this type without #[repr(C)] isn't enough, as that only works for sized types.)

Alternatively, though this would require more lang work to actually guarantee, we could guarantee a different layout for Sized and !Sized types. EDIT: unsizing coercions mean that's a no-go.

The alternatives for libraries today are to just eat the Box->(A)Rc transformation cost (as far as I can tell, it doesn't optimize to one allocation even for known types, and probably cannot) or expose a custom ArcMyThing type that re-implements (A)Rc, complete with unsoundness.

1 Like

This can't work because then converting an Arc<[T; N]> to Arc<[T]> would have to copy data.

1 Like

It seems to be the case that the reference counted object is always put last currently, even when providing optimization fuel for types that do not need to cannot coerce to unsized.

It must always be last or you couldn't CoerceUnsized, as mentioned above. The compiler doesn't scan the entire program to see how a type is used before laying it out.

1 Like

One representation change that could be worth considering before stabilizing a layout is to move reference counts to negative offsets from the Rc/Arc pointer, so that we do arithmetic only when touching the reference counts and not when dereferencing, assuming the average Rc is dereferenced at least once during its lifetime.

https://rust.godbolt.org/z/skAP2_

Though maybe this change would be completely transparent if everything goes through the into_raw / from_raw functions? In that case stabilizing the OnHeapReferenceCounted layout is independent.

Before:

         โ”Œโ”€โ”€โ”€โ”
โ•”โ•โ•โ•โ•โ•โ•—  โ”‚   โ•”โ•โ•โ•โ•โ•โ•โ•คโ•โ•โ•โ•โ•โ•โ•คโ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•—
โ•‘ ptrโ”€โ•ซโ”€โ”€โ”˜   โ•‘ strg โ”‚ weak โ”‚ value... โ•‘
โ•šโ•โ•โ•โ•โ•โ•      โ•šโ•โ•โ•โ•โ•โ•โ•งโ•โ•โ•โ•โ•โ•โ•งโ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•
 Rc<T>        RcBox<T>

After:

         โ”Œโ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”
โ•”โ•โ•โ•โ•โ•โ•—  โ”‚   โ•”โ•โ•โ•โ•โ•โ•โ•คโ•โ•โ•โ•โ•โ•โ•คโ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•—
โ•‘ ptrโ”€โ•ซโ”€โ”€โ”˜   โ•‘ strg โ”‚ weak โ”‚ value... โ•‘
โ•šโ•โ•โ•โ•โ•โ•      โ•šโ•โ•โ•โ•โ•โ•โ•งโ•โ•โ•โ•โ•โ•โ•งโ•โ•โ•โ•โ•โ•โ•โ•โ•โ•โ•
 Rc<T>        RcBox<T>
11 Likes

Yeah, given we have into_raw/from_raw, I'm not interested in trying to stabilize the stack representation of the actual (A)Rc pointer, just the on-heap representation.

(In fact, the custom (A)Rc that I'm working with right now stores the raw pointer as exposed by those two methods.)

Completely off topic side question: do there exist any memory allocators that allow you to say "ptr + 16 is align(N)" (or equivalently "give me a ptr with align(N), forward size M, and reverse size L")? That would be an interesting approach for shrinking the size of (A)Rc-style heap-annotated pointers where the annotated object has a high align. (I realize that in practice aligns greater than usize are rare.)

1 Like

If you already know, in advance, that the object is likely to wind up moving into an Arc, why not just allocate it in an Arc in the first place, and use a wrapper to make it pretend to be a box?

struct ArcBox<T> {
    inner: Arc<T>,
}
impl<T> ArcBox<T> {
    pub fn new(inner: T) -> ArcBox<T> {
        ArcBox { inner: Arc::new(inner) }
    }
    pub fn from_arc(inner: Arc<T>) -> Result<ArcBox<T>, Arc<T>> {
        if Arc::get_mut(&mut inner).is_some() {
            Ok(ArcBox { inner })
        } else {
            Err(inner)
        }
    }
    pub fn into_arc(self) -> Arc<T> { self.inner }
}
impl<T> Deref for ArcBox<T> {
    type Target = T;
    fn deref(&self) -> &T { &*self.inner }
}
impl<T> DerefMut for ArcBox<T> {
    fn deref_mut(&mut self) -> &mut T {
        unsafe {
            // The ArcBox wrapper ensures that the arc only has one reference,
            // and that it cannot be cloned.
            &mut *(self.into_raw() as *mut T)
        }
    }
}

There's a type like this in Servo, because turning all the Arc instances into Box, because the construction phase wants refcounting, but the resulting tree requires mutable access.

3 Likes

This came about because I'm playing around with custom ?Sized types, and there's no way to safely create these types. You have to manually allocate them, even though once they exist they can be safe to use.

The only reason to start as a Box is because Box has a defined heap layout and is defined to be compatible with manually using the GlobalAlloc API. Arc has no such guarantee, which is what stabilizing the heap layout of reference counted objects would provide.

Yeah, custom unsized types kind of stink in present-day Rust. If you can make an Arc, you can make an ArcBox.

That seems like it would be better solved with a placement system, so that your object-creation routine can be generic over containers (Arc, Rc, Box). That seems like a long way away, though...

It's painful, but possible, and you can abstract it into a library.

That's why this is hopefully a minimal commitment for the libs team.