MIN_OFFSET strategy is very slow

[bazhenovc]

Hi,

We were using the MIN_OFFSET strategy for allocating persistent GPU objects and noticed that it's approximately 120x slower than the default mode in release builds, I was wondering if there's any way to improve it?

Context: we have a GPU driven rendering system that needs to handle millions of small mesh instances that can be constantly loaded and unloaded, these instances are "handles" allocated out of a global buffer. We use a bitmask to track what is allocated and needs processing, the compute shader is then dispatched over the bitmask (64 threads, each thread checks 1 bit).

MIN_TIME is very fast, but it produces a ton of empty pages and causes very low GPU utilization at times, so it both requires some kind of indirection and extra complexity to reduce the memory usage, MIN_OFFSET is much easier in that regard.

For the time being I rolled out an ad-hoc "handle allocator" with a 2 level bitmask and a simple acceleration structure to circumvent the issue, but I'd rather not maintain it myself and rely on D3DMA support.

We still use MIN_TIME for all other GPU memory allocations, but would really benefit from MIN_OFFSET being faster.

Benchmark code: https://gist.github.com/bazhenovc/4b527b1912288184ca7f35c0aefb259a
My implementation: https://github.com/BobbyAnguelov/Esoterica/blob/main/Code/Base/Render/HandleAllocator.h
More docs / ramblings: https://github.com/BobbyAnguelov/Esoterica/blob/main/Docs/Rendering/HandleAllocator.md

Thanks a lot for the amazing library!

Debug results

	HandleAllocator	D3D12MA MIN_OFFSET	D3D12MA MIN_TIME
Small allocs	1.07 ms	12.70 ms	0.30 ms
Large allocs	1.82 ms	5.30 ms	0.15 ms
Total	2.88 ms	17.99 ms	0.46 ms

Release results

	HandleAllocator	D3D12MA MIN_OFFSET	D3D12MA MIN_TIME
Small allocs	0.41 ms	7.41 ms	0.06 ms
Large allocs	0.61 ms	3.76 ms	0.03 ms
Total	1.01 ms	11.16 ms	0.09 ms

[sawickiap]

Thank you for reporting this issue.

Note that ALLOCATION_FLAG_STRATEGY_MIN_OFFSET is documented as: This is not the most efficient strategy but achieves highly packed data. Used internally by defragmentation, not recommended in typical usage.

That said, I will look into possibilities to optimize its performance. In the meantime, let's explore other possibilities.

Did you try allocating without any ALLOCATION_FLAG_STRATEGY_ flag (using default strategy)? This is the recommended default. How does the performance and allocation quality compare to MIN_OFFSET and MIN_TIME in your app?

Do you really need a full allocator algorithm for this kind of objects? Are your GPU objects of various sizes, allocated and deallocated in random order? If they are all the same size or if they are allocated in certain order like FIFO, LIFO, or destroying all at once, a custom pool with POOL_FLAG_ALGORITHM_LINEAR or a simple custom allocator could be better.

[bazhenovc]

Did you try allocating without any ALLOCATION_FLAG_STRATEGY_ flag (using default strategy)? This is the recommended default. How does the performance and allocation quality compare to MIN_OFFSET and MIN_TIME in your app?

Just added this to the benchmark and tested it, performance seems largely identical to MIN_TIME strategy (with some fluctuations). Offset quality is the same as MIN_TIME.

Do you really need a full allocator algorithm for this kind of objects?

Well, probably not 😅 But it seems like a natural fit for this use-case, I'm open to considering alternatives.

Are your GPU objects of various sizes, allocated and deallocated in random order?

So the objects themselves are the same size (64 bytes struct), but I do need to allocate contiguous ranges of them. This allocation pattern is exploited in multiple places across the codebase - most of the time I'm passing offset+count to various subsystems and it simplifies the code a lot.

The allocations generally fall into 2 categories:

1- we have regular "fat" game objects that are complex individual meshes with different behaviour like attachments, skinning etc - this category has a lot of small allocations. Our test setups have 8k-15k "game objects" in the level that each allocate 2-10 "mesh instances" individually.

2 - we have a "PCG" system that is used for things like scattering and kitbashing that don't require complex game logic attached. These tend to be a few "game objects" (well under 1K), that allocate upwards to 200k instances each.

Currently both are served by the same underlying system and I'm pretty happy with how it works. There's some additional stuff under the hood like making sure these ranges of instances have reasonably cache coherent memory access, batching, etc, and that stuff also relies on the contiguous range allocation pattern.

If they are all the same size or if they are allocated in certain order like FIFO, LIFO

Allocation and deallocation pattern is completely random and not predictable, object streaming is not deterministic or easily predictable and this code also runs in the level editor context where the user should be able to do whatever.

custom pool with POOL_FLAG_ALGORITHM_LINEAR

The objects are persistent in the GPU memory, I don't think a linear wrap around allocator would work at all. We are trying to avoid touching anything that isn't actively updating or being streamed in/out.

simple custom allocator could be better

Well this is kinda what I ended up doing 🤷 It's a very ad-hoc system for the specific workloads that we have right now, I'm not very happy with it because of how specialized it is.

[sawickiap]

You can also try using VMA custom pools separate for your small and large allocations, or some other distinct kinds of objects you have in your code and see if that helps.

[bazhenovc]

You can also try using VMA custom pools separate for your small and large allocations, or some other distinct kinds of objects you have in your code and see if that helps.

Unfortunately no, I want to keep one global buffer with everything for more simplicity.

That said, I think you're right that the custom allocator is likely a better solution here, I thought about it since yesterday and I now I agree with you on it. Thank you for your advice, much appreciated!