README.md
1# `bumpalo`
2
3
4**A fast bump allocation arena for Rust.**
5
6[![](https://docs.rs/bumpalo/badge.svg)](https://docs.rs/bumpalo/)
7[![](https://img.shields.io/crates/v/bumpalo.svg)](https://crates.io/crates/bumpalo)
8[![](https://img.shields.io/crates/d/bumpalo.svg)](https://crates.io/crates/bumpalo)
9[![Build Status](https://dev.azure.com/fitzgen/bumpalo/_apis/build/status/fitzgen.bumpalo?branchName=master)](https://dev.azure.com/fitzgen/bumpalo/_build/latest?definitionId=2&branchName=master)
10
11![](https://github.com/fitzgen/bumpalo/raw/master/bumpalo.png)
12
13### Bump Allocation
14
15Bump allocation is a fast, but limited approach to allocation. We have a chunk
16of memory, and we maintain a pointer within that memory. Whenever we allocate an
17object, we do a quick test that we have enough capacity left in our chunk to
18allocate the object and then update the pointer by the object's size. *That's
19it!*
20
21The disadvantage of bump allocation is that there is no general way to
22deallocate individual objects or reclaim the memory region for a
23no-longer-in-use object.
24
25These trade offs make bump allocation well-suited for *phase-oriented*
26allocations. That is, a group of objects that will all be allocated during the
27same program phase, used, and then can all be deallocated together as a group.
28
29### Deallocation en Masse, but No `Drop`
30
31To deallocate all the objects in the arena at once, we can simply reset the bump
32pointer back to the start of the arena's memory chunk. This makes mass
33deallocation *extremely* fast, but allocated objects' `Drop` implementations are
34not invoked.
35
36> **However:** [`bumpalo::boxed::Box<T>`][crate::boxed::Box] can be used to wrap
37> `T` values allocated in the `Bump` arena, and calls `T`'s `Drop`
38> implementation when the `Box<T>` wrapper goes out of scope. This is similar to
39> how [`std::boxed::Box`] works, except without deallocating its backing memory.
40
41[`std::boxed::Box`]: https://doc.rust-lang.org/std/boxed/struct.Box.html
42
43### What happens when the memory chunk is full?
44
45This implementation will allocate a new memory chunk from the global allocator
46and then start bump allocating into this new memory chunk.
47
48### Example
49
50```rust
51use bumpalo::Bump;
52use std::u64;
53
54struct Doggo {
55 cuteness: u64,
56 age: u8,
57 scritches_required: bool,
58}
59
60// Create a new arena to bump allocate into.
61let bump = Bump::new();
62
63// Allocate values into the arena.
64let scooter = bump.alloc(Doggo {
65 cuteness: u64::max_value(),
66 age: 8,
67 scritches_required: true,
68});
69
70assert!(scooter.scritches_required);
71```
72
73### Collections
74
75When the `"collections"` cargo feature is enabled, a fork of some of the `std`
76library's collections are available in the `collections` module. These
77collection types are modified to allocate their space inside `bumpalo::Bump`
78arenas.
79
80```rust
81use bumpalo::{Bump, collections::Vec};
82
83// Create a new bump arena.
84let bump = Bump::new();
85
86// Create a vector of integers whose storage is backed by the bump arena. The
87// vector cannot outlive its backing arena, and this property is enforced with
88// Rust's lifetime rules.
89let mut v = Vec::new_in(&bump);
90
91// Push a bunch of integers onto `v`!
92for i in 0..100 {
93 v.push(i);
94}
95```
96
97Eventually [all `std` collection types will be parameterized by an
98allocator](https://github.com/rust-lang/rust/issues/42774) and we can remove
99this `collections` module and use the `std` versions.
100
101### `bumpalo::boxed::Box`
102
103When the `"boxed"` cargo feature is enabled, a fork of `std::boxed::Box` library
104is available in the `boxed` module. This `Box` type is modified to allocate its
105space inside `bumpalo::Bump` arenas.
106
107**A `Box<T>` runs `T`'s drop implementation when the `Box<T>` is dropped.** You
108can use this to work around the fact that `Bump` does not drop values allocated
109in its space itself.
110
111```rust
112use bumpalo::{Bump, boxed::Box};
113use std::sync::atomic::{AtomicUsize, Ordering};
114
115static NUM_DROPPED: AtomicUsize = AtomicUsize::new(0);
116
117struct CountDrops;
118
119impl Drop for CountDrops {
120 fn drop(&mut self) {
121 NUM_DROPPED.fetch_add(1, Ordering::SeqCst);
122 }
123}
124
125// Create a new bump arena.
126let bump = Bump::new();
127
128// Create a `CountDrops` inside the bump arena.
129let mut c = Box::new_in(CountDrops, &bump);
130
131// No `CountDrops` have been dropped yet.
132assert_eq!(NUM_DROPPED.load(Ordering::SeqCst), 0);
133
134// Drop our `Box<CountDrops>`.
135drop(c);
136
137// Its `Drop` implementation was run, and so `NUM_DROPS` has been incremented.
138assert_eq!(NUM_DROPPED.load(Ordering::SeqCst), 1);
139```
140
141### `#![no_std]` Support
142
143Bumpalo is a `no_std` crate. It depends only on the `alloc` and `core` crates.
144
145
README.tpl
1# `{{crate}}`
2
3{{readme}}
4