Separate dealloc from Alloc into other trait

[TimDiekmann]

Most (all?) of the structs mentioned in #7 only needs the dealloc method for Drop. It'd may be useful to split up Alloc into two traits. We didn't came up however with the exact layout and relationship with those two traits. So far, those possibilities showed up:

• Make it a supertrait: trait Alloc: Dealloc { ... } (Separate dealloc from Alloc into other trait #9 (comment))
• Associate the Alloc trait: trait Dealloc { type Alloc: Alloc; ... }
• Introduce a trait trait GetDealloc { unsafe fn get_dealloc() -> ???; }
• Same as above, but get_alloc as method in Alloc instead of an extra trait (Separate dealloc from Alloc into other trait #9 (comment))
• Also split realloc into Realloc and associate Dealloc with Alloc and Realloc (Separate dealloc from Alloc into other trait #9 (comment))
  • Also associate Alloc with Realloc (Separate dealloc from Alloc into other trait #9 (comment))
• Even more complicated hierarchies (Separate dealloc from Alloc into other trait #9 (comment))

Edits

• 2019/Oct/05: Reflect the threads current solution proposals.

[glandium]

Other possibility:

• trait Dealloc { ... } impl<T: Alloc> Dealloc for T { ... }, and change the relevant bounds to Dealloc.

[SimonSapin]

only needs the dealloc method for dropping

This is not quite true. Other APIs like Box::clone or Rc::make_mut may need to allocate.

---

I think it’s important for this issue to provide some context and motivation.

Current proposals revolve around adding an A: Alloc type parameter to types such as Box<T>, Vec<T>, etc; and storing a value of type A inline in those structs. For "traditional" allocators like jemalloc that are process-global / singleton, A can be a zero-sized type. However for allocators that might have multiple "instances", A needs to be a handle like &_ or Arc<_> in order to associate each collection value with its corresponding allocator instance. This means e.g. doubling size_of for Box, which has non-trivial cost.

This issue is about reducing this cost in a narrow set of circumstances:

• The allocator has multiple instances, so allocating requires a non-zero-size handle
• Deallocation is a no-op (for example in a simple bump allocator) or otherwise doesn’t require a handle that point to the allocator instance.
• And the user is willing to give up on APIs like Box::clone, such that the box only ever needs to know how to deallocate, never allocate.

In that case we could in theory have zero-size deallocation-only handles to keep in Box<T, A>, in order to keep it small.

[SimonSapin]

So far I haven’t seen a complete proposal of what an API supporting this use case might look like. It’s not just the trait:

• Giving up on Clone and friends needs to be a opt-in choice, so there needs to be dedicated APIs on collections in any case. Does that mean e.g. Box::new_dealloc_only_in in addition to Box::new_in? What’s the signature?

• Before we can get a deallocation-only handle that is appropriate for some allocation, that allocation needs to have been allocated at some point. Presumably with a “full” handle. Does that mean that a “full” handle knows how to downgrade itself to deallocation-only? What’s the API for that?

Before we accept it as a goal to support this use case, I’d like someone who wants it to come up with a more comprehensive API proposal. That should be the starting point of the discussion.

But if this adds significant complexity to the type signature even for users who do not use this feature, I’m not sure we should accept such a narrow use case.

[TimDiekmann]

This is not quite true. Other APIs like Box::clone or Rc::make_mut may need to allocate.

I'm sorry, I think I expressed myself misunderstandably. The struct itself only needs Dealloc as bound as Drop only needs dealloc. Things like Box::clone could bind A: Alloc + Dealloc.

[scottjmaddox]

Yeah, the impl<T> for Box (and other collections) would just need to be split into impl<T, A: Dealloc> and impl<T, A: Alloc+Dealloc>. You wouldn't need a separate new_dealloc_only_in.

[SimonSapin]

I don’t understand. If new_dealloc_only_in is not needed, please provide the full signatures you would expect for the Box type, the constructor, and the destructor. In particular, how is the allocation owned by Box<T, A: Dealloc> created?

[TimDiekmann]

Not a signature, but with from_raw_in it would be possible. It's rather lowlevel but for complex data structures this might makes sense.

[scottjmaddox]

You're right, my previous suggestion was incorrect. However, it can be done like this (unless I'm missing something):

struct Box<T: ?Sized, D>(Unique<T>, D);

impl<T: ?Sized, D: Dealloc> Drop for Box<T, D> {
    fn drop(&mut self);
}

impl<T: ?Sized, D: Dealloc, A: Alloc<Dealloc=D>> Box<T, D> {
    fn new_in(x: T, a: A) -> Box<T, D>;
}

[SimonSapin]

@TimDiekmann So the only way to use this feature would require unsafe code?

@scottjmaddox So we’d have an Alloc::downgrade(self) -> Self::Dealloc method, and the choice of giving up on Box::clone or not (A = D) would be based on using a different allocator type?

[scottjmaddox]

Yes, you would need something like Alloc::downgrade(self) -> Self::Dealloc; perhaps just Alloc:get_dealloc(&self) -> Self::Dealloc. And as you say, some allocators would provide a type that implements Alloc + Dealloc instead of just Dealloc, and the former would impl Box::clone.

Ideally, there would be additional methods like Box::clone_in that accept an Alloc argument.

[gnzlbg]

So the only way to use this feature would require unsafe code?

Yes. I don't know if the analogy helps, but have you used C++'s std::unique_ptr ? It only needs a "custom deleter" to free itself on destruction. The std::unique_ptr itself is "move only", and cannot be implicitly cloned (has no copy constructor/assignment).

IIUC what's being proposed here is the same. Box<T, A: Dealloc> is the bound on the type. This is useful, e.g., because you don't necessarily need to construct a Box via Box::new, you can also construct a Box from a raw pointer, e.g., coming from FFI (e.g. from a C++ unique_ptr).

Most of the Box functionality would just be impl<T, A: Dealloc> for Box<T, A> { ... }. As you mention, some of the functionality, like Box::new, would be in a impl<T, A: Alloc + Dealloc> for Box<T, A> { ... } and some of it, like Box::clone, in a impl<T: Clone, A: Alloc + Dealloc> for Box<T, A> { ... }.

[scottjmaddox]

@gnzlbg Is there any reason my suggestion for a safe new_in function would not work? There should certainly be from_raw_in, too. And Box::clone could still be in an impl<T: Clone, A: Alloc + Dealloc> for Box<T, A> { ... } block so that it's available if the allocator handle is Alloc+Dealloc.

[gnzlbg]

@scottjmaddox

One of the main use cases for Box<T, D: Dealloc> is FFI wrappers, where e.g. a C library gives you ownership of some value, and provides you with a function to free it. There is no way to clone that Box, or use the Box type to allocate anything else with it.

Ideally, you'd just implement Dealloc for a MyCResourceDeallocator ZST, and use Box<MyCResource, MyCResourceDeallocator> directly in C FFI.

I'm not sure how you would be able to achieve that with new_in, but I think this is a use case worth supporting.

[scott-maddox]

@gnzlbg I totally agree that that's a use case worth supporting, and that from_raw_in is a great way to support that. I'm just asking if there's any reason you couldn't also have the new_in I suggested, so that there's a way to use this feature without unsafe.

[gnzlbg]

@scott-maddox would that require implementing Alloc for MyCResourceDeallocator ?

[scottjmaddox]

@gnzlbg No, it would not. With my suggestion, implementing Alloc would require implementing Dealloc, but implementing Dealloc would not require implementing Alloc.

(Side note: this is the same person as scott-maddox; I meant to use this account.)

[glandium]

I was thinking about this a little, and I think this means there needs to be a different trait for realloc too. Because Alloc + Dealloc doesn't allow doing something specific for realloc instead of doing a dealloc + alloc sequence. So there would need to be a Realloc trait, as well as a a default impl<A: Alloc + Dealloc> Realloc for A.

[gnzlbg]

as well as a a default impl<A: Alloc + Dealloc> Realloc for A.

The problem with that is that, without specialization, users cannot override that impl.

[glandium]

Thus "default" in my sentence.

[gnzlbg]

I thought that wasn't intended. If that's by design, then the main downside is still that we would be blocking the stabilization of these APIs on stable specialization. I'm not sure that would make strategic sense.

[glandium]

I'm not sure it would need to block on stable specialization. Implementers should be able to impl Realloc for their type whether specialization is stable or not, shouldn't they?

[glandium]

Without a Realloc trait, Alloc should keep both realloc and dealloc methods, and there should be an impl<A: Alloc> Dealloc for A (which is what I mentioned in #9 (comment) already).

[gnzlbg]

Is there is some already-stable magic that allows users to specialize without specialization default impls of liballoc ?

If not, your blanket impl<A: Alloc> Dealloc for A has the same problem. T

here are two impls for your allocator, the blanket one that you provide (e.g. Dealloc, and Realloc), and the one that a user might want to write. Without specialization, those two conflict.

[glandium]

A user wouldn't have to write a Dealloc impl if they write a Alloc impl, because dealloc is already in there.

[gnzlbg]

I’m not sure we are talking about the same trait hierarchy then. I understood this issue as separating dealloc from the Alloc trait into a different trait, such that ‘trait Alloc: Dealloc { ... no dealloc here ... }’.

[TimDiekmann]

If we decide to introduce either of the traits, this would be done in three steps:

1. Provide an empty trait for DeallocRef (and ReallocRef)
2. Update miri and the nomicon to import both traits
3. Actually split AllocRef

[Wodann]

If we think that the ReallocRef change is going to be controversial, it might be a good idea to split it into two separate PRs; one for splitting the DeallocRef trait and one for splitting the ReallocRef trait. That way if one gets rejected/reverted, the rest of the work won't be affected.

[TimDiekmann]

I'm fine with that.

Does anyone want to write the documentation for DeallocRef and adjust AllocRef a bit?
Update: @Wodann will do this

[Wodann]

Do you still want to create the actual PR to rustc? It might be good if it is the same person making PRs (for recognisability). In that case someone'd need to push/pr to your fork.

[Amanieu]

I am strongly opposed to having a separate ReallocRef trait. There is no good reason for splitting it away from AllocRef when a perfectly good default implementation needs only alloc and dealloc.

Regarding DeallocRef I am concerned that the use case for it is somewhat niche: it only really helps Box, which isn't really used that much with custom allocators (as far as I know). The use case I am currently looking at is a compiler where I use a bumpalo instance per function, so that I can quickly allocate memory for internal data structures while compiling (mainly Vec and HashMap) and discard them all once I am done compiling a function.

[Lokathor]

Just leak the box and keep the &mut around however long you would have kept the box around

[TimDiekmann]

@Wodann

Do you still want to create the actual PR to rustc? It might be good if it is the same person making PRs (for recognisability).

Yes, I think that makes sense.

In that case someone'd need to push/pr to your fork.

One could also make a PR to alloc-wg, or post the docs here, in zulip, or send it to me via EMail or PM in Discord 🙂

@Amanieu @Lokathor Could you also give a vote?

[Lokathor]

i vote this idea is just way too niche

[scottjmaddox]

Regarding DeallocRef I am concerned that the use case for it is somewhat niche: it only really helps Box, which isn't really used that much with custom allocators (as far as I know).

That's one of the things this working group is trying to fix, though. It would be much better if Rust std lib collections had first-class support for custom allocators.

[TimDiekmann]

Can I assume that the majority voted for splitting dealloc (not realloc!) and I can go ahead? While @JelteF and @stevenlr are not tagged, I don't want to ignore those votes as we don't have a fixed membership.

[stevenlr]

I originally voted to also split realloc for consistency but @Amanieu's arguments had me change my mind. Updated my vote above, thanks for taking it into account. :)

[TimDiekmann]

Whops, wrong Issue... Sorry for the noise

[TimDiekmann]

Will close this as we probably won't implement this. If we will do, we can still reopen it (again).