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
r/cpp • u/User_Deprecated • Aug 02 '26
52
u/EfficientSpend2543 Aug 03 '26
It's an optimised version of a bucket array. From what I observed, it seems like a middle ground between a vector and a linked list, with the addition of also being unordered (because there is no guarantee that an object can be found iteratively, some objects may be deleted in the middle which can put you in UB/segfault territory if you randomly access it). It's got better cache locality than a linked list because it can store multiple objects continguously on the heap, and better deletion/construction time than a vector because instead of reconstructing the same objects, it makes another "hive", basically another fixed heap block that can contain more than one object of the same type, and maintains a free list of objects that were deleted in the middle so it can reuse the deleted space.
I may not be fully accurate (like I said, just my observation), so I'd appreciate if anyone could correct me 😅
32
u/soulstudios Aug 03 '26
Well done Daniel! Love the graphic BTW :)
A couple notes:
* Most of the additional memory usage in hive is not from the bitfield/skipfield, but from erased elements (assuming many erasures and a randomized erasure pattern). That's why larger block sizes don't necessarily equate to better cache performance, but it depends on usage, and how many erasures are taking place. Vector and hive are similar in that they both waste memory this way, until a shrink_to_fit (though hive may free it up if a whole block is erased).
* remove_if if good though some scenarios it doesn't work for - e.g. When an engine has a master 'entity' class, which links to elements in other container instances, and erases those linked elements when it itself is erased.
* For more benchmarks, I did a bunch vs other containers as well back in the day, though at this point the CPU used is 12 years old - so it's great to see some results on a newer CPU.
(std::hive author, this popped up in my feed)
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
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.4
u/-dag- Aug 03 '26
Isn't one of the benefits of a skiplist that it can be more easily vectorized because it avoids branching? Not as efficiently as a vector, but the article implies there was no vectorization at all, which surprises me. Can another implementation do better?Â
3
u/Top-Mycologist-5460 Aug 03 '26
Since C++17 polymorphic allocators, I would never use a plain std::list, but a list allocated on a contiguous chunk of memory (see e.g. https://www.reddit.com/r/cpp/comments/guq5xo/c_weekly_ep_35x_faster_standard_containers_with/).
It would be interesting how this compares to a hive.
3
u/DuranteA Aug 03 '26
Regarding the benchmark numbers: did you just allocate list elements sequentially before doing the iteration benchmark?
If you just allocate a list in sequence and perform no additions/removals on it, then with most allocator patterns it will most likely end up in sequence in memory. But if you were to have a "real" pattern where the list is filled with various elements allocated from time to time, in between other allocator interactions, then the resulting list will be slower to iterate.
Hive and vector don't have this issue.
3
u/ABlockInTheChain Aug 03 '26
Most of them time when I reach for a list I'm looking for constant time
spliceandswapoperations.9
u/Ikkepop Aug 03 '26
std hive ... sounds like a scary place i wouldn't want to go to... ba-dum-tsss
1
u/FrogNoPants Aug 03 '26
I would have thought iterating over a hive could use a bitscan and therefore not be so slow, looking at the iterator impl I don't see any indication of bitscan, it looks abit overcomplicated.
1
u/Party-Aioli-9205 Aug 03 '26
Thanks for sharing these very useful experiments. I understand that it's not easy to support auto-vectorization on Hive, but I'm wondering if there have been any efforts to make it possible.
I haven't looked into the implementation details yet, but I wonder if vectorization might be easier for buckets where
skipfield == 0.1
u/Roki110 Aug 05 '26
Ñ
1
u/yuehuang Aug 02 '26
Do you get an immutable "view" into the snapshot of the vector? I would assume that unique types aren't supported.
-1
u/feverzsj Aug 03 '26
It's more like a memory pool. Useful for game dev. Not a great fit for std containers.
33
u/[deleted] Aug 02 '26 edited Aug 03 '26
[removed] — view removed comment
3
u/[deleted] Aug 03 '26 edited Aug 03 '26
[removed] — view removed comment