good_memory_allocator
This is a linked list allocator, inspired by the dlmalloc algorithm, to be used in no_std environments such as operating system kernels.
The overhead for each allocation is a single usize.
The implementation prioritizes runtime efficiency over memory efficiency, but also provides very good memory utilization.
The allocator is heavily tested with test cases covering almost all code paths; fuzzing is used to cover the rest.
Create a static allocator:
```rust use goodmemoryallocator::SpinLockedAllocator;
static ALLOCATOR: SpinLockedAllocator = SpinLockedAllocator::empty(); ```
Before using this allocator, you need to initialize it:
rust
pub fn init_heap() {
unsafe {
ALLOCATOR.init(heap_start, heap_size);
}
}
spin (default): Provide a SpinLockedAllocator type that implements the GlobalAlloc trait by using a spinlock.allocator: Provides an implementation of the unstable Allocator trait for the SpinLockedAllocator type.In most cases, allocation is O(1), mostly for relatively small allocations with relatively small alignment.
Deallocation is always O(1).
Reallocaiton uses a custom algorithm which tries to prevent copying of memory as much as possible, by reallocating in place.
The overall performance of the allocator is superb, and it performs better than all other alternative allocators which we could find on crates.io.
We benchmarked galloc using multiple benchmarks against 2 other crates that we found on crates.io, that seem to provide similar functionality: simple-chunk-allocator and linked-list-allocator.
In each benchmark, each allocator is given a certain duration and must perform as many operations as it can in the given duration.
The first benchmark that we used is called random_actions.
In this benchmark each allocator tries to perform as many allocations, deallocations and reallocations as it can in the given duration.
The size and alignment of the allocations and reallocations is random.
In each iteration, the benchmark randomly chooses between allocation, deallcation and reallocation.
In the top left, below the legend, you can see the percentage difference of the number of actions between galloc and each of the other allocators.
The percentage difference is calculated using the following formula: a / b * 100, where a is galloc's score, and b is the other allocator's score.
You can see that galloc outperforms both other allocators by almost an order of magnitude.
The second benchmark that we used is called heap_exhaustion.
In this benchmark each allocator performs as many allocations as it can in the given duration.
The size and alignment of the allocations is random.
Once an allocation request fails, it means that the heap was exhausted, and the allocator's score is punished by making it sleep for a certain duration.
Thus, this benchmark measures how well the allocator utilizes its memory, since all allocators are given a heap of the same size.
Here, too, galloc outperforms the 2 other allocators.
The simple-chunk-allocator crate provides a benchmark of its own.
Here is an explanation of the benchmark from simple-chunk-allocator's readme:
The benchmark performs random allocations of different sizes and alignments and also deallocates some of the older allocations. Over time, the heap becomes full, which is why the number of successful allocations has a higher delta to the attempted allocations.
We ran these benchmarks on the 3 allocators including galloc, and the results were as follows:
``` RESULTS OF BENCHMARK: Chunk Allocator 51244 allocations, 15404 successful_allocations, 35840 deallocations median= 1210 ticks, average= 1232 ticks, min= 218 ticks, max=144410 ticks
RESULTS OF BENCHMARK: Linked List Allocator 34937 allocations, 10829 successful_allocations, 24108 deallocations median= 28778 ticks, average= 41553 ticks, min= 78 ticks, max=1165606 ticks
RESULTS OF BENCHMARK: Galloc 51694 allocations, 15651 successful_allocations, 36043 deallocations median= 176 ticks, average= 654 ticks, min= 90 ticks, max=989542 ticks ```
``` RESULTS OF BENCHMARK: Chunk Allocator 79818 allocations, 23909 successful_allocations, 55909 deallocations median= 1294 ticks, average=320782 ticks, min= 174 ticks, max=13773388 ticks
RESULTS OF BENCHMARK: Linked List Allocator 113181 allocations, 30521 successful_allocations, 79611 deallocations median= 91688 ticks, average=120273 ticks, min= 80 ticks, max=1831252 ticks
RESULTS OF BENCHMARK: Galloc 147720 allocations, 32754 successful_allocations, 103313 deallocations median= 214 ticks, average= 39177 ticks, min= 88 ticks, max=2228776 ticks ```
As you can see, galloc outperformed both of them in both test cases. This is especially noticable in the 10 seconds test.
linked-list-allocatorThe linked-list-allocator crate currently has a bug where it loses heap memory over time, eventually reaching heap exhaustion even after freeing all memory.
For this reason, we do not consider linked-list-allocator production ready.
galloc on the other hand is heavily tested and, as far as we are aware, has no such bugs.