Stream: t-libs/wg-allocators

Topic: Conversion of `bumpalo` to use `alloc_wg` crate

Erich Gubler (Nov 01 2019 at 17:13, on Zulip):

Hey all! As part of learning about how to actually use the APIs we currently have I'm experimenting with changing bumpalo to use the alloc_wg crate. I think I've been able to figure out how to use some things, so I'll have lots of questions to check that my understanding is right soon. :)

Erich Gubler (Nov 01 2019 at 17:15, on Zulip):

I've been adding the necessary fallible APIs for bumpalo's forked definitions of String and Vec, but I'm worried I may be reinventing the wheel. Has that already been done?

Tim Diekmann (Nov 01 2019 at 17:30, on Zulip):

Currently I have only implemented Box and RawVec. Vec and String would be the logical next step (in this order). Feel free to make PRs to the alloc-wg crate :)

Tim Diekmann (Nov 01 2019 at 17:34, on Zulip):

Regarding the fallible API: I introduced a new Never-type for stable-compatibility. As soon as an allocator uses this as the error type, the infallible methods on Box and RawVec can be used. AbortAlloc wraps any BuildAlloc and AllocRef and makes them infallible.

Erich Gubler (Nov 01 2019 at 18:19, on Zulip):

What's the reason for a separate Never type when core::convert::Infallible is available? Does it predate that, maybe?

Tim Diekmann (Nov 01 2019 at 21:07, on Zulip):

It's actually an alias ;)

Erich Gubler (Nov 02 2019 at 23:45, on Zulip):

Okay, one hitch I'm not immediately sure how to resolve, so I'll shelf this for a bit in favor of developing the summary I've talked about: the only part of the pre-allocators API that doesn't seem to match now is actually the interface of Clone. Right now, the only way to get a <B as BuildAlloc>::Ref from a RawVec (the Vec::buf field, in this case) is with the RawVec::alloc_ref() method, but...that takes &mut self. Which obviously can't happen in an implementation of Clone without some form of synchronization.

Tim Diekmann (Nov 03 2019 at 02:50, on Zulip):

alloc_ref takes a &mut self as build_alloc_ref requires &mut self. This was discussed in the issue about BuildAlloc as well (Can't remember if it was in the issue directly or in the old issue on /rust-lang/rust).

I have not implemented Clone on RawVec but I think it's very similar to the Box. I implemented Clone on Box in two steps: First I introduced a more generic trait CloneIn`. Currently this was only for structuring the code better:

impl<T: Clone, A: AllocRef, B: BuildAllocRef> CloneIn<A> for Box<T, B>
    B::Ref: AllocRef,
    type Cloned = Box<T, A::BuildAlloc>;

    fn clone_in(&self, a: A) -> Self::Cloned
        A: AllocRef<Error = crate::Never>,
        Box::new_in(self.as_ref().clone(), a)

    fn try_clone_in(&self, a: A) -> Result<Self::Cloned, A::Error> {
        Box::try_new_in(self.as_ref().clone(), a)

This provides an interface of creating a clone of the current object in an arbitrary allocator. Keep in mind, that Box (and RawVec) holds the ref-builder, not the Ref itself. An AllocRef (or B::Ref) is typically a ZST, a handle, or a reference, which can be cloned cheaply. With this, Clone is pretty straight forward to implement:

impl<T: Clone, B: BuildAllocRef + Clone> Clone for Box<T, B>
    B::Ref: AllocRef<Error = crate::Never>,
    fn clone(&self) -> Self {
        // Clone the builder, this has to be done anyway
        // Now we don't have to care about `&mut self` anymore
        let mut b = self.build_alloc().clone();
        let old_ptr = self.ptr.cast();
        let old_layout = NonZeroLayout::for_value(self.as_ref());

        unsafe {
            // create a new `B::Ref`
            let a = b.build_alloc_ref(old_ptr, old_layout);
            // clone it

It's basically reusing the stored builder.

Does this helps you understanding my thoughts?

Erich Gubler (Nov 03 2019 at 03:54, on Zulip):

So, you're saying I should implement this for RawVec first?

Tim Diekmann (Nov 03 2019 at 03:58, on Zulip):

I meant Vec, sorry, it's late ;)
On RawVec it doesn't make much sense as it's not aware of the underlying content.

Gurwinder Singh (Nov 03 2019 at 10:46, on Zulip):

I was also trying to use alloc-wg in bumpalo.
It may be very silly but I am stuck with implementing the BuildAllocRef and AllocRef (and friends) traits. What do you implement them on? directly on Bump or &mut Bump?

impl BuildAllocRef for Bump {
    type Ref = &'a mut Bump;  // ??

    unsafe fn build_alloc_ref(
        &mut self,
        ptr: NonNull<u8>,
        layout: Option<NonZeroLayout>,
    ) -> Self::Ref {

We can't clone Bump around.

Also, if I do:

impl<'a> BuildAllocRef for &'a mut Bump {
    type Ref = Self;

    unsafe fn build_alloc_ref(
        &mut self,
        ptr: NonNull<u8>,
        layout: Option<NonZeroLayout>,
    ) -> Self::Ref {

That also don't work, because returned reference can't outlive the function's borrowed lifetime.

Gurwinder Singh (Nov 03 2019 at 10:53, on Zulip):

I looked around and GAT seems to be the solution. Is it possible to implement this without GATs?

Erich Gubler (Nov 06 2019 at 15:40, on Zulip):

They're supposed to be on references/handles to Bump. With the current API, we'll have to use a mutable reference, but I think we need to add another API for synchronized allocator access too.

Gurwinder Singh (Nov 06 2019 at 16:55, on Zulip):

Right.. I tried with Bump but cant get it to work

Gurwinder Singh (Nov 06 2019 at 16:55, on Zulip):

Global/System ones were simple as they are empty structs that forward calls to global alloc

Gurwinder Singh (Nov 06 2019 at 16:56, on Zulip):

For local allocators, borrow checkers gets in thw way

Tim Diekmann (Nov 06 2019 at 16:56, on Zulip):

@Scott J Maddox If I remembered correctly you had an Idea here when proposing the BuildAlloc approach regarding a bump allocator?

Erich Gubler (Nov 06 2019 at 17:06, on Zulip):

I feel like we might want to discuss having a &self variant for allocators that have synchronization. Using &mut self will be nice when we want unsynchronized access to allocator state, but I think many (if not most) allocators will have a synchronization mechanism of some sort to be thread-safe.

Last update: Sep 18 2020 at 07:30UTC