Modify `Arc` and `Rc` so the allocator is moved into the inner allocation

[Enderlook]

Basically, at the moment Arc<T, A> and its Weak<T, A> uses:

pub struct Arc<T: ?Sized, A: Allocator = Global> {
    ptr: NonNull<ArcInner<T>>,
    phantom: PhantomData<ArcInner<T>>,
    alloc: A,
}

pub struct Weak<T: ?Sized, A: Allocator = Global> {
    ptr: NonNull<ArcInner<T>>,
    alloc: A,
}

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

(Something similar happens in Rc and its Weak, so this whole issue could also be applied to them.)

My idea is to move alloc from Arc and Weak to InnerArc:

pub struct Arc<T: ?Sized, A: Allocator = Global> {
    ptr: NonNull<ArcInner<T, A>>,
    phantom: PhantomData<ArcInner<T, A>>,
}

pub struct Weak<T: ?Sized, A: Allocator = Global> {
    ptr: NonNull<ArcInner<T>>,
}

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

This would produce 2 benefits:

1) The size of Arc is guaranteed to be the size of a single pointer, which is cool. Also, being more realistic, it means that if you have a non-zero-sized allocator, you don't have to pay the cost of its size on each clone of the instance, instead the allocator is stored in the inner pointer. That means that multiple copies of the same instance won't require multiple copies of the allocator, saving memory unlike the current approach, 2) Doing this also means that A doesn't require implementing Clone if you want to clone the Arc, since it's stored in the shared pointer. This would relax the current Arc cloning implementation, no longer requiring A: Allocator + Clone but only A: Allocator. It would probably relax the same constrain in make_mut, unwrap_or_clone, downcast, downcast_unchecked, From<Vec<T, A>> for Arc<[T], A> and TryFrom<Arc<[T], A>> for Arc<[T; N], A>.

[zachs18]

This would be problematic for Weak, specifically Weaks created by Weak::new(_in), which do not have a backing allocation. fn Weak::allocator (if/when it exists) could return Option<&A> instead of &A, with None indicating that there is no backing allocation. Similarly, fn Weak::new_in could take no arguments, since it doesn't need to have an allocator (We probably couldn't just generalize Weak::new unless type parameter defaults affecting type inference becomes possible).

This would also require into_raw_with_allocator/from_raw_in to be changed on all four types. into_raw_with_allocator could just be removed, with into_raw being generalized. from_raw_in would have to change in the same way as Weak::new_in, for the same reason.

There's also something to be said for consistency; Box and Vec currently do not do this, and given their guarantees I'm not sure they could. On the other hand, Rc/Arc are unique in that they are conceptually shared where other heap-allocation types are uniquely owned, which may make "consistency" less convincing.

This would also mean that Arc/Rc wouldn't support being used interchangeably with A and &A as allocators

[Enderlook]

This would be problematic for Weak, specifically Weaks created by Weak::new(_in), which do not have a backing allocation. fn Weak::allocator (if/when it exists) could return Option<&A> instead of &A, with None indicating that there is no backing allocation. Similarly, fn Weak::new_in could take no arguments, since it doesn't need to have an allocator (We probably couldn't just generalize Weak::new unless type parameter defaults affecting type inference becomes possible).

Of course, these changes would also be applied to Weak for consistency, otherwise, it wouldn't make much sense. I should have been more explicit.

This would also require into_raw_with_allocator/from_raw_in to be changed on all four types. into_raw_with_allocator could just be removed, with into_raw being generalized. from_raw_in would have to change in the same way as Weak::new_in, for the same reason.

Yeah, a slightly inconvenient of this issue is that it's a breaking change. Although Rust has editions, so maybe the change could be between editions. I'm not sure if editions also include type changes or just compiler features...

There's also something to be said for consistency; Box and Vec currently do not do this, and given their guarantees I'm not sure they could. On the other hand, Rc/Arc are unique in that they are conceptually shared where other heap-allocation types are uniquely owned, which may make "consistency" less convincing.

I don't know if that is a convincing argument against this. After all Box and Vec has single ownership, and so the allocator is only stored once. Instead Arc and Rc can be cloned multiple times, so with the current approach, you are also duplicating the allocator, incurring unnecessary memory (and probably CPU) costs, (plus the downside that several methods require to implement Clone in the allocator, which could be completely avoided).

Also, maybe they should, though as you said, their guarantees make it much more difficult. Probably not worth it for those types.

This would also mean that Arc/Rc wouldn't support being used interchangeably with A and &A as allocators

Not sure if I understand that sentence, but I don't see a problem on it. If you use different allocators, you would always have to use generics, how does this feature impact on that specific issue?

[zachs18]

