OffsetAllocator

> Malloc and memory allocation methods are at least 10k+ lines of code for instance. Only the really big ones, e.g. here is Emscripten's allocator that focuses on small binary size and is implemented in about 1.5 kloc (ignoring comments and whitespace it's actually under 1 kloc), and that allocator is perfectly fine for most use cases (especially C code bases which typically don't have a high allocation frequency): https://github.com/emscripten-core/emscripten/blob/main/syst... ...and Seb Aaltonen's offset allocator (used for allocating GPU buffers in his Vulkan API wrapper) has under 500 lines of code: https://github.com/sebbbi/OffsetAllocator/blob/main/offsetAl... Right tool for the job etc... big general-purpose allocators like jemalloc or mimalloc are usually a bandaid to somewhat salvage a failed memory management strategy.

Here's another interesting O(1) memory allocator but with arbitrary sized allocations and low fragmentation. Negative side is relatively high memory overhead (a few dozen bytes per allocation). This kind of allocator is often used to suballocate GPU memory in game and graphics applications. I'm using a variant of this algorithm with added support for shrinkable and aligned allocations and flexible bin sizing. You can also extend this idea to two dimensions to create texture atlases, which is possible in O(1) for power of two sized allocations. Original: https://github.com/sebbbi/OffsetAllocator Rust port: https://crates.io/crates/offset-allocator

There are definitely a lot of similarities. I spent some time reviewing allocator designs to see if some ideas might carry over. One problem I found is that a lot of allocators benefit from being able to track freelists based on some minimum sizes needed for allocations (e.g., https://github.com/sebbbi/OffsetAllocator). This problem is a bit different in that I want to know the first available block even though it might be much bigger than I need. Having multiple lists might still be useful though, but it's not as effective as how they're used in allocators - you'd usually need to search multiple freelists to know the first available instead of one.

https://github.com/sebbbi/OffsetAllocator which has links to a pertinent paper at the end of that page.

At least one mention of it here https://github.com/bevyengine/bevy/issues/12590 > Use one set of large mesh buffers per vertex attribute layout > Problem: Index/vertex buffers have to be re-bound when the mesh changes. This adds overhead when encoding draws and when drawing. It also prevents some optimisations like being able to draw all objects for shadow mapping for a light in one draw. > Solution(s): [...] Use an appropriate allocator like a port of Sebastian Aaltonen's offset allocator [https://github.com/sebbbi/OffsetAllocator] to manage allocation Where the "port of Sebastian Aaltonen's offset allocator" is what got linked in this HN submission.