8 ms·

Fast, simple, hard real time allocator for Rust

207 points by practicalrs 2y ago

Ono-Sendai 2y ago
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. https://github.com/glaretechnologies/glare-core/blob/master/utils/BestFitAllocator.cpp https://github.com/glaretechnologies/glare-core/blob/master/... https://github.com/glaretechnologies/glare-core/blob/master/utils/BestFitAllocator.h https://github.com/glaretechnologies/glare-core/blob/master/...
pcwalton 2y ago
Author here. Didn't expect this to make HN :) 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.
hinkley 2y ago
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.
deleted 2y ago
[deleted]
lionkor 2y ago
> Please note that offset-allocator isn't a Rust allocator conforming to the GlobalAlloc trait Aw. Why not? > find the next available bin using 2x LZCNT instructions to make all operations O(1) 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.
- exDM69 2y ago
  > Aw. Why not? Because the global allocator API is defined as free(pointer address) and this used free(buffer handle). It would require a reverse lookup structure from address to buffer handle, e.g. red-black tree. Maintaining it would no longer be O(1). > the fact that the number of bits is constant doesn't make this O(1), it just makes it O(n) where n := 64 O(n) when n is constant is equal to O(1). But lzcnt uses a fixed number of clock cycles so it's not really O(n) either.
  - orlp 2y ago
    > It would require a reverse lookup structure from address to buffer handle, e.g. red-black tree. Maintaining it would no longer be O(1). Well, another solution is enlarging each allocation by 8 bytes and storing the buffer handle in front of the returned allocation. So `free(ptr)` would get the handle as `*((ptr as *const u64) - 1)`.
    - exDM69 2y ago
      That works but... This kind of allocators are usually used for suballocating GPU buffers, so hiding a few bytes of metadata "in-band" can mess up your alignment requirements and not all kinds of GPU memory are even accessible by CPU. Due to false sharing cache problems you would probably want a full cache line (64 bytes) to store the metadata. For a CPU-only memory allocator your idea could work quite well. It can also be implemented on top of this code without any modifications.
  - pbalcer 2y ago
    > It would require a reverse lookup structure from address to buffer handle, e.g. red-black tree. Maintaining it would no longer be O(1). Not necessarily. If you are able to map a block of normal memory in a known location relative to the GPU memory that you are managing with an "offset allocator", it should be possible to directly calculate the metadata location for each "offset". This is how most allocators find arenas/buckets (whatever you want to call them) for an allocation by a pointer. Something like this: +-------------------------+ 0x000000 (start of managed memory) | Metadata | | | | | | ... | +-------------------------+ 0x001000 | Padding ... | +-------------------------+ 0x010000 | GPU Memory Block | | | | | | | ~2MB block | | | | | | +-------------------------+ 0x210000 With this layout, to get to a metadata for an allocation, all you need to do is to align down the allocation pointer and calculate the appropriate location in the metadata page. This obviously won't work in all scenarios, but it's a simple and practical way around a map lookup.
exDM69 2y ago
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. 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. 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. 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. 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.
- pcwalton 2y ago
  > I'm also curious about making something like this work as a general purpose allocator (as alluded to by the README). Besides the reverse mapping, you'd also have to get rid of the Vec use in the allocator, but that's fairly straightforward. Additionally, you'd need some sort of logic about requesting slabs of memory from the OS (and returning them when free), which is some extra work.
- scott_s 2y ago
  > 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. A radix tree can solve this: https://en.wikipedia.org/wiki/Radix_tree https://en.wikipedia.org/wiki/Radix_tree I used one way, way back to do exactly the same thing: upon a free, I needed to look up all of the metadata for an address. For a 32-bit address space, you can just allocate a giant array up front, and use the address as an index. For a 64-bit address space, it's obviously way too big to statically allocate it up front. A radix tree neatly solves the problem. An arbitrarily sized radix tree is not constant lookup, but for reasons I honestly cannot remember, for a 64-bit address space, it's guaranteed to only be 3 levels deep. See my implementation, which (I believe) I borrowed from tcmalloc: https://github.com/scotts/streamflow/blob/master/streamflow.c#L117 https://github.com/scotts/streamflow/blob/master/streamflow....
