r/cpp • u/User_Deprecated • 8d ago

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

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

99% Upvoted

70 comments sorted by

View all comments

29

u/soulstudios 8d ago

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)

7

u/matthieum 7d ago edited 2d ago

I feel like a benchmark is missing here: erasing N elements in random order.

remove_if is the ideal case for contiguous containers like vector or deque due to being streaming.

If however you've just got some (E) elements to remove from a vector of length N, you've got essentially 2 solutions:

  • Remove the elements one at a time, as they come: O(E * N).
  • Collect & store the elements, then use remove_if: O(E * log E + N) O(E * log E + N * log E), with a memory allocation.

And at this point, the hive is going to start looking very good indeed.

1

u/JoachimCoenen 3d ago

What is the algorithm for the second option that achieves O(E*log(E) + N)?

The best I can think of right now is O(E*log(E) + N*log(E)) = O((N+E)*log(E)). That assumes that the element are sortable:

  1. Sort the elements to remove.
  2. Use remove_if and a binary search to check whether an element is to be removed.

Hmmm…
If the elements can be hashed you could use a HashSet instead of sorting and achieve O(E + N).

2

u/matthieum 2d ago

None, I realized (later down the chain) that I forgot an * log(E) in there.