Blink-alloc is extremely fast allocator based on the common idea of allocating linearly zipping a cursor through memory chunk and reset everything at once by setting cursor back to start.
With Rust's borrow checker this idea can be implemented safely, preventing resets to occur while allocated memory is in use.
The blink-allocator acts as an adaptor to some lower-level allocator. Grabs chunks of memory from underlying allocator and serves allocations from them. When chunk is exhausted blink-allocator requests new larger chunk of memory from lower-level allocator.
On reset all but last chunks are returned back to underlying allocator. The goal is to allocate a single chunk large enough to serve all allocations between resets, so that lower-level allocator is not touched after initial warm-up phase. Making allocations and resets almost free.
The way blink-allocators are implemented offers cheap allocation shrinks when
new layout fits into currently allocated memory block.
Which is certainly the case for things like Vec::shrink_to and Vec::shrink_to_fit.
When done on the tip of allocation it also frees the memory for reuse.
Additionally fast allocation grows is possible when done on the tip of allocation.
Which is easy to control when using thread-local version.
This opens a way for blazing fast Vec::push call even at full Vec capacity.
The simple implementation uses unsynchronized interior mutability and thus only works in single-thread scenario. It can be send to another thread but not shared.
Maintaining an instance per thread is one way to tackle this problem. Yet not always possible or desireable.
This crate provides additional implementation for multi-threaded scenario with slight performance penalty. To negate it, a local copy of single-threaded blink-allocator can be created to take memory from shared multi-threaded blink-allocator, allowing reusing memory across threads while keeping blazing fast allocations of single-threaded version. It works best for fork-join type of parallelism since it requires a point where the multi-threaded blink-allocator is not shared to reset it.
For task-based parallelism a cache of blink-allocators can be constructed. Task may borrow single-threaded blink-allocator and return it when its done. This will keep cache full of pre-warmed blink-allocators.
BlinkAlloc is a single-threaded version of the allocator.
It uses unsynchronized interior mutability for fastest performance.
BlinkAlloc can be sent to other threads but not shared.
For multi-threading an instance of BlinkAlloc per thread/task
can be created.
Though it may be not possible or practical in some ways, so consider
alternatives below.
SyncBlinkAlloc works in multithreaded environment and shares memory
from one chunk between threads. Reduces overall memory usage,
skips warm-up phase for new threads and tasks.
SyncBlinkAlloc can spawn LocalBlinkAlloc instances
that work similarly to BlinkAlloc.
LocalBlinkAlloc instances fetch memory chunks from shared SyncBlinkAlloc.
SyncBlinkAlloc still requires exclusive access to reset.
Works best for fork-join style of parallelism, where reset happens
after joining all threads.
For task/based parallelism this crate provides BlinkAllocCache type
which is a cache of BlinkAlloc instances.
Tasks may fetch blink allocator from cache,
use it and then return it back to cache.
Cache keeps BlinkAlloc instances warmed up.
Allocators implement Allocator interface from alloc crate
or a copy of it when feature "nightly" is not enabled.
"nightly" requires Rust feature allocator_api
and works only on nightly.
Once Allocator trait is stable the feature will do nothing and
removed in next major release.
BlinkAlloc and friends implement Allocator from allocator_api
unstable feature. It is only available when "nightly" feature is enabled
for this crate. Otherwise Allocator is not core::alloc::Allocator
but a duplicate defined in the crate.
With allocator_api it is possible to use BlinkAlloc and others
for allocator type in collection types that support one.
Currently Vec, VecDeque, BTreeMap and BTreeSet can use
user-provided allocator.
Also hashbrown::HashMap and hashbrown::HashSet support it with
"nightly" feature.
However on stable it cannot be used right now.
It is still possible to use blink-allocators in safe manner -
meet Blink allocator adaptor.
Put anything into memory allocated by Blink.
Values, iterators, closures to construct a value,
slices and strings.
It works with everything*.
Uses underlying blink-allocator and returns mutable reference
to values placed into allocated memory.
By default it drops placed values on reset.
* Ask for API extension if doesn't work for your use case.
Usage of Blink allocator adaptor.
Initialize and start putting values there.
use blink_alloc::Blink;
#[cfg(feature = "alloc")]
fn main() {
// `Blink::new` uses `BlinkAlloc<Global>`
let mut blink = Blink::new();
// Allocates memory and moves value there.
// Returns mutable reference to it.
let x = blink.put(42);
assert_eq!(*x, 42);
*x = 11;
// Copies string slice to the blink-allocated memory.
let string = blink.copy_str("Hello world");
// Mutable reference allows string mutation
string.make_ascii_lowercase();
assert_eq!(string, "hello world");
// Consumes iterator and returns all values from it in slice.
// Works fine on problematic iterators with terrible size hint.
let slice = blink.emplace().from_iter((0..10).filter(|x| x % 3 != 0));
assert_eq!(&*slice, &[1, 2, 4, 5, 7, 8]);
blink.reset();
}
#[cfg(not(feature = "alloc"))] fn main() {}#![cfg_attr(feature = "nightly", feature(allocator_api))]
use blink_alloc::BlinkAlloc;
#[cfg(feature = "alloc")]
fn main() {
use allocator_api2::vec::Vec;
let mut blink = BlinkAlloc::new();
let mut vec = Vec::new_in(&blink);
vec.extend((1..10).map(|x| x * 3 - 2));
drop(vec);
blink.reset();
}
#[cfg(not(feature = "alloc"))] fn main() {}This crate supports no_std environment.
"alloc" feature is enabled by default and adds
dependency on alloc crate.
Licensed under either of
- Apache License, Version 2.0, (license/APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (license/MIT or http://opensource.org/licenses/MIT)
at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.