I wrote almost the exact same thing after seeing Sebastian Aaltonen's original offset allocator repo which inspired me to write my own clone in Rust.<p>It's possible to further improve the fragmentation characteristics if the maximum size of the memory to be allocated is known ahead of time. The original used a 5.3 "floating point" scheme for the free bins, but given the maximum size you can opt for 4.4 or 6.2 or whatever can cover the whole region, giving more dense (or sparse) allocation granularity as needed.<p>This same idea can also be extended to allocating texture atlas regions when the regions have power of two size. 256 bins can cover all possible texture sizes that GPUs can handle, so you can get hard O(1) texture packing.<p>I'm also curious about making something like this work as a general purpose allocator (as alluded to by the README). For that it would be necessary to make a reverse lookup from pointer address to allocation handle, which would require something like a red-black tree covering the address space, which would no longer be 0(1). If anyone has ideas on this front, I would be happy to hear them.<p>This algorithm is so clever and kind of a game changer. Allocating and freeing are fast real time operations (only dozens of CPU cycles and a few memory writes). It kind of makes "bump allocators" obsolete because this allocator is almost as fast but supports trimming and freeing allocations as well. This algorithm requires more memory but the amount is quite low.
Author here. Didn't expect this to make HN :)<p>I don't deserve any credit for this; @SebAaltonen did all the work to write the C++ version. I just did a line-by-line translation.
What's the difference between this and a slab allocator? Is it just that the bin size distribution wastes less memory (assuming the slab allocator used pow2 bin sizes)?
I have a best-fit allocator for this problem (managing GPU resources).
It has higher CPU overhead due to using a std::map, but should waste less space due to not using fixed bucket sizes.<p><a href="https://github.com/glaretechnologies/glare-core/blob/master/utils/BestFitAllocator.cpp">https://github.com/glaretechnologies/glare-core/blob/master/...</a>
<a href="https://github.com/glaretechnologies/glare-core/blob/master/utils/BestFitAllocator.h">https://github.com/glaretechnologies/glare-core/blob/master/...</a>
> Please note that offset-allocator isn't a Rust allocator conforming to the GlobalAlloc trait<p>Aw. Why not?<p>> find the next available bin using 2x LZCNT instructions to make all operations O(1)<p>Isn't that sort of implementation defined? The LZCNT operation itself is a loop over all bits -- the fact that the number of bits is constant doesn't make this O(1), it just makes it O(n) where n := 64. But if it was 16 or 32 bit, it may be faster, which means its not O(1), or rather, big o notation really breaks down here.
Why is this hard realtime in the face of arbitrary allocations and deallocations? These dots aren't connected anywhere within two links distance from the given URL.