joshsyn 2y ago
How is this exactly going to be used in bevy?
- pcwalton 2y ago
  The goal is to start storing multiple meshes in the same vertex buffer/index buffer. (I already have a decent chunk of this code written in a branch.) This reduces binding overhead, but moreover it allows us to start using multidraw indirect where supported, which should reduce drawcall counts dramatically. I measured a 97% drawcall count reduction for the opaque pass on the Bistro test scene, for example. The benefits are even higher for shadow maps, because they use a single shader and so the drawcall count should drop to the single digits in most cases. I've said it before, but if drawcall count is a problem in your game, you should complain to the engine vendor. On modern GPUs, there's no reason people should be manually optimizing for drawcall count in 2024. Game engines have the tools to make it a non-issue; they just need to use them.
- CaptainOfCoit 2y ago
  At least one mention of it here https://github.com/bevyengine/bevy/issues/12590 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 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.
widdershins 2y ago
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)?
- hinkley 2y ago
  Slab allocators don’t provide real time guarantees. That is arena allocators. The distinction may seem trivial but the requirements are distinct. In tiny systems all allocations of one type may come from a single operation, but in larger systems what fits in a slab will come from distinct concerns with different priorities. You want a different arena for those allocations.
  - widdershins 2y ago
    I'm confused. To me it seems that real time guarantees are a function of three things: - Is it constant time in algorithmic complexity? - Is it single threaded (i.e. free from locks)? - Does it need to fetch memory from the system (not realtime safe)? There are slab allocators that can satisfy all of these, and are therefore realtime safe. So I'm still wondering what the difference is.
mgrithm 2y ago
whats a offset allocator?
- jjtheblunt 2y ago
  https://github.com/sebbbi/OffsetAllocator https://github.com/sebbbi/OffsetAllocator which has links to a pertinent paper at the end of that page.
  - hinkley 2y ago
    That doesn't explain anything. And the linked paper doesn't even contain the word 'offset'.
    - jjtheblunt 2y ago
      I mean you could presumably read the code. It looks like the general idea of TLSF is an array of second level arrays, where the second level arrays hold blocks of fixed size, and in TLSF those fixed sizes for the secondary arrays increase as powers of 2, and in this so called offset allocator the secondary level arrays use a more complex size statistically chosen. Allocation requests seemingly return an offset into a second level array. Kinda uncommented code, to your point, makes it not obvious.

207 points by practicalrs 2y ago

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. https://github.com/glaretechnologies/glare-core/blob/master/utils/BestFitAllocator.cpp https://github.com/glaretechnologies/glare-core/blob/master/... https://github.com/glaretechnologies/glare-core/blob/master/utils/BestFitAllocator.h https://github.com/glaretechnologies/glare-core/blob/master/...

pcwalton 2y ago

Author here. Didn't expect this to make HN :) 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.

hinkley 2y ago

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.

deleted 2y ago

[deleted]

lionkor 2y ago

> Please note that offset-allocator isn't a Rust allocator conforming to the GlobalAlloc trait Aw. Why not? > find the next available bin using 2x LZCNT instructions to make all operations O(1) 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.

exDM69 2y ago
> Aw. Why not? Because the global allocator API is defined as free(pointer address) and this used free(buffer handle). It would require a reverse lookup structure from address to buffer handle, e.g. red-black tree. Maintaining it would no longer be O(1). > the fact that the number of bits is constant doesn't make this O(1), it just makes it O(n) where n := 64 O(n) when n is constant is equal to O(1). But lzcnt uses a fixed number of clock cycles so it's not really O(n) either.
- orlp 2y ago
  > It would require a reverse lookup structure from address to buffer handle, e.g. red-black tree. Maintaining it would no longer be O(1). Well, another solution is enlarging each allocation by 8 bytes and storing the buffer handle in front of the returned allocation. So `free(ptr)` would get the handle as `*((ptr as *const u64) - 1)`.
  - exDM69 2y ago
    That works but... This kind of allocators are usually used for suballocating GPU buffers, so hiding a few bytes of metadata "in-band" can mess up your alignment requirements and not all kinds of GPU memory are even accessible by CPU. Due to false sharing cache problems you would probably want a full cache line (64 bytes) to store the metadata. For a CPU-only memory allocator your idea could work quite well. It can also be implemented on top of this code without any modifications.
