Simple bump allocator

[AngelicosPhosphoros]

It would be nice to have a simple bump allocator without extra tracking of freed blocks.
This would make generated machine code for common case shorter.

I imagine it would be like this:

#[repr(C)]
struct BumpStalloc<const L: usize, const B: usize> {
   _align: Align<B>,
   buffer: UnsafeCell<[MaybeUninit<[u8; B]>; L]>,
   next_free_block: usize,
   count_living_allocs: usize,
}

fn alloc(&self, layout: Layout)->Result<NonNull<[u8]>, AllocError>{
    let blocks = /* calc blocks */
    if self.next_free_block + blocks <= L {
        let res_ptr = (buffer.get() as *mut u8).add(self.next_free_block * L)
        self.next_free_block += blocks;
        self.count_living_allocs += 1;
        Ok(slice from res_ptr)
    } else {
        Err()
    }
}

fn grow(&self, layout: Layout)->Result<NonNull<[u8]>, AllocError>{
    if is_last() {
       try_extend();
    } else {
       Err()
    }
}

fn dealloc(&self, ptr, layout) {
    if is_last() {
       next_free_block -= length;
    }
    count_living_allocs -= 1;
    if count_living_allocs == 0 {
       // No living allocations, can safely reset.
       // next_free_block may be not naturally 0 if allocs/deallocs didn't
       // happen in stricly symmetrical fashion
       next_free_block = 0;
    }
}

[abgros]

@AngelicosPhosphoros Thanks for the suggestion. Before I implement this I would like to better understand what the expected use case is. The issues I see are:

• You absolutely have to allocate/deallocate symmetrically, or you will run out of memory very very quickly (other crates solve this by dynamically expanding the buffer on the heap).
• The count_living_allocs tracker is unnecessary if all of your allocations have a fixed lifetime, because you can just drop the entire allocator and recreate it practically for free
• Growing is problematic, trying to grow two vectors at the same time results in them constantly "hitting" each other and copying themselves (this can also happen in Stalloc but it's not as bad)

So I'm not convinced that that the performance gain of not having a free list is actually worthwhile...

[AngelicosPhosphoros]

Basically, the idea is to use combination of ChainAlloc<BumpStalloc, &Global> + Vec<T, ChainAlloc> as a replacement of smallvec on stack. This combination would be better than smallvec due to avoiding performance hit from branching on every indexing and push.

And the following scenarios:

1. allocator used in a single Vec that dropped only when exiting from current scope.

let stackalloc = BumpAlloc::<128, 4>::new().chain(&Global);

let mut some_vec: Vec<_> = some_iterator.collect_in(stackalloc);
// Never add items again or shrink until return

2. allocator used in a many Vecs but they never explicitly dropped so memory is freed in reverse order.

let stackalloc = BumpAlloc::<128, 4>::new().chain(&Global);
let v0 = /* create v0 */;
/* work with v0 */

// Never modify v0 after this point
let v1 = /* work with it */.

3. 90% calls do very simple thing

let stalloc: Stalloc<1024, 16> = Stalloc::new();
let allocator = BumpAlloc::<5, 4>::new().chain(&stalloc).chain(&Global);

let mut v = Vec::new_in(&allocator);
// Push to v up to 5 times
if this_condition_is_true_9_times_of_10 {
   return;
}
// Here complicated code starts to use more robust stalloc by chaining.

4. Repeated use in loops

let mut bump = BumpAlloc::<1024, 8>::new().chain(&Global);

for x in iter0 {
    let mut v = Vec::new_in(&bump);
    // add some to v.
    // ...
    while some_condition {
        // Here v is never modified
        let mut set = HashSet::new_in(&bump);
        // Work with set.
        // drop it in scope
    }
    // Here bump allocator returned to state it was before inner loop
    // so reallocs of inner buffer of v can use allocator again.
}

[abgros]

Oh I understand. I actually have created my own small vector optimization which I've benchmarked to be faster than both smallvec and std's Vec, and it avoids branching access by using a self-referential pointer (so it's immovable). Since each vector uses its own stack buffer you can grow multiple at the same time for no additional cost. I haven't released publicly it since I've only implemented a few APIs that I need (push and pop basically).