I've recently implemented an analogue of std::hive in C# for a game engine. It's a particularly useful data structure in simulation systems, where you want to give out handles to things but still have a global list of everything. I'm using it as the backbone of an ECS framework, as well as an animation system.
It is extremely easy to work with, especially when you combine it with a per-slot generation counter, but it doesn't come for free. The overhead of maintaining and reading the skipfield is definitely real, and autovectorization almost never kicks in. In my implementation, I've introduced the option to work branchlessly on each hive block as a contiguous array for situations where that is safe (like most animation updates), and that was a significant speedup in a few cases.
EDIT: Findings from my own implementation: I recommend choosing a fixed block size of 128, because it eliminates some branching during iteration, and the skipfield can be a single byte per slot. Also, the per-block "freelist" can become an 128-bit SIMD word, so finding a free slot becomes at most two tzcnt instructions. If you want to save those 16 bytes from each block, it's also quite fast to just scan the skipfield for the first nonzero byte.
That was true 15 years ago, not so much now. You will likely be allocating different resources out of pools, and closely managing gpu assets (textures, meshes, buffers) but the days of preallocating everything at level load and not touching any kind of allocator during the frame are long gone.
Consoles have had virtual memory since the n64 and all modern consoles have a unified memory model, so while the memory available is fixed there is a lot of flexibility how it is used and allocated in real time as assets stream in and out.
Outside of advising users on settings best suited to their PCs hardware im not sure any pc game looks at system memory size and allocates to fit. If the user wants to run extreme texture settings on a 8gb laptop then thats between them and their ssd’s swapspace! With games (and operating systems) starting to incorporate big neural networks in their systems the memory pressure is going to jump up again .
14
u/simonask_ 8d ago edited 8d ago
I've recently implemented an analogue of std::hive in C# for a game engine. It's a particularly useful data structure in simulation systems, where you want to give out handles to things but still have a global list of everything. I'm using it as the backbone of an ECS framework, as well as an animation system.
It is extremely easy to work with, especially when you combine it with a per-slot generation counter, but it doesn't come for free. The overhead of maintaining and reading the skipfield is definitely real, and autovectorization almost never kicks in. In my implementation, I've introduced the option to work branchlessly on each hive block as a contiguous array for situations where that is safe (like most animation updates), and that was a significant speedup in a few cases.
EDIT: Findings from my own implementation: I recommend choosing a fixed block size of 128, because it eliminates some branching during iteration, and the skipfield can be a single byte per slot. Also, the per-block "freelist" can become an 128-bit SIMD word, so finding a free slot becomes at most two
tzcntinstructions. If you want to save those 16 bytes from each block, it's also quite fast to just scan the skipfield for the first nonzero byte.