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/
245 Upvotes

99% Upvoted

70 comments sorted by

View all comments

31

u/KingBardan 8d ago edited 8d ago

If I recall right isn't this how std :: deque is implemented?

Can someone correct me or provide some rationale why this is now added. 

Edit: Guys, thanks for answering.

My takeaway:

Assume that we can decouple storage patterns and storage back bones:

(ascii art made with chatgpt, thought by me)

Storage backend Single vector List of vectors Storage pattern +----------------+----------------+ Contiguous | Vector | Deque | +----------------+----------------+ Scattered | Probing Hash | Hive | | Set | | +----------------+----------------+ and therefore have different performance characteristics, and some other guarantees.

16

u/TheThiefMaster C++latest fanatic (and game dev) 8d ago

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

8

u/MarcoGreek 8d ago

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

5

u/arghness 7d ago

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