Crate bump_scope

A fast bump allocator that supports allocation scopes / checkpoints. Aka an arena for values of arbitrary types.

What is bump allocation?

A bump allocator owns a big chunk of memory. It has a pointer that starts at one end of that chunk. When an allocation is made that pointer gets aligned and bumped towards the other end of the chunk by the allocation’s size. When its chunk is full, it allocates another chunk with twice the size.

This makes allocations very fast. The drawback is that you can’t reclaim memory like you do with a more general allocator. Memory for the most recent allocation can be reclaimed. You can also use scopes, checkpoints and reset to reclaim memory.

A bump allocator is great for phase-oriented allocations where you allocate objects in a loop and free them at the end of every iteration.

use bump_scope::Bump;
let mut bump: Bump = Bump::new();

loop {
    // use bump ...
    bump.reset();
}

The fact that the bump allocator allocates ever larger chunks and reset only keeps around the largest one means that after a few iterations, every bump allocation will be done on the same chunk and no more chunks need to be allocated.

The introduction of scopes makes this bump allocator also great for temporary allocations and stack-like usage.

Comparison to bumpalo

Bumpalo is a popular crate for bump allocation. This crate was inspired by bumpalo and Always Bump Downwards.

Unlike bumpalo, this crate…

• Supports scopes and checkpoints.
• Drop is always called for allocated values unless explicitly leaked or forgotten.
  • alloc* methods return a BumpBox<T> which owns and drops T. Types that don’t need dropping can be turned into references with into_ref and into_mut.
• You can efficiently allocate items from any Iterator with alloc_iter_mut(_rev).
• Every method that panics on allocation failure has a fallible try_* counterpart.
• Bump’s base allocator is generic.
• Bump needs to allocate on construction.
• Bump and BumpScope have the same repr as NonNull<u8>. (vs 3x pointer sized)
• Won’t try to allocate a smaller chunk if allocation failed.
• No built-in allocation limit. You can provide an allocator that enforces an allocation limit (see tests/limit_memory_usage.rs).
• Allocations are a bit more optimized. (see crates/inspect-asm/out/x86-64)
• You can choose the bump direction. Bumps upwards by default.
• You can choose the minimum alignment.

Scopes and Checkpoints

You can create scopes to make allocations that live only for a part of its parent scope. Creating and exiting scopes is virtually free. Allocating within a scope has no overhead.

You can create a new scope either with a scoped closure or with a scope_guard:

use bump_scope::Bump;

let mut bump: Bump = Bump::new();

// you can use a closure
bump.scoped(|mut bump| {
    let hello = bump.alloc_str("hello");
    assert_eq!(bump.stats().allocated(), 5);
     
    bump.scoped(|bump| {
        let world = bump.alloc_str("world");

        println!("{hello} and {world} are both live");
        assert_eq!(bump.stats().allocated(), 10);
    });
     
    println!("{hello} is still live");
    assert_eq!(bump.stats().allocated(), 5);
});

assert_eq!(bump.stats().allocated(), 0);

// or you can use scope guards
{
    let mut guard = bump.scope_guard();
    let mut bump = guard.scope();

    let hello = bump.alloc_str("hello");
    assert_eq!(bump.stats().allocated(), 5);
     
    {
        let mut guard = bump.scope_guard();
        let bump = guard.scope();

        let world = bump.alloc_str("world");

        println!("{hello} and {world} are both live");
        assert_eq!(bump.stats().allocated(), 10);
    }
     
    println!("{hello} is still live");
    assert_eq!(bump.stats().allocated(), 5);
}

assert_eq!(bump.stats().allocated(), 0);

You can also use the unsafe checkpoint api to reset the bump pointer to a previous location.

let checkpoint = bump.checkpoint();

{
    let hello = bump.alloc_str("hello");
    assert_eq!(bump.stats().allocated(), 5);
}

unsafe { bump.reset_to(checkpoint); }
assert_eq!(bump.stats().allocated(), 0);

Allocator API

Bump and BumpScope implement allocator_api2::alloc::Allocator. With this you can bump allocate allocator_api2::boxed::Box, allocator_api2::vec::Vec and collections from other crates that support it like hashbrown::HashMap.

A bump allocator can grow, shrink and deallocate the most recent allocation. When bumping upwards it can even do so in place. Growing other allocations will require a new allocation and the old memory block becomes wasted space. Shrinking or deallocating other allocations does nothing which means wasted space.

A bump allocator does not require deallocate or shrink to free memory. After all, memory will be reclaimed when exiting a scope or calling reset. You can wrap a bump allocator in a type that makes deallocate and shrink a no-op using without_dealloc and without_shrink.

