2 unstable releases
new 0.2.0 | Apr 26, 2025 |
---|---|
0.1.0 | Jan 7, 2025 |
#168 in Memory management
38KB
898 lines
contiguous-arena
contiguous-arena
is a Rust crate that provides a memory-efficient, contiguous data structure for managing collections of homogeneously-typed elements. It is designed to handle frequent allocations and deallocations efficiently by reusing freed memory spans.
The library is designed to allow for allocation of contiguous elements, such that:
- Appending an arbitrary amount of elements will allocate them in a contiguous memory block (
arena.append(T, count)
) - The arena uses
Vec<T>
as the backing buffer, unlike most arena crates which bundle metadata together with the item. This crate uses 2 additional buffers to store the span metadata, which makes it easier to iterate the arena with crates likerayon
or share it with the GPU, for example.
Features
- Memory-efficient storage by reusing freed spans.
- Contiguous memory layout for improved cache performance, easier iteration and GPU memory sharing.
- Support for arbitrary owned types. Note that the arena DOES NOT currently run
drop()
! (a PR would be appreciated) - Only depends on std. A PR adding
#![no_std]
support would be appreciated.
Be aware of memory fragmentation when using this library: frequest allocations of different sizes will eventually fragment the arena. This crate is ideal for use-cases where most allocations are about the same size.
Example
use contiguous_arena::Arena;
fn main() {
let mut arena: Arena<u8> = Arena::new();
// Append elements to the arena
let handle1 = arena.append(5, 10); // Append 10 elements of value 5
let handle2 = arena.append(6, 10); // Append 10 elements of value 6
// Access elements using handles
assert_eq!(arena[handle1], 5);
assert_eq!(arena[handle2], 6);
// Free a span
arena.free(handle1);
// Reuse freed span
let handle3 = arena.append(7, 10); // This should reuse the space freed by handle1
assert_eq!(handle1, handle3);
assert_eq!(arena[handle3], 7);
}
Benchmarks and tests
To run tests, run cargo test
. To run benchmarks, run cargo bench
in the project directory. See benchmark results in target/criterion/report/index.html
.
Benchmark results on an Intel Xeon E5-2690 v3 with 2133 MHz DDR4 quad-channel RAM:
append 1 element time: [122.48 ns 125.71 ns 129.62 ns]
append 10 elements time: [126.89 ns 129.69 ns 133.18 ns]
append 100 elements time: [129.01 ns 129.65 ns 130.51 ns]
free 10 elements time: [185.96 ns 189.48 ns 193.88 ns]
free 100 elements time: [191.01 ns 191.40 ns 191.93 ns]
reuse span of 10 elements
time: [205.49 ns 210.46 ns 216.89 ns]
reuse span of 100 elements
time: [266.60 ns 274.03 ns 282.45 ns]
iterate 100 elements time: [85.580 ns 87.331 ns 89.547 ns]
iterate 1000 elements time: [696.59 ns 715.24 ns 736.26 ns]
iterate and mutate 100 elements
time: [67.295 ns 67.438 ns 67.636 ns]
iterate and mutate 1000 elements
time: [625.11 ns 639.24 ns 656.52 ns]
fetch_if found in 100 elements
time: [66.565 ns 68.174 ns 70.049 ns]
fetch_if not found in 1000 elements
time: [582.72 ns 591.28 ns 603.65 ns]
fetch_or_append found in 100 elements
time: [2.5913 ns 2.5918 ns 2.5922 ns]
fetch_or_append not found in 1000 elements
time: [585.43 ns 591.74 ns 600.30 ns]
retain_mut keep half of 100 elements
time: [325.25 ns 333.94 ns 345.95 ns]
mixed workload with 100 elements
time: [433.85 ns 439.76 ns 452.24 ns]
(light travels about 30 meters in 100 nanoseconds)
License
The Unlicense (public domain)