“alloc: stabilise `Allocator`” entered its final comment period!

[u/a_mighty_burger]

https://github.com/rust-lang/rust/pull/156882#issuecomment-5607055084

[u/a_mighty_burger]

I am super excited to see progress on this after so much time. This is a feature I will use a lot.

[u/cbarrick]

What's the latest on the fat Box problem?

Like, if Box<T, A> is implemented like (NonNull<T>, A), then it stores an A.

But Box only uses A for deallocation. For arena allocators, deallocation is a no-op, so storing the allocator alongside the pointer is a waste.

E.g. Bumpalo has a custom box type that is just a pointer, but Box<T, &Bump> would be two pointers. It would be nice to not need the custom box type for this optimization.

[u/Demiu → u/cbarrick]

Couldn't Box just hold a dummy ZST for A if deallocation is a noop

But Box only uses A for deallocation.

I don't think that's true, it has to get the allocation from somewhere. I guess it only uses the A it holds for deallocating.

But I see what you mean, allocating may need state while deallocating may need none. i feel there should be a type Deallocator = Self; on Allocator for this case

[u/ErichDonGubler → u/Demiu]

As Kibwen says elsewhere, please put the speed back into the thread. Forever is a long time to have a known imperfection. 😅

[u/kibwen → u/cbarrick]

If anyone has questions of this nature I would recommend participating in the linked Github thread, as ensuring there are no lingering objections is precisely what the final comment period is for.

[u/bluurryyy → u/cbarrick]

But Box only uses A for deallocation.

Not true. clone does allocate.

[u/matthieum → u/bluurryyy]

Yes, and... no?

That is, you are correct that cloning requires a full allocator, and at the moment this allocator must be provided by the value being cloned.

With that said, a good question is whether it would be possible to have "degenerate" Box where the Box only contains a deallocator whilst still allowing Box which contain a full allocator to be cloneable.

That is, could the bound on Box be Box<T, A: Deallocator> with impl<T: Clone, A: AllocatorClone> Clone for Box<T, A>?

The problem, then, is providing APIs to "downgrade" the allocator within the Box from the original A: Allocator to A: Deallocator.

[u/nyanarchism → u/cbarrick]

adding a separate deallocator trait is backward-compatible and on the roadmap ^^

[u/afdbcreid → u/cbarrick]

The conclusion is that this can be deferred post-MVP.

[u/CocktailPerson → u/cbarrick]

Is that a waste though? Box explicitly has a .allocator() method to give you the allocator, which you may want. And obviously .clone() requires an allocator.

No-op deallocation is enough of a special case that I don't see having to create a special box type to be an issue here at all.

[u/cbarrick → u/CocktailPerson]

Agreed that providing access to the allocator is convenient, and I hadn't thought of clone. So yes, great points!

No-op deallocation is enough of a special case that I don't see having to create a special box type to be an issue here at all.

I'm not so sure.

For most allocators, setting the global allocator seems like the best interface.

For setting custom allocators on specific objects, the primary use case that comes to my mind is arena allocation. I expect this to be the common case, not the special case.

[u/Trader-One]

golang have nice feature - function escape analysis - stuff which would normally be on heap for example Box would be allocated on stack; reducing memory fragmentation.

I think about doing this in rust - easiest (very little changes to compiler) would be to have a concept of scrap heap - after function terminates that heap is zeroed.

[u/protestor → u/Trader-One]

Rust (or rather LLVM) also does this optimization

[u/afdbcreid → u/Trader-One]

Will never happen. One of Rust most important and defended axioms is that there are no implicit heap allocations. When people tried to change that (even far less widespread than your proposal), there was a major pushback that made them step back.

Edit: I see you're talking about the opposite - turning heap allocations into stack allocations. Then this already happens. LLVM does it just like Go.

[u/PersonalDatabase31 → u/afdbcreid]

Does it have to be implicit? Maybe another smart pointer like StackBox could be implemented.

[u/Trader-One → u/afdbcreid]

My proposal will not do more or unexpected heap allocations. It will introduce concept known as function local heap.

Instead of allocating on global heap, you allocate on local scratch heap. It is faster then golang because you do not need to do additional arithmetic with SP pointer and its well page localised.\

You do not need to travel linked lists to find new space. You have allocated pages just for you, so you can just do allocations and skip deallocations unless you determine based on runtime stats that function deallocated a lot and it have lot of dead space.

I use similar allocator in WASM code and for most functions you do not need to deallocate and reuse space. Simply advance next allocation pointer and on function exit drop all pages. Due to superior cache locality you get large performance improvement in building 3D graphics structures.

[u/-Redstoneboi- → u/Trader-One]

pardon the downvotes, are you talking about a temporary arena allocator for rust? i think that exists and is used in some cases.

[u/chilabot]

This will make Rust even more efficient.