Debian Codegraph @

.cargo/vendor/bumpalo/README.md

raw
1 # `bumpalo`
2
3 **A fast bump allocation arena for Rust.**
4
5 [![](https://docs.rs/bumpalo/badge.svg)](https://docs.rs/bumpalo/)
6 [![](https://img.shields.io/crates/v/bumpalo.svg)](https://crates.io/crates/bumpalo)
7 [![](https://img.shields.io/crates/d/bumpalo.svg)](https://crates.io/crates/bumpalo)
8 [![Build Status](https://github.com/fitzgen/bumpalo/workflows/Rust/badge.svg)](https://github.com/fitzgen/bumpalo/actions?query=workflow%3ARust)
9
10 ![](https://github.com/fitzgen/bumpalo/raw/main/bumpalo.png)
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.