How is Arc implemented? How is it only 8 bytes large?

Question

I noticed that the size of Arc is only 8 bytes in Rust. What is the basic implementation for Arc? My sense is that it would require at least a pointer and counter, and the pointer alone would be 8 bytes already. Is it the same for Rc?

Answer 1

As with any implementation question, the answer may be out-of-date in a future version.

tl;dr the count can't be part of the Arc, because everyone with a reference has their own instance of the Arc struct. The count has to be somewhere shared.

In the current standard library implementation, Arc<T> is defined as

pub struct Arc<
    T: ?Sized,
    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
> {
    ptr: NonNull<ArcInner<T>>,
    phantom: PhantomData<ArcInner<T>>,
    alloc: A,
}

This is three things: a pointer to an ArcInner<T>, a zero-sized phantom used for static analysis regarding variance and related matters, and an allocator. By default, this uses the global allocator (a zero-sized struct that says to use the system malloc/free or equivalent).

In that typical case where you don't bring your own allocator, an Arc<T> object's bytes is simply a pointer to the ArcInner, which is defined as follows:

#[repr(C)]
struct ArcInner<T: ?Sized> {
    strong: atomic::AtomicUsize,

    // the value usize::MAX acts as a sentinel for temporarily "locking" the
    // ability to upgrade weak pointers or downgrade strong ones; this is used
    // to avoid races in `make_mut` and `get_mut`.
    weak: atomic::AtomicUsize,

    data: T,
}

source

It's this ArcInner that holds the counts and the data being shared through the Arc.

Note that the count is stored alongside the data itself. This makes sense - the count needs to be shared between all Arcs that are pointing to the same data, rather than each Arc having its own counter. If each Arc had its own counter, there would be no way to agree on what the reference count ought to be at any moment. Instead, as individual Arc objects are created by cloning and dropped, this one shared reference count tracks how many of these Arc objects are out there.

It's worth noting that an Arc may not always be sized 8 bytes on a 64-bit system. For a 64-bit system, 8 bytes is enough for a thin pointer (i.e. just an address, with no additional metadata).

However, Rust has something called fat pointers which arise in cases where an address is not enough to define an object. A common case of a fat pointer is a pointer or reference to a dynamically sized type, such as a slice where the length isn't statically specified. e.g. &[u8] but not &[u8; 4096]. Other examples of DSTs are trait objects (i.e. adorned with dyn); &dyn references are likewise fat pointers, with the metadata pointing to the vtable that lets the caller find the correct implementation of the trait's methods.

Recall the T: ?Sized bound in Arc and ArcInner? By default, generic type parameters aren't allowed to be DSTs, since DSTs are very restrictive (they cannot be put onto the stack, returned by value, etc). This weird-looking bound allows T, the type parameter, to be a DST - and consequently, ArcInner to become a DST if T is a DST.

If your ArcInner is a DST, then the NotNull<ArcInner<T>> itself will store a fat pointer instead, and the Arc will store a fat pointer + two zero-sized types. For example, on x86_64, all of the following will actually be 16 bytes:

• Arc<str> - an Arc holding a string slice. Needs space to store the address of the ArcInner and the metadata about the size of the data field.
• Arc<[u8]> - an Arc holding an array of u8 of unknown length. Likewise.
• Arc<dyn Foo>, where Foo is an object-safe trait. Needs to store the address of the ArcInner and a vtable that allows a caller to locate the correct implementation of functions in Foo.
• An Arc holding my own struct that's a DST (either because I put a DST in the last field, or the last field was generic, I allowed a DST there using T: ?Sized, and the type parameter was in fact a DST)

By the way, Rc is very similar - although instead of an ArcInner with atomic refcounts, it has an RcBox that has Cell<usize> refcounts.