Type erased (dynamically dispatched) allocators

[Matthias247]

Would this WG also be interested in working on and standardizing type-erased/dynamic-dispatched/polymorphic allocators?

I imagine something along:

struct Allocator {
    // The internals could potentially be analoguous to the type erased `core::task::Waker`,
    // which solves a similar problem of being a type-erased handle that can be easily
    // forwarded and which can be implemented through a wide variety of strategies.
    data: *const(),
    vtable: &'static AllocatorVtable,
}

impl Allocator {
    pub unsafe fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr> {
        // Dynamic dispatch
        self.vtable.alloc(self.vtable.data, layout)
    }

    unsafe fn dealloc(&mut self, ptr: NonNull<u8>, layout: Layout) {
        // Dynamic dispatch
        self.vtable.dealloc(self.vtable.data, ptr, layout)
     }
}

The benefit of this type of allocators is that it can be stored inside the types which allocate (custom Boxes, Vecs, etc) without also making them generic. E.g. Box<T> could be defined along:

struct Box<T> {
    allocator: Allocator,
    ptr: *const T,
}

This also allows to pass types which originate from different allocators to the same APIs. Basically the same reasoning why C++ introduced polymorphic allocators (PMR).

Some personal experience report why I am interested in using those kinds of allocators:

I recently played around with custom allocation strategies for libraries in no-std environments, where relying on global allocation and always succeeding allocations wasn't feasible.

I started there with using traits for buffers and allocators to support various allocation strategies (e.g. buffer pools) - see the appendix. But the more I implemented my program, the more I got annoyed by it. The main reason was that I was at some places threading up to 6 generic generic types through functions in order to abstract over buffers and some other platform related types.

Since then I'm looking more and more into type-erased buffers and allocators, which seem to be very promising. In addition to having Allocators as plain structs, the buffer types could be the same, and e.g. store a struct Allocator inside them to be able to release themself back to the allocator or a pool. The Bytes crate recently went into a similar direction. This would clean up a lot of APIs in my case and make it easier for end-users to utilize them (it's e.g. easier to know what Bytes is then what a BufferLike constraint is).

Another domain which will in my opinion benefit from it would be Futures and async/await support on embedded platform. There we will want Futures to be allocated from different allocators in order to provide fault isolation and to prevent fragmentation. However parameterizing Future boxes for allocators and trying to make Futures from different allocators to run on the same executor is not pretty. This project tried this approach, and already ended up with a huge amount of code for just supporting 3 Future types. A FutureBox whic doesn't have to be generic over an allocator might be easier.

Drawbacks

The polymorphic allocator has 2 drawbacks:

• The additional cost of dynamic dispatch. I think it's not that relevant in most applications, since allocations are already costly. But nevertheless good to mention it.
• We have to store the Allocator in the types which allocate. That will likely be 2 additional pointers (which certainly can be relevant!).

Therefore it might not be a full replacement for generic static dispatched allocators.
But for my personal use-cases the usefulness would currently be higher.

Appendix: This was the original message buffer mechanism that I used

pub trait BufferLike: Deref<Target = [u8]> + DerefMut<Target = [u8]> + Debug {
}

impl<T> BufferLike for T
where T: Deref<Target = [u8]> + DerefMut<Target = [u8]> + Debug {}

/// An allocator for buffers
pub trait BufferAllocator {
    /// The type of the buffer which is returned. The buffer must dereference
    /// into a byte array.
    type BufferType: BufferLike;

    /// Tries to allocate a new buffer of the given size.
    /// If no buffer is available, `None` is returned.
    fn get_buffer(&self, min_size: usize) -> Option<Self::BufferType>;
}

[SimonSapin]

What makes an explicit vtable useful? I’ve always assumed we would keeps the "main" trait (Alloc or AllocRef if it’s renamed) object-safe, so that users can opt into dynamic dispatch by using &'a dyn Alloc or Box<dyn Alloc>.

[gnzlbg]

I’ve always assumed we would keeps the "main" trait (Alloc or AllocRef if it’s renamed) object-safe, so that users can opt into dynamic dispatch by using &'a dyn Alloc or Box.

👍 I always assumed this as well, maybe it might be worth to open an issue to track seeing if this has consensus and writing that down somewhere.

[lachlansneff]

Box must always be a single pointer for backwards compatibility, so putting additional pointers in box is a no go.

[Matthias247]

The epxlicit approach is a bit more flexible in what it can represent.

E.g. you can have the same type which represents the equivalent of a &'static dyn Alloc or a Arc<dyn Alloc> and do not have to choose between those. So an allocated thingy can point back to the allocator independent on whether it's a global one or whether it was also a dynamically created one which is refcounted and will shut down after all it's allocations had been released.

I think with regular trait objects you have to be explicit in terms of whether and how the trait object is boxed (static ref, Box, Arc).

The regular trait object approach also always uses the 2 pointers as an object. But sometimes that might actually not be what you intend. E.g. you might define a static allocator which manages a set of buckets - where each buckets contain equal sized memory chunks. You could now simply store the bucket ID in the data field. The method in the vtable then finds the associated underlying buffer by doing along GLOBAL_BUCKETS[data].

You can use trait objects for some of those alternate implementations, but it gets quite messy - people need to rely directly on dyn Trait layouts and need to structure/destructure them. E.g. futures-rs provided a set of Waker implementations which just did nothing, or dispatched to a thread-local function. For those some wilder transmutes had been used - as can e.g. be seen in this CR for NoopWaker which replaced it with the newer mechanism.

[JelteF]

Box must always be a single pointer for backwards compatibility, so putting additional pointers in box is a no go.

@lachlansneff what do you mean by this? Why would adding a field at the end of the struct break compatibility?

[Ixrec]

@JelteF I assume it's because Box explicitly guarantees this, and has public, stable APIs such as from_raw() that aren't really possible to implement otherwise.

[ObsidianMinor]

That link only talks about how you can convert between Box ptrs and Global allocator pointers. It doesn't make any guarantees that the size of a Box will always be the size of a native int.

For other things like from_raw and into_raw, new APIs will have to be added that return the allocator used to make the Box allocation or take in the allocator that created the ptr allocation.

[lachlansneff]

My main issue with this design, other than using up more space unnecessarily, is that it erases lifetimes as well as types. There is no way to safely put a stack allocated allocator into box here.

[Matthias247]

is that it erases lifetimes as well as types. There is no way to safely put a stack allocated allocator into box here.

Yes, for that you would need to have a different concrete type. E.g. Allocator vs ScopedAllocator. Boxes created by the latter must have lifetimes associated to them which tie them to the lifetime of the ScopedAllocator . The allocators API would look exactly the same, since you can't assign lifetimes to pointers.

That makes 2 concrete types, but that should cover all scenarios.