Proof Of Concept Crate: Simplistic Bump Allocator

[Lokathor]

Many groups want a simple "bump allocator" which can be used for per-frame data.

This should be sufficiently simple to setup and also maintain safety.

• The bump alloc has a pile of data and an "alloc count"
• When you allocate out of it you get a BumpBox or BumpSlice<[T]> or possibly other types. Optionally we can allow allocation failures here.
• When any of the BumpBox and friends types drop they know to decrease the alloc count. This could be done via Rc or Arc, or via having a single global bump allocator with an atomic counter that they know to go and edit, or whatever way.
• You can call reset on the allocator to reset the allocator to the start of the data pile.
• If the number of allocations checked out when you call reset is non-zero, it panics.

What we need is a proof of concept crate so that we can test it out, find the problems, iterate design, etc.

[zakarumych]

Most existing bump allocators use lifetimes to ensure everything is deallocated when they reset.
Is there a problem with passing 'frame to functions which needs to allocate frame-local data?

[Lokathor]

That might be fine, but clogs up the outer types of everything if you use lifetimes, so it might also be very unwanted.

There is space for both styles probably.

[zakarumych]

For lifetime-style bumpalo looks nice

[zakarumych]

Sure. lifetimes are going to infect lots of functions, but you're going to add allocator reference in arguments anyway wherever allocation will happen. And whatever function borrows allocated data will have lifetime too.
So the only functions that may go without lifetime with ref-counted approach are those which takes ownership of allocated values - take BumpBox<T>. Do you expect much of those?

[Lokathor]

Yes, I was expecting almost exclusively that you'd be getting owned allocation out of the allocator and then dropping them all at the end of a loop.

Also that you could potentially put it on a global static and then never need to pass it around. Or a thread-local, depending on if lots of threads will do lots of stuff.

[jaynus]

We've implemented this for usage in amethyst and rendy related projects.

https://github.com/jaynus/purple

The entire concept revolves around some user behavior constraints to protect against UB, which we dont handle.

Let me know if this is of any interest to get up to snuff on the safety side. We currently use it for some limited cases in amethyst and rendy, with some known limitations and factors around that. Collections type are a bit lacking at the moment as well, but that is, again, because it is geared towards being a very strict game-oriented bump allocator, not a generic one (such as bumpalo)

[Wodann]

@Ericson2314 @TimDiekmann I am just taking our discussion from issue #70 here.

You mentioned that this code segment might solve my problem:

impl<ChunkAlloc> AllocRef for Bump<ChunkAlloc> where ChunkAlloc: AllocRef {}
impl<ChunkAlloc> AllocRef for &Bump<&ChunkAlloc> where &ChunkAlloc: AllocRef {}

but as far as I can tell this doesn't affect my use case at all. I am adding the following function to my BumpAlloc implementation:

pub fn alloc_t<T>(&self, val: T) -> Result<&mut T, <&Self as AllocRef>::Error> {
    assert!(mem::size_of::<T>() > 0);

    unsafe {
        let layout = NonZeroLayout::new_unchecked::<T>();

        let ptr = self.alloc(layout)?;
        let ptr = ptr.cast::<T>().as_ptr();

        ptr::write(ptr, val);
        Ok(&mut *ptr)
    }
}

The BumpAlloc struct implements the AllocRef trait, allowing the self.alloc(layout) call. For reasons explained in the previous thread, the alloc_t function needs to be a shared reference (&self). As long as the AllocRef::alloc function requires a mutable ref (&mut self), I don't see how @Ericson2314's proposed solution would prevent the borrow checker from throwing an error.

[Wodann]

@TimDiekmann, I extended @95th's implementation of bumpalo by generalizing the bump allocator over a AllocRef chunk allocator. The changes are bundled in this single commit. It should give an idea of the new traits in a practical example.

Some general feedback:

