Crate bump_scope

Expand description

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

Changelog - Crates.io - Repository

§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. When its chunk is full, this allocator 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 (but ignores the title).

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 allocate a slice from any Iterator with alloc_iter.
Every method that panics on allocation failure has a fallible try_* counterpart.
Bump’s base allocator is generic.
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 tiny bit more optimized. See ./crates/callgrind-benches.
You can choose the bump direction. Bumps upwards by default.

§Allocator Methods

The bump allocator provides many methods to conveniently allocate values, strings, and slices. Have a look at the documentation of Bump for a method overview.

§Scopes and Checkpoints

You can create scopes to make allocations that live only for a part of its parent scope. Entering 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 position.

let bump: Bump = Bump::new();
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);

§Collections

bump-scope provides bump allocated variants of Vec and String called BumpVec and BumpString. They are also available in the following variants:

Fixed* for fixed capacity collections
Mut* for collections optimized for a mutable bump allocator

§API changes

The collections are designed to have the same api as their std counterparts with these exceptions:

split_off — splits the collection in place without allocation; the parameter is a range instead of a single index
retain — takes a closure with a &mut T parameter like Vec::retain_mut

§New features

append — allows appending all kinds of owned slice types like [T; N], Box<[T]>, Vec<T>, vec::Drain<T> etc.
map — maps the elements, potentially reusing the existing allocation
map_in_place — maps the elements without allocation, failing to compile if not possible
conversions between the regular collections, their Fixed* variants and BumpBox<[T]> / BumpBox<str>

§Parallel Allocation

Bump is !Sync which means it can’t be shared between threads.

To bump allocate in parallel you can use a BumpPool.

§Allocator API

Bump and BumpScope implement bump-scope’s own Allocator trait and with the respective feature flags also implement allocator_api2@0.2, allocator_api2@0.3 and nightly’s Allocator trait. All of these traits mirror the nightly Allocator trait at the time of writing.

This allows you to bump allocate collections.

A bump allocator can grow, shrink and deallocate the most recent allocation. When bumping upwards it can even do so in place. Growing allocations other than the most recent one will require a new allocation and the old memory block becomes wasted space. Shrinking or deallocating allocations other than the most recent one 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, calling reset or dropping the Bump. You can wrap a bump allocator in a type that makes deallocate and shrink a no-op using WithoutDealloc and WithoutShrink.

use bump_scope::{Bump, WithoutDealloc};
use allocator_api2_03::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, WithoutDealloc(&bump));
assert_eq!(bump.stats().allocated(), 4);
drop(boxed);
assert_eq!(bump.stats().allocated(), 4);

§Feature Flags

std (enabled by default) — Adds BumpPool and implementations of std::io traits.
alloc (enabled by default) — Adds Global as the default base allocator and some interactions with alloc collections.
panic-on-alloc (enabled by default) — Adds functions and traits that will panic when the allocation fails. Without this feature, allocation failures cannot cause panics, and only try_-prefixed allocation methods will be available.
serde — Adds Serialize implementations for BumpBox, strings and vectors, and DeserializeSeed for strings and vectors.
bytemuck — Adds bytemuck::* extension traits for alloc_zeroed(_slice), BumpBox::init_zeroed and resize_zeroed and extend_zeroed for vector types.
zerocopy-08 — Adds zerocopy_08::* extension traits for alloc_zeroed(_slice), BumpBox::init_zeroed and resize_zeroed and extend_zeroed for vector types.
allocator-api2-02 — Makes Bump(Scope) implement allocator_api2 version 0.2’s Allocator and makes it possible to use an allocator_api2::alloc::Allocator as a base allocator via AllocatorApi2V02Compat.
allocator-api2-03 — Makes Bump(Scope) implement allocator_api2 version 0.3’s Allocator and makes it possible to use an allocator_api2::alloc::Allocator as a base allocator via AllocatorApi2V03Compat.

§Nightly features

These nightly features are not subject to the same semver guarantees as the rest of the library. Breaking changes to these features might be introduced in minor releases to keep up with changes in the nightly channel.

nightly — Enables all other nightly feature flags.
nightly-allocator-api — Makes Bump(Scope) implement alloc’s Allocator and allows using an alloc::alloc::Allocator as a base allocator via AllocatorNightlyCompat.

This will also enable allocator-api2 version 0.2’s nightly feature.
nightly-coerce-unsized — Makes BumpBox<T> implement CoerceUnsized. With this BumpBox<[i32;3]> coerces to BumpBox<[i32]>, BumpBox<dyn Debug> and so on. You can unsize a BumpBox in stable without this feature using unsize_bump_box.
nightly-exact-size-is-empty — Implements is_empty manually for some iterators.
nightly-trusted-len — Implements TrustedLen for some iterators.
nightly-fn-traits — Implements Fn* traits for BumpBox<T>. Makes BumpBox<T: FnOnce + ?Sized> callable. Requires alloc crate.
nightly-tests — Enables some tests that require a nightly compiler.
nightly-dropck-eyepatch — Adds #[may_dangle] attribute to box and vector types’ drop implementation. This makes it so references don’t have to strictly outlive the container. (That’s how std’s Box and Vec work.)
nightly-clone-to-uninit — Adds alloc_clone method to Bump(Scope).

§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. This benefits collections as well as alloc_iter(_mut) and alloc_fmt(_mut) with the exception of MutBumpVecRev and alloc_iter_mut_rev which can be grown and shrunk in place if and only if bumping downwards.

