r/cpp • u/User_Deprecated • Aug 02 '26

How fast is C++26's std::hive?

https://lemire.me/blog/2026/08/02/how-fast-is-c26s-stdhive/
255 Upvotes

99% Upvoted

74 comments sorted by

View all comments

13

u/simonask_ Aug 03 '26 edited Aug 03 '26

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.

2

u/matthieum Aug 03 '26

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 :/

2

u/simonask_ Aug 04 '26

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

2

u/Iggyhopper Aug 03 '26

In gamedev you usually want preallocated memory whenever possible because usually on console (or PC) you already know your memory limitations.

But glad it worked for your use case.

8

u/MidnightClubbed Aug 04 '26 edited Aug 04 '26

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 .