This would also require into_raw_with_allocator/from_raw_in to be changed on all four types. into_raw_with_allocator could just be removed, with into_raw being generalized. from_raw_in would have to change in the same way as Weak::new_in, for the same reason.

Yeah, a slightly inconvenient of this issue is that it's a breaking change. Although Rust has editions, so maybe the change could be between editions. I'm not sure if editions also include type changes or just compiler features...

I don't see how it would be a breaking change, actually. All of the _with_allocator/_in functions are unstable, so "breaking changes" to them are fine until they are stabilized, and do not require any edition-gating. Generalizing into_raw should not be a breaking change[^1]. Unless you mean generalizing from_raw? I don't know that this could be done over an edition easily[^2], but I suppose it could be done.

This would also mean that Arc/Rc wouldn't support being used interchangeably with A and &A as allocators

Not sure if I understand that sentence, but I don't see a problem on it. If you use different allocators, you would always have to use generics, how does this feature impact on that specific issue?

It is a fairly common pattern to do something similar the following to deallocate a heap-allocated container without dropping the allocator itself:

// let boxed: Box<T, A> = ...;
let (ptr, alloc) = Box::into_raw_with_allocator(boxed);
let boxed: Box<T, &A> = unsafe { Box::from_raw_in(ptr, &alloc) };
drop(boxed); // Deallocate using `impl<A: Allocator> Allocator for &A`
// use alloc for other things

This pattern is used in impl From<Box<T, A>> for Arc<T, A> and impl From<Vec<T, A>> for Arc<[T], A>, for example.

If Arc<T, A> holds A in its heap allocation (or its heap allocation's layout in any other way depends on A), then this pattern cannot be used with Arc as it can with Box and Vec. (Well, really the whole idea behind this proposal means that this pattern cannot be used with Arc). IMO the existence of impl<A: Allocator + ?Sized> Allocator for &A is a strong hint that &A can be used interchangeably with A for purposes of (de)allocation, which would mean that Arc<T, A> having the heap allocation's layout depend on the layout of A is unexpected.

[^1]: Because Arc already has a generic parameter, there's no String-like issue where the allocator parameter cannot be inferred, since users are generally either: 1. specifying Arc<T> which explicitly uses the default, or 2. already using type inference to resolve the T in Arc<T> anyway, so the allocator should not cause issues I think.

[^2]: AFAIK there are currently no path-resolution differences between editions; making Arc::from_raw resolve to different items in different editions would require support for this to be newly added to the compiler. Another way I could think to implement it would be to add the A parameter but have it "hard-coded" to Global on old editions, which Is also unprecedented AFAIK. The "best" way to resolve it would be "type parameter defaults affect inference" as discussed with Weak::new, which is also not currently possible.

[Enderlook]

I don't see how it would be a breaking change, actually. All of the _with_allocator/_in functions are unstable, so "breaking changes" to them are fine until they are stabilized, and do not require any edition-gating.

Great.

It is a fairly common pattern to do something similar the following to deallocate a heap-allocated container without dropping the allocator itself:

// let boxed: Box<T, A> = ...;
let (ptr, alloc) = Box::into_raw_with_allocator(boxed);
let boxed: Box<T, &A> = unsafe { Box::from_raw_in(ptr, &alloc) };
drop(boxed); // Deallocate using `impl<A: Allocator> Allocator for &A`
// use alloc for other things

This pattern is used in impl From<Box<T, A>> for Arc<T, A> and impl From<Vec<T, A>> for Arc<[T], A>, for example.

If Arc<T, A> holds A in its heap allocation (or its heap allocation's layout in any other way depends on A), then this pattern cannot be used with Arc as it can with Box and Vec. (Well, really the whole idea behind this proposal means that this pattern cannot be used with Arc). IMO the existence of impl<A: Allocator + ?Sized> Allocator for &A is a strong hint that &A can be used interchangeably with A for purposes of (de)allocation, which would mean that Arc<T, A> having the heap allocation's layout depend on the layout of A is unexpected.

I see. But couldn't the pattern be replaced with a new one? For example, Box<T, A> could implement a method Box<T, A>::pop_value_with_allocator(Self) -> (T, A), which deallocates the pointer, but prior to that it copies the values in order to return them (thoght probably a different method would be required for dynamic sized types as you can't just return them by value).

IMO the existence of impl<A: Allocator + ?Sized> Allocator for &A is a strong hint that &A can be used interchangeably with A for purposes of (de)allocation, which would mean that Arc<T, A> having the heap allocation's layout depend on the layout of A is unexpected.

Oh, well, I can't ague with opinions. So I don't know that to say about this, even if it's a hint, it's not a demand.