Bumping downwards can be done in less instructions.

For the performance impact see ./crates/callgrind-benches.

§What is minimum alignment?

Minimum alignment is the alignment the bump pointer maintains when doing allocations.

When allocating a type in a bump allocator with a sufficient minimum alignment, the bump pointer will not have to be aligned for the allocation but the allocation size will need to be rounded up to the next multiple of the minimum alignment.

For example changing the minimum alignment to 4 makes it so allocations with the alignment of 4 don’t need to align the bump pointer anymore. This will penalize allocations whose sizes are not a multiple of 4 as their size now needs to be rounded up the next multiple of 4.

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

For the performance impact see ./crates/callgrind-benches.

§What does guaranteed allocated mean?

A guaranteed allocated bump allocator will own at least one chunk that it has allocated from its base allocator.

The constructors new, with_size, with_capacity and their variants always allocate one chunk from the base allocator.

The exception is the unallocated constructor which creates a Bump without allocating any chunks. Such a Bump will have the GUARANTEED_ALLOCATED generic parameter of false which will make the scoped, scoped_aligned, aligned and scope_guard methods unavailable.

You can turn any non-GUARANTEED_ALLOCATED bump allocator into a guaranteed allocated one using as_guaranteed_allocated, as_mut_guaranteed_allocated or into_guaranteed_allocated.

The point of this is so Bumps can be const constructed and constructed without allocating. At the same time Bumps that have already allocated a chunk don’t suffer additional runtime checks.

Modules§

CHANGELOG: Changelog
alloc: Memory allocation APIs.
bump_vec: Contains BumpVec and associated types.
bytemuckbytemuck: Contains extension traits.
mut_bump_vec: Contains MutBumpVec and associated types.
owned_slice: Contains types associated with owned slices.
owned_str: Contains types associated with owned strings.
stats: Contains types for inspecting memory usage in bump allocators.
zerocopy_08zerocopy-08: Contains extension traits.

Macros§

bump_format: This is like format! but allocates inside a bump allocator, returning a BumpString.
bump_vec: This is like vec! but allocates inside a bump allocator, returning a BumpVec.
mut_bump_format: This is like format! but allocates inside a mutable bump allocator, returning a MutBumpString.
mut_bump_vec: This is like vec! but allocates inside a bump allocator, returning a MutBumpVec.
mut_bump_vec_rev: This is like vec! but allocates inside a bump allocator, returning a MutBumpVecRev.
unsize_bump_box: Allows unsizing to be performed on T of BumpBox<T>.

Structs§

Bump: The 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.
BumpPoolstd: A pool of bump allocators.
BumpPoolGuardstd: This is a wrapper around Bump that mutably derefs to a BumpScope and returns its Bump back to the BumpPool on drop.
BumpScope: A bump allocation scope.
BumpScopeGuard: Returned from BumpScope::scope_guard.
BumpScopeGuardRoot: Returned from Bump::scope_guard.
BumpString: A bump allocated String.
BumpVec: A bump allocated Vec.
Checkpoint: This is returned from checkpoint and used for reset_to.
FixedBumpString: A type like BumpString but with a fixed capacity.
FixedBumpVec: A type like BumpVec but with a fixed capacity.
FromUtf8Error: A possible error value when converting a string from a UTF-8 byte vector.
FromUtf16Error: A possible error value when converting a string from a UTF-16 byte slice.
MinimumAlignment: Specifies the current minimum alignment of a bump allocator.
MutBumpString: A type like BumpString, optimized for a mutable bump allocator.
MutBumpVec: A type like BumpVec, optimized for a mutable bump allocator.
MutBumpVecRev: A type like MutBumpVec but new elements are pushed to the front.
WithoutDealloc: Wraps a bump allocator and does nothing on deallocate.
WithoutShrink: Wraps a bump allocator and does nothing on shrink.

Traits§

BaseAllocator: Trait that the base allocator of a Bump is required to implement to make allocations.
BumpAllocator: A bump allocator.
BumpAllocatorExt: An extension trait for BumpAllocators.
BumpAllocatorScope: A bump allocator scope.
BumpAllocatorScopeExt: A shorthand for BumpAllocatorScope<’a> + BumpAllocatorExt
MutBumpAllocator: A marker trait for BumpAllocators who have exclusive access to allocation.
MutBumpAllocatorExt: A shorthand for MutBumpAllocator + BumpAllocatorExt
MutBumpAllocatorScope: A shorthand for MutBumpAllocator + BumpAllocatorScope<’a>
MutBumpAllocatorScopeExt: A shorthand for MutBumpAllocatorScope<’a> + MutBumpAllocatorExt
NoDrop: This trait marks types that don’t need dropping.
SupportedMinimumAlignment: Statically guarantees that a minimum alignment is marked as supported.

Crate bump_scope

Crate bump_scope Copy item path

§What is bump allocation?

§Comparison to bumpalo

§Allocator Methods

§Scopes and Checkpoints

§Collections

§API changes

§New features

§Parallel Allocation

§Allocator API

§Feature Flags

§Nightly features

§Bumping upwards or downwards?

§What is minimum alignment?

§What does guaranteed allocated mean?

Modules§

Macros§

Structs§

Traits§

Crate bump_scope

§Comparison to `bumpalo`