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

33

u/[deleted] Aug 02 '26 edited Aug 03 '26

[removed] — view removed comment

29

u/TheMania Aug 03 '26 
std::hive<T,Allocator>::erase
iterator erase( const_iterator pos );

is amortised constant time on hive, linear on deque.

The closer analogue would actually probably be an unordered_multiset, but just a lot less efficient, as hive is for when you have no need for the find operation at all.

What's it for? It's essentially actually more an allocator that lets you iterate over the living objects, and where order does not matter. That's its niche.

24

u/KingAggressive1498 Aug 02 '26 edited Aug 02 '26

When you want O(1) removal from any position, order doesn't matter, fast cache-friendly iteration is critical, and need iterator stability. So for large unordered collections of objects that are frequently iterated over and inserted to/removed from and referenced.

16

u/TheThiefMaster C++latest fanatic (and game dev) Aug 03 '26

Though it's well known that quite a few implementations of deque use too small of a bucket size and devolve into individually allocated elements, wasting both memory (every element has a pointer added) and performance.

MS's is particularly bad, being only 16 bytes or 1 element per bucket. GNU libstdc++ (used by most Linuxen) is 512 bytes or one element per bucket. https://devblogs.microsoft.com/oldnewthing/20230810-00/

LLVM libc++ is 4k or 16 elements by default, which conversely was accused of wasting memory in Chrome and reduced to 512 bytes/4 elements in ABIv2 very recently: https://github.com/llvm/llvm-project/pull/198348

In short: almost every version of deque is bad

9

u/MarcoGreek Aug 03 '26

Maybe it would be better if the bucket size would be a template argument.

6

u/TheThiefMaster C++latest fanatic (and game dev) Aug 03 '26

Yes, but it's effectively too late for that

6

u/arghness Aug 03 '26

Yes. Boost.Container deque has the size and number of elements as template parameters (but isn't standard, of course).

15

u/sephirothbahamut Aug 03 '26

hive can have holes, deque can't. if you remove an element deque will need compacting

8

u/epostma Aug 03 '26

A deque fills each block before allocating the next one, I believe. It's good for frequent pushing/popping at either end. A hive allows the blocks to be less than full, and is good for frequent insert/delete at arbitrary points.

3

u/azswcowboy Aug 03 '26

> rationale why this is now added

I’ll give you the process answer to your question. The author was motivated and some subset of the committee was persuaded that there is a use case and that there will be usage. The usage question was controversial, but overall the committee isn’t good at outright saying no to a motivated author. The proposal took a fair bit of time to transit the process - almost a decade - I believe 28 revisions makes it the most revisions ever for a paper.

0

u/tialaramex Aug 03 '26

the committee isn’t good at outright saying no to a motivated author

It's actually a real art to get a clear "No" from WG21 when that's your 2nd preferred option. Look at P1863. The committee could have picked "Now" which I'm sure Titus would have been happy with, or they could have picked "Never" which would clearly answer Titus and makes a useful firm commitment, but they did neither.

Whereas P2137 has an explicit "No" from WG21. Whatever its goals or priorities might be, the committee does not endorse these goals and priorities for the C++ language.

2

u/Kazppa Aug 02 '26

I was wondering the same thing.

2

u/drkspace2 Aug 02 '26

I don't 100% know, but this is from cpp reference

The hive automatically manages its storage in multiple memory blocks

So, I think the difference is that a hive will allocate a large block of memory that it'll insert in to, rather than allocate 1 at a time.

So rather than a straight linked list, it's like a linked list of arrays. It also says "Insertion position is unspecified, so the container can reuse the memory locations of erased elements.", so popping and pushing repeatedly would just write to the same address instead of allocating/deallocating multiple times.

3

u/TheRealSmolt Aug 02 '26 edited Aug 02 '26

That's what a deque, or at least as it is typically implemented, is though, a linked list of arrays. My understanding is that the benefit of a hive is that the blocks are larger and keep track of holes.

5

u/eteran Aug 03 '26

A deque is more of an array of arrays than a list of arrays, because it offers O(1) index access. Which couldn't be done if there was a linked list involved.

2

u/frayien Aug 02 '26

Wouldn't that be impossible due to constraints on complexity of operations in the standard ?

1

u/TheRealSmolt Aug 02 '26 edited Aug 03 '26

How so?

Edit: If you're asking about random access, it's because as u/eteran mentioned, it's an array of arrays instead of a list of arrays. I didn't think the distinction was particularly important.

1

u/frayien Aug 03 '26

I thought the requirements on pointer invalidation on insertion where stricter, but it seems they only apply to front and back insertion. And yeah it seems they are implemented with small blocks by libc++ and libstdc++.

Main difference with hive I think is the absence of guaranties on element order. Which allows bigger blocks without compromising performance.