use bump_scope::Bump;
use allocator_api2::boxed::Box;
let bump: Bump = Bump::new();

let boxed = Box::new_in(5, &bump);
assert_eq!(bump.stats().allocated(), 4);
drop(boxed);
assert_eq!(bump.stats().allocated(), 0);

let boxed = Box::new_in(5, bump.without_dealloc());
assert_eq!(bump.stats().allocated(), 4);
drop(boxed);
assert_eq!(bump.stats().allocated(), 4);

Feature Flags

This crate supports no_std, unless the std feature is enabled.

• std (default):

  Adds implementations of std::io traits for BumpBox and (Fixed)BumpVec. Activates alloc feature.

• alloc (default):

  Adds implementations interacting with String and Cow<str>. Is required for alloc_iter and alloc_fmt.

• nightly-allocator-api (requires nightly):

  Enables allocator-api2’s nightly feature which makes it reexport the nightly allocator api instead of its own implementation. With this you can bump allocate collections from the standard library.

• nightly-coerce-unsized (requires nightly):

  Makes BumpBox<T> implement CoerceUnsized. With this BumpBox<[i32;3]> coerces to BumpBox<[i32]>, BumpBox<dyn Debug> and so on.

Bumping upwards or downwards?

Bump direction is controlled by the generic parameter const UP: bool. By default, UP is true, so the allocator bumps upwards.

• Bumping upwards…
  • has the advantage that the most recent allocation can be grown and shrunk in place.
  • makes alloc_iter(_mut) and alloc_fmt(_mut) faster.
• Bumping downwards…
  • uses slightly fewer instructions per allocation.
  • makes alloc_iter_mut_rev faster.

Minimum alignment?

The minimum alignment is controlled by the generic parameter const MIN_ALIGN: usize. By default, MIN_ALIGN is 1.

Changing the minimum alignment to e.g. 4 makes it so allocations with the alignment of 4 don’t need to align the bump pointer anymore. This will penalize allocations of a smaller alignment as their size now needs to be rounded up the next multiple of 4.

This amounts to about 1 or 2 instructions per allocation.

Re-exports

• pub use allocator_api2;

Macros

• bump_format
  This is like format! but allocates inside a mutable bump allocator, returning a BumpString.
• bump_vec
  Creates a BumpVec containing the arguments.
• bump_vec_rev
  Creates a BumpVecRev containing the arguments.

Structs

• Bump
  A bump allocator.
• BumpBox
  A pointer type that uniquely owns a bump allocation of type T. This type is returned whenever a bump allocation is made.
• BumpScope
  A bump allocation scope whose allocations are valid for the lifetime of its associated BumpScopeGuard or closure.
• BumpScopeGuard
  Returned from BumpScope::scope_guard.
• BumpScopeGuardRoot
  Returned from Bump::scope_guard.
• BumpString
  A type like String, optimized for exclusive bump allocation.
• BumpVec
  This is like a Vec but optimized for being allocated in a &mut Bump(Scope).
• BumpVecRev
  This is like a BumpVec, but new elements are pushed to the front.
• Checkpoint
  This is returned from checkpoint and used for reset_to.
• Chunk
  Refers to a chunk of memory that was allocated by the bump allocator.
• ChunkNextIter
  Iterator that iterates over next chunks by continuously calling Chunk::next.
• ChunkPrevIter
  Iterator that iterates over previous chunks by continuously calling Chunk::prev.
• Drain
  A draining iterator for BumpBox<[T]> and BumpVec<T>.
• ExtractIf
  An iterator which uses a closure to determine if an element should be removed.
• FixedBumpVec
  This is like a Vec but with a fixed capacity.
• FromUtf8Error
  A possible error value when converting a BumpString from a BumpVec<u8> or a BumpBox<str> from a BumpBox<[u8]> where the bytes are UTF-8.
• IntoIter
  An iterator that moves out of a BumpVec<T>, BumpVecRev<T> or BumpBox<[T]>.
• MinimumAlignment
  Specifies the current minimum alignment of a bump allocator.
• Stats
  Provides statistics about the memory usage of the bump allocator.
• WithLifetime
  Associates a lifetime to a wrapped type.
• WithoutDealloc
  Wraps an bump allocator and does nothing on deallocate.
• WithoutShrink
  Wraps an bump allocator and does nothing on shrink.

Traits

• BumpAllocator
  Allocators that don’t need to have deallocate or shrink being called, because they have another way of reclamation.
• NoDrop
  This trait marks types that don’t need dropping.
• SupportedMinimumAlignment
  Statically guarantees that a minimum alignment is marked as supported.