• For the bump allocator use case, the BuildAllocRef didn't add any desired functionality. I did find the usability a bit complex. It took some time before I had figured out the inter-connectedness. I am not sure when one would employ the BuildAllocRef. If there is no demonstrated use case yet, it might be good to create a sample. Or if there isn't any, maybe consider simplifying the interfaces by removing it.
• I like the subdivision between DeallocRef, AllocRef, and ReallocRef. It allows you to specify increasing constraints depending on the use case.
• I ended up working around the &mut self restriction of trait functions by calling a shared reference member function that employs a RefCell to create internal mutability. This way it's possible to have stricter constraints (i.e. mutable referencing) on traits while not requiring it for the struct itself.

Feel free to give feedback on the design/implementation.

[TimDiekmann]

Thanks for the feedback @Wodann! I'll look into your commit as soon as I have a bit more free time 😄

For the bump allocator use case, the BuildAllocRef didn't add any

The BuildAllocRef was initially proposed by @scottjmaddox. Maybe he can say a few words regarding this. Note, that in the issue are more links, which still uses the old name AllocFrom. I proposed to change this to BuildAlloc, as it's acting similary to BuildHasher.

I like the subdivision between DeallocRef, AllocRef, and ReallocRef.

Nice to hear! With this it should also be easier to interface FFI.

I ended up working around the &mut self restriction of trait functions by calling a shared reference member function that employs a RefCell to create internal mutability.

Can't say, if I like this or not. On the one hand, internal mutability is pretty flexible and a solution to this. On the other hand it always introduces an overhead, especially with multithreading.
When using &self instead, the internal mutability has to be moved into the allocator implementation.
The global allocator uses &self, the old Alloc trait uses &mut self.

[scottjmaddox]

@Wodann Please let me know if the use case for BuildAllocRef still doesn't make sense after reading through rust-lang/wg-allocators#12. And if there are specific questions you have after reading that issue, please share them, to help guide me. Thanks!

[Wodann]

Having read that, it makes a lot more sense @scottjmaddox for the use cases you mention.

@TimDiekmann Did you have time to take a look at my use case? The Rust All-Hands 2020 is coming up in March and if possible I'd like your alloc-wg crate integration into nightly to be one of the topics brought up there as beneficial to gamedev.

[TimDiekmann]

@Wodann with your use case, I guess you mean your bump allocator and TimDiekmann/alloc-wg#11?

Yes, I have tested around with it. I think, the problem isn't the mutable AllocRef, but the BuildAllocRef trait, which constructs the AllocRef, but returns Self::AllocRef rather than a reference. I think the design idea of having a dedicated BuildAllocRef is nice, but flawed and won't work out for 95% of the non-ZST allocators.
Anyway, before dropping this idea, I have thinked a lot about altering the signatur of the (De/Re-)AllocRef methods to take self instead of &mut self or &self. In rust-lang/rust#32838 this was already discussed and basically rejected.
The Idea was a oneshot-allocator, but this would apply to all other allocators, too, but this isn't true. As the name says, AllocRef shouldn't hold the state itself, but borrow it, so implementing AllocRef for e.g. &BumpAlloc or &mut BumpAlloc is maybe the best solution here.

What do you think?

[Wodann]

@TimDiekmann I tried you new API design. (see commit) I like that this API allows the implementer to designate whether they are passing by value, shared reference, or mutable reference.

Is there are reason why the BuildAllocRef::build_alloc_ref and DeallocRef::get_build_alloc still receive a mutable reference?

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

fn get_build_alloc(&mut self) -> Self::BuildAlloc {
    self
}

[TimDiekmann]

@Wodann

I like [...] this API

Nice to hear! I have posted a proposal to wg-allocators.

• BuildAllocRef::build_alloc_ref:
  As BuildAllocRef should act similiary to BuildHasher and is probably implemented on the struct itself, not on a reference, it should take &mut self. IMO it feels more intuitive. However, if this blocks implementation in any way, self could be used as well

• DeallocRef::get_build_alloc:
  I guess I simply forgot to change the signature 😄