| 1 |
# `bumpalo` |
| 2 |
|
| 3 |
**A fast bump allocation arena for Rust.** |
| 4 |
|
| 5 |
[](https://docs.rs/bumpalo/) |
| 6 |
[](https://crates.io/crates/bumpalo) |
| 7 |
[](https://crates.io/crates/bumpalo) |
| 8 |
[](https://github.com/fitzgen/bumpalo/actions?query=workflow%3ARust) |
| 9 |
|
| 10 |
 |
| 11 |
|
| 12 |
### Bump Allocation |
| 13 |
|
| 14 |
Bump allocation is a fast, but limited approach to allocation. We have a chunk |
| 15 |
of memory, and we maintain a pointer within that memory. Whenever we allocate an |
| 16 |
object, we do a quick check that we have enough capacity left in our chunk to |
| 17 |
allocate the object and then update the pointer by the object's size. *That's |
| 18 |
it!* |
| 19 |
|
| 20 |
The disadvantage of bump allocation is that there is no general way to |
| 21 |
deallocate individual objects or reclaim the memory region for a |
| 22 |
no-longer-in-use object. |
| 23 |
|
| 24 |
These trade offs make bump allocation well-suited for *phase-oriented* |
| 25 |
allocations. That is, a group of objects that will all be allocated during the |
| 26 |
same program phase, used, and then can all be deallocated together as a group. |
| 27 |
|
| 28 |
### Deallocation en Masse, but no `Drop` |
| 29 |
|
| 30 |
To deallocate all the objects in the arena at once, we can simply reset the bump |
| 31 |
pointer back to the start of the arena's memory chunk. This makes mass |
| 32 |
deallocation *extremely* fast, but allocated objects' [`Drop`] implementations are |
| 33 |
not invoked. |
| 34 |
|
| 35 |
> **However:** [`bumpalo::boxed::Box<T>`][box] can be used to wrap |
| 36 |
> `T` values allocated in the `Bump` arena, and calls `T`'s `Drop` |
| 37 |
> implementation when the `Box<T>` wrapper goes out of scope. This is similar to |
| 38 |
> how [`std::boxed::Box`] works, except without deallocating its backing memory. |
| 39 |
|
| 40 |
[`Drop`]: https://doc.rust-lang.org/std/ops/trait.Drop.html |
| 41 |
[box]: https://docs.rs/bumpalo/latest/bumpalo/boxed/struct.Box.html |
| 42 |
[`std::boxed::Box`]: https://doc.rust-lang.org/std/boxed/struct.Box.html |
| 43 |
|
| 44 |
### What happens when the memory chunk is full? |
| 45 |
|
| 46 |
This implementation will allocate a new memory chunk from the global allocator |
| 47 |
and then start bump allocating into this new memory chunk. |
| 48 |
|
| 49 |
### Example |
| 50 |
|
| 51 |
```rust |
| 52 |
use bumpalo::Bump; |
| 53 |
use std::u64; |
| 54 |
|
| 55 |
struct Doggo { |
| 56 |
cuteness: u64, |
| 57 |
age: u8, |
| 58 |
scritches_required: bool, |
| 59 |
} |
| 60 |
|
| 61 |
// Create a new arena to bump allocate into. |
| 62 |
let bump = Bump::new(); |
| 63 |
|
| 64 |
// Allocate values into the arena. |
| 65 |
let scooter = bump.alloc(Doggo { |
| 66 |
cuteness: u64::max_value(), |
| 67 |
age: 8, |
| 68 |
scritches_required: true, |
| 69 |
}); |
| 70 |
|
| 71 |
// Exclusive, mutable references to the just-allocated value are returned. |
| 72 |
assert!(scooter.scritches_required); |
| 73 |
scooter.age += 1; |
| 74 |
``` |
| 75 |
|
| 76 |
### Collections |
| 77 |
|
| 78 |
When the `"collections"` cargo feature is enabled, a fork of some of the `std` |
| 79 |
library's collections are available in the [`collections`] module. These |
| 80 |
collection types are modified to allocate their space inside `bumpalo::Bump` |
| 81 |
arenas. |
| 82 |
|
| 83 |
[`collections`]: https://docs.rs/bumpalo/latest/bumpalo/collections/index.html |
| 84 |
|
| 85 |
```rust |
| 86 |
#[cfg(feature = "collections")] |
| 87 |
{ |
| 88 |
use bumpalo::{Bump, collections::Vec}; |
| 89 |
|
| 90 |
// Create a new bump arena. |
| 91 |
let bump = Bump::new(); |
| 92 |
|
| 93 |
// Create a vector of integers whose storage is backed by the bump arena. The |
| 94 |
// vector cannot outlive its backing arena, and this property is enforced with |
| 95 |
// Rust's lifetime rules. |
| 96 |
let mut v = Vec::new_in(&bump); |
| 97 |
|
| 98 |
// Push a bunch of integers onto `v`! |
| 99 |
for i in 0..100 { |
| 100 |
v.push(i); |
| 101 |
} |
| 102 |
} |
| 103 |
``` |
| 104 |
|
| 105 |
Eventually [all `std` collection types will be parameterized by an |
| 106 |
allocator](https://github.com/rust-lang/rust/issues/42774) and we can remove |
| 107 |
this `collections` module and use the `std` versions. |
| 108 |
|
| 109 |
For unstable, nightly-only support for custom allocators in `std`, see the |
| 110 |
`allocator_api` section below. |
| 111 |
|
| 112 |
### `bumpalo::boxed::Box` |
| 113 |
|
| 114 |
When the `"boxed"` cargo feature is enabled, a fork of `std::boxed::Box` |
| 115 |
is available in the `boxed` module. This `Box` type is modified to allocate its |
| 116 |
space inside `bumpalo::Bump` arenas. |
| 117 |
|
| 118 |
**A `Box<T>` runs `T`'s drop implementation when the `Box<T>` is dropped.** You |
| 119 |
can use this to work around the fact that `Bump` does not drop values allocated |
| 120 |
in its space itself. |
| 121 |
|
| 122 |
```rust |
| 123 |
#[cfg(feature = "boxed")] |
| 124 |
{ |
| 125 |
use bumpalo::{Bump, boxed::Box}; |
| 126 |
use std::sync::atomic::{AtomicUsize, Ordering}; |
| 127 |
|
| 128 |
static NUM_DROPPED: AtomicUsize = AtomicUsize::new(0); |
| 129 |
|
| 130 |
struct CountDrops; |
| 131 |
|
| 132 |
impl Drop for CountDrops { |
| 133 |
fn drop(&mut self) { |
| 134 |
NUM_DROPPED.fetch_add(1, Ordering::SeqCst); |
| 135 |
} |
| 136 |
} |
| 137 |
|
| 138 |
// Create a new bump arena. |
| 139 |
let bump = Bump::new(); |
| 140 |
|
| 141 |
// Create a `CountDrops` inside the bump arena. |
| 142 |
let mut c = Box::new_in(CountDrops, &bump); |
| 143 |
|
| 144 |
// No `CountDrops` have been dropped yet. |
| 145 |
assert_eq!(NUM_DROPPED.load(Ordering::SeqCst), 0); |
| 146 |
|
| 147 |
// Drop our `Box<CountDrops>`. |
| 148 |
drop(c); |
| 149 |
|
| 150 |
// Its `Drop` implementation was run, and so `NUM_DROPS` has been |
| 151 |
// incremented. |
| 152 |
assert_eq!(NUM_DROPPED.load(Ordering::SeqCst), 1); |
| 153 |
} |
| 154 |
``` |
| 155 |
|
| 156 |
#### Serde |
| 157 |
|
| 158 |
Adding the `serde` feature flag will enable transparent serialization of Vecs and |
| 159 |
boxed values. |
| 160 |
|
| 161 |
```toml |
| 162 |
[dependencies] |
| 163 |
bumpalo = { version = "3.9", features = ["collections", "boxed", "serde"] } |
| 164 |
``` |
| 165 |
|
| 166 |
```rust,ignore |
| 167 |
use bumpalo::{Bump, boxed::Box, collections::Vec}; |
| 168 |
|
| 169 |
// Create a new bump arena. |
| 170 |
let bump = Bump::new(); |
| 171 |
|
| 172 |
// Create a `Box` |
| 173 |
let box = Box::new_in("hello", &bump); |
| 174 |
|
| 175 |
// Serialize with serde_json |
| 176 |
assert_eq!(serde_json::to_string(&box).unwrap(), "\"hello\""); |
| 177 |
|
| 178 |
// Create a `Vec` |
| 179 |
let vec = Vec::new_in( &bump); |
| 180 |
vec.push(1); |
| 181 |
vec.push(2); |
| 182 |
|
| 183 |
// Serialize with serde_json |
| 184 |
assert_eq!(serde_json::to_string(&vec).unwrap(), "[1, 2]"); |
| 185 |
``` |
| 186 |
|
| 187 |
### `#![no_std]` Support |
| 188 |
|
| 189 |
Bumpalo is a `no_std` crate by default. It depends only on the `alloc` and `core` crates. |
| 190 |
|
| 191 |
### `std` Support |
| 192 |
|
| 193 |
You can optionally decide to enable the `std` feature in order to enable some |
| 194 |
std only trait implementations for some collections: |
| 195 |
|
| 196 |
* `std::io::Write` for `Vec<'bump, u8>` |
| 197 |
|
| 198 |
### Thread support |
| 199 |
|
| 200 |
The `Bump` is `!Sync`, which makes it hard to use in certain situations around |
| 201 |
threads ‒ for example in `rayon`. |
| 202 |
|
| 203 |
The [`bumpalo-herd`](https://crates.io/crates/bumpalo-herd) crate provides a |
| 204 |
pool of `Bump` allocators for use in such situations. |
| 205 |
|
| 206 |
### Nightly Rust `allocator_api` Support |
| 207 |
|
| 208 |
The unstable, nightly-only Rust `allocator_api` feature defines an [`Allocator`] |
| 209 |
trait and exposes custom allocators for `std` types. Bumpalo has a matching |
| 210 |
`allocator_api` cargo feature to enable implementing `Allocator` and using |
| 211 |
`Bump` with `std` collections. Note that, as `feature(allocator_api)` is |
| 212 |
unstable and only in nightly Rust, Bumpalo's matching `allocator_api` cargo |
| 213 |
feature should be considered unstable, and will not follow the semver |
| 214 |
conventions that the rest of the crate does. |
| 215 |
|
| 216 |
First, enable the `allocator_api` feature in your `Cargo.toml`: |
| 217 |
|
| 218 |
```toml |
| 219 |
[dependencies] |
| 220 |
bumpalo = { version = "3", features = ["allocator_api"] } |
| 221 |
``` |
| 222 |
|
| 223 |
Next, enable the `allocator_api` nightly Rust feature in your `src/lib.rs` or |
| 224 |
`src/main.rs`: |
| 225 |
|
| 226 |
```rust,ignore |
| 227 |
#![feature(allocator_api)] |
| 228 |
``` |
| 229 |
|
| 230 |
Finally, use `std` collections with `Bump`, so that their internal heap |
| 231 |
allocations are made within the given bump arena: |
| 232 |
|
| 233 |
```rust,ignore |
| 234 |
use bumpalo::Bump; |
| 235 |
|
| 236 |
// Create a new bump arena. |
| 237 |
let bump = Bump::new(); |
| 238 |
|
| 239 |
// Create a `Vec` whose elements are allocated within the bump arena. |
| 240 |
let mut v = Vec::new_in(&bump); |
| 241 |
v.push(0); |
| 242 |
v.push(1); |
| 243 |
v.push(2); |
| 244 |
``` |
| 245 |
|
| 246 |
[`Allocator`]: https://doc.rust-lang.org/std/alloc/trait.Allocator.html |
| 247 |
|
| 248 |
### Using the `Allocator` API on Stable Rust |
| 249 |
|
| 250 |
You can enable the `allocator-api2` Cargo feature and `bumpalo` will use [the |
| 251 |
`allocator-api2` crate](https://crates.io/crates/allocator-api2) to implement |
| 252 |
the unstable nightly`Allocator` API on stable Rust. This means that |
| 253 |
`bumpalo::Bump` will be usable with any collection that is generic over |
| 254 |
`allocator_api2::Allocator`. |
| 255 |
|
| 256 |
### Minimum Supported Rust Version (MSRV) |
| 257 |
|
| 258 |
This crate is guaranteed to compile on stable Rust **1.73** and up. It might |
| 259 |
compile with older versions but that may change in any new patch release. |
| 260 |
|
| 261 |
We reserve the right to increment the MSRV on minor releases, however we will |
| 262 |
strive to only do it deliberately and for good reasons. |