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