Fast O(1) offset allocator with minimal fragmentation
Fast O(1) offset allocator with minimal fragmentation
Fast hard realtime O(1) offset allocator with minimal fragmentation.
Uses 256 bins with 8 bit floating point distribution (3 bit mantissa + 5 bit exponent) and a two level bitfield to find the next available bin using 2x LZCNT instructions to make all operations O(1). Bin sizes following the floating point distribution ensures hard bounds for memory overhead percentage regarless of size class. Pow2 bins would waste up to +100% memory (+50% on average). Our float bins waste up to +12.5% (+6.25% on average).
The allocation metadata is stored in a separate data structure, making this allocator suitable for sub-allocating any resources, such as GPU heaps, buffers and arrays. Returns an offset to the first element of the allocated contiguous range.
Bin size table:
…CMakeLists.txt exists for cmake folder include. Alternatively, just copy the OffsetAllocator.cpp and OffsetAllocator.hpp in your project. No other files are needed.
…This allocator is similar to the two-level segregated fit (TLSF) algorithm.
Comparison paper shows that TLSF algorithm provides best in class performance and fragmentation: https://www.researchgate.net/profile/Alfons-Crespo/publication/234785757_A_comparison_of_memory_allocators_for_real-time_applications/links/5421d8550cf2a39f4af765f4/A-comparison-of-memory-allocators-for-real-time-applications.pdf
Early one weekend prototype. Unit tests are green, but coverage is still not 100%. Use at your own risk!
MIT license (see file: LICENSE)
No open issues yet, or sync has not completed.