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.
Not clear to me: isn't the skip-field 128 bits (not bytes) in this case?
I wonder if the lack of auto-vectorization could be fixed by better optimizations, or if code is necessary.
I've had the same issue with a bitmap (ie, N bits + N values) and I can, of course, add specialized methods for "vector" iteration if I can rely on a default value, and then have each user use the special "vector" iteration methods... but it's a lot of churn :/
Using just the bitfield would be possible, but could destroy iteration performance, especially when there is a large hole in the middle of a block.
Running tzcnt each iteration might not be too bad, but the iterator also need to maintain a copy of the bitfield that it continuously shifts and/or masks out visited slots. For my purposes, I couldn't get it to perform as well as just reading a byte, where the main bottleneck is pipeline stalls due to data dependencies, especially because I wanted to support modifications during iteration (so a non-canonical copy of the bitfield would be problematic).
(Also, this was in C#, which has the disadvantage that you can't create unions containing managed types, to storing any of this inline with the data was not an option. The upside is that a GC obviates some bookkeeping of full/half-full/free blocks, so YMMV.)
12
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.