- pbalcer 2y ago
  > It would require a reverse lookup structure from address to buffer handle, e.g. red-black tree. Maintaining it would no longer be O(1). Not necessarily. If you are able to map a block of normal memory in a known location relative to the GPU memory that you are managing with an "offset allocator", it should be possible to directly calculate the metadata location for each "offset". This is how most allocators find arenas/buckets (whatever you want to call them) for an allocation by a pointer. Something like this: +-------------------------+ 0x000000 (start of managed memory) | Metadata | | | | | | ... | +-------------------------+ 0x001000 | Padding ... | +-------------------------+ 0x010000 | GPU Memory Block | | | | | | | ~2MB block | | | | | | +-------------------------+ 0x210000 With this layout, to get to a metadata for an allocation, all you need to do is to align down the allocation pointer and calculate the appropriate location in the metadata page. This obviously won't work in all scenarios, but it's a simple and practical way around a map lookup.

exDM69 2y ago

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. 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. 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. 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. 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.

pcwalton 2y ago
> I'm also curious about making something like this work as a general purpose allocator (as alluded to by the README). Besides the reverse mapping, you'd also have to get rid of the Vec use in the allocator, but that's fairly straightforward. Additionally, you'd need some sort of logic about requesting slabs of memory from the OS (and returning them when free), which is some extra work.
scott_s 2y ago
> 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. A radix tree can solve this: https://en.wikipedia.org/wiki/Radix_tree https://en.wikipedia.org/wiki/Radix_tree I used one way, way back to do exactly the same thing: upon a free, I needed to look up all of the metadata for an address. For a 32-bit address space, you can just allocate a giant array up front, and use the address as an index. For a 64-bit address space, it's obviously way too big to statically allocate it up front. A radix tree neatly solves the problem. An arbitrarily sized radix tree is not constant lookup, but for reasons I honestly cannot remember, for a 64-bit address space, it's guaranteed to only be 3 levels deep. See my implementation, which (I believe) I borrowed from tcmalloc: https://github.com/scotts/streamflow/blob/master/streamflow.c#L117 https://github.com/scotts/streamflow/blob/master/streamflow....

joshsyn 2y ago

How is this exactly going to be used in bevy?

pcwalton 2y ago
The goal is to start storing multiple meshes in the same vertex buffer/index buffer. (I already have a decent chunk of this code written in a branch.) This reduces binding overhead, but moreover it allows us to start using multidraw indirect where supported, which should reduce drawcall counts dramatically. I measured a 97% drawcall count reduction for the opaque pass on the Bistro test scene, for example. The benefits are even higher for shadow maps, because they use a single shader and so the drawcall count should drop to the single digits in most cases. I've said it before, but if drawcall count is a problem in your game, you should complain to the engine vendor. On modern GPUs, there's no reason people should be manually optimizing for drawcall count in 2024. Game engines have the tools to make it a non-issue; they just need to use them.
CaptainOfCoit 2y ago
At least one mention of it here https://github.com/bevyengine/bevy/issues/12590 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 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.

widdershins 2y ago

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)?

hinkley 2y ago
Slab allocators don’t provide real time guarantees. That is arena allocators. The distinction may seem trivial but the requirements are distinct. In tiny systems all allocations of one type may come from a single operation, but in larger systems what fits in a slab will come from distinct concerns with different priorities. You want a different arena for those allocations.
- widdershins 2y ago
  I'm confused. To me it seems that real time guarantees are a function of three things: - Is it constant time in algorithmic complexity? - Is it single threaded (i.e. free from locks)? - Does it need to fetch memory from the system (not realtime safe)? There are slab allocators that can satisfy all of these, and are therefore realtime safe. So I'm still wondering what the difference is.

mgrithm 2y ago

whats a offset allocator?

jjtheblunt 2y ago
https://github.com/sebbbi/OffsetAllocator https://github.com/sebbbi/OffsetAllocator which has links to a pertinent paper at the end of that page.
- hinkley 2y ago
  That doesn't explain anything. And the linked paper doesn't even contain the word 'offset'.
  - jjtheblunt 2y ago
    I mean you could presumably read the code. It looks like the general idea of TLSF is an array of second level arrays, where the second level arrays hold blocks of fixed size, and in TLSF those fixed sizes for the secondary arrays increase as powers of 2, and in this so called offset allocator the secondary level arrays use a more complex size statistically chosen. Allocation requests seemingly return an offset into a second level array. Kinda uncommented code, to your point, makes it not obvious.