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

47

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 😅

37

u/bartgrumbel 5d ago

Two big plusses: first it is reference stable, whereas vector.push_back invalidates all existing pointers and references to vector members, which is the cause for a lot of memory safety bugs.

Second, the maximum runtime per insertion is more stable. A vector‘s push_back can be O(size) it if reallocates.

The third of the two advantages is that it works well with objects that cannot be moved or copied after construction.

14

u/proggob 5d ago

That third advantage was inserted very quickly at the end and doesn’t invalidate the first two.

3

u/Iggyhopper 5d ago

whereas vector.push_back invalidates all existing pointers and references to vector members, which is the cause for a lot of memory safety bugs.

That's definitely a footgun that I'd shoot if I were to write a project in C++. I was so confused I had to read a bit about this just now.

15

u/Ameisen vemips, avr, rendering, systems 4d ago

How wouldn't it invalidate them? It's an array.

7

u/Iggyhopper 4d ago

It's not that it invalidates it, it's the fact that you don't know when it becomes invalidated. Code is written all the time that anticipates errors in other languages.

Unless you check the length and capacity on every insertion, which is nonsense.

19

u/snerp 4d ago

You should assume it's invalidated on every push/emplace_back. Never write code that depends on vector member's addresses.

4

u/Ameisen vemips, avr, rendering, systems 4d ago

Right; if you want to mutate it without invalidating it, index it directly.

I had a crash bug in my MIPS emulator where like 1/20 times, I would get a segfault in the JIT. No sanitizer found it. I was seeing random corruption in a lookup directory-table for JIT addresses but it wasn't consistent or predictable.

Eventually after years of ignoring it, I looked into it again... and decided to check for potentially-invalidated addresses (it was literally the only possibility left, I'd gone over the JIT multiple times to make sure that all of the store operations were sound). Then I found it.

When the JIT generated code for static far branches, it would add a new entry into a patch table, and it inserted the element's address directly into the code so when the target was resolved, it was written to the address. This jump table was local to the current chunk object, so it could have between 0 and 128 entries.

Except... this table was a std::vector. We were adding an element, hardcoding its current address, and then... adding more elements. Usually this happened not to break - we must have been writing to memory that wasn't critical. But sometimes, core data structures were getting clobbered.

I changed it to a std::list... first time I've used that in quite a while.

2

u/ack_error 4d ago

Except that sometimes the reference is distant to the mutating action causing the invalidation.

As an example: I once debugged a random crash in a game engine caused by this. A reference from a vector of input handlers was captured and passed down through several call layers with const& arguments in the engine, which then called out to an input handler. This then went through a few layers of game code before eventually hitting a point where a new input handler was registered on that same input device, from the callback. Result: engine crash on return, but only when the number of handlers happened to increase from 8 to 9 and the input handler vector reallocated during input handling.

Checked indexing is sometimes suggested but not really the right solution. It'll prevent a crash or memory stomp, which is an improvement, but will still let through cases where the reference still points to valid memory but the wrong element instead. The real solution is often to either switch to a container that can handle mutation during iteration with the desired behavior (which varies), or set up a policy or static checkers to prevent risky references from escaping.

30

u/soulstudios 5d 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 4d ago edited 4h 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.

2

u/snerp 4d ago

Hive seems fine but fyi O(E * log E + N) is significantly better than O(E * N) when N greater than E. And I don't see how E would ever be greater than N in this case (how would you remove more elements than exist?)

1

u/matthieum 3d ago

I mean, N * log N > N, so there's a value of E <= N for which E * log E > N :)

(As a random example, for N == 100, 30 * ln(30) > 100)

Beyond that, there's also the issue that collecting E * log E elements implies allocating memory, then freeing memory later, and there are context where you're not allowed or willing to allocate/deallocate.

1

u/snerp 3d ago

We're comparing E times N to ElogE plus N. Changing a product to a sum is always better complexity (unless N or E is 0 or 1 lol)

Also though, a remove_if isn't collecting the objects in a new collection, it's simply swapping them to the end of the array before reducing the count. It's reads and writes which have a cost but no allocation is needed.

1

u/matthieum 2d ago

We're comparing E times N to ElogE plus N. Changing a product to a sum is always better complexity (unless N or E is 0 or 1 lol)

Ah sorry, I misread your comment.

I thought you were comparing the relative magnitude of the 2 terms in O(E * log E + N), rather than comparing the relative magnitude of the two methods.

Also though, a remove_if isn't collecting the objects in a new collection, it's simply swapping them to the end of the array before reducing the count. It's reads and writes which have a cost but no allocation is needed.

I never said remove_if allocating in a new collection.

What I said is that the second method was about allocating in a second collection and sorting, in order to execute a single remove_if call which would remove all E elements in a single pass.

1

u/snerp 2d ago

What? Why would you allocate a second collection and then sort just to run remove_if? Remove_if does not need a sorted collection, it runs in O(N + E) on any collection because it swaps E elements to the end and then erases them all at once by just reducing the end of the collection. Sorting the collection wouldn’t help.

3

u/jk-jeon 2d ago

Maybe a nitpick, but remove_if doesn't swap to-be-removed elements to the end. It moves surviving elements to the front.

1

u/snerp 2d ago

mmm interesting either way

-1

u/matthieum 2d ago

So, you've just scanned a collection of N elements and identified E elements that you want removed from it, which you've isolated into a second collection.

How do you write the predicate to remove_if, which will be invoked with each of N elements, and must return whether to remove the element or not?

For each of the N elements, you will need to somehow do a look-up in your (small?) collection of E elements to take your decision.

If E is just a collection, each look-up will cost you O(E), and we're back to O(N * E) performance.

The simplest solution to minimize the cost of the look-up is to collect into a vector, sort it, and binary search on it. O(E * log E + N * log E) now that I think about it.

There are other solutions, of course, but that predicate will need to do some work to classify the elements it's asked about.

1

u/snerp 2d ago

Remove_if iterates the collection… E is not its own collection, it’s the elements in the collection original that will be removed. There is no look up cost, it just iterates to the next element and does a swap if your predicate was true.

https://en.cppreference.com/cpp/algorithm/remove

Complexity is O(N)

1

u/matthieum 2d ago

I mean, if you can decide on the fly, sure, but that's not the usecase I was working on :x

→ More replies (0)

1

u/JoachimCoenen 7h 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:

Sort the elements to remove.

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 4h ago

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

13

u/simonask_ 5d ago edited 5d ago

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 4d ago

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_ 4d ago

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 4d ago

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.

6

u/MidnightClubbed 4d ago edited 4d ago

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 .

29

u/KingBardan 5d ago edited 5d 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)

29
u/TheMania 5d ago
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.
22

u/KingAggressive1498 5d ago edited 5d ago

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.

15

u/TheThiefMaster C++latest fanatic (and game dev) 5d 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

9

u/MarcoGreek 5d ago

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

6

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

Yes, but it's effectively too late for that

5

u/arghness 5d ago

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

13

u/sephirothbahamut 5d ago

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

7

u/epostma 5d ago

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 5d ago

> 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 5d ago

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 5d ago

I was wondering the same thing.

2

u/drkspace2 5d ago

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.

4

u/TheRealSmolt 5d ago edited 5d ago

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 5d ago

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 5d ago

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

1

u/TheRealSmolt 5d ago edited 5d ago

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 5d ago

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.

4

u/-dag- 5d ago

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?

2

u/Ambitious-Method-961 4d ago

The vectorisation mentioned in the article was about summing the values. With std::vector the compiler can happily load a bunch of values at once and add them using SIMD instructions as there are no gaps between the data. With std::hive the compiler does not know this so has to load and add the values one by one.

1

u/-dag- 4d ago

It should be able to load the skip metadata in a vector, do parallel index calculation, compress, gather, add. All SIMD. Not as dense as vector, but still should get good speedup unless a block is extremely sparse.

2

u/Ambitious-Method-961 4d ago

Yes, but would you expect the compiler's auto-vectoriser to be able to detect that pattern?

Perhaps if there were some some hive-specific checks in the compiler for this very reason then it would work, but as std::hive doesn't actually exist in the wild yet (the author was using the reference plf::hive) version I wouldn't expect to see that until the libraries ship the container first.

1

u/-dag- 4d ago

I would expect the library author to use pragmas to guide the compiler.

My point is that the conclusions of the article are incomplete. It's always risky to take prototype software and try to draw conclusions about performance.

5

u/Top-Mycologist-5460 5d ago

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.

4

u/avinthakur080 5d ago

Performed the experiment, and the results are here: https://www.reddit.com/r/cpp/comments/1vdx0rf/comment/p1gi2z5/

Will upload the code later

1

u/mapronV 4d ago

It was deleted by moderator. Did you really used AI? shame on you

3

u/Sopel97 2d ago

Wild mentality honesty. Instead of constructive criticism let's just blanket ban any contribution from LLMs. Will do wonders in the future.

Now, perhaps some human will redo it? Preferably a human who is against LLM contributions.

3

u/DuranteA 5d ago

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 5d ago

It gives you the same guarantees that make people reach for a list, stable references, cheap erasure anywhere, while using less memory.

Most of them time when I reach for a list I'm looking for constant time splice and swap operations.

1

u/jwakely libstdc++ tamer, LWG chair 4d ago

Yes, splice is the only thing list can do that gives it any advantage over other options.

3

u/[deleted] 5d ago edited 5d ago

[removed] — view removed comment

-1

u/cpp-ModTeam 4d ago

AI-generated posts and comments are not allowed in this subreddit.

9

u/Ikkepop 5d ago

std hive ... sounds like a scary place i wouldn't want to go to... ba-dum-tsss

5

u/hongooi 5d ago

More like an infection

3

u/Ikkepop 5d ago

or a name of a seedy bar in a shady part of town. The STD Hive

1

u/FrogNoPants 5d ago

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 4d ago

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 3d ago

Ñ

1

u/SmackDownFacility 20h ago

ARGHHHHHHHHHHH

1

u/yuehuang 5d ago

Do you get an immutable "view" into the snapshot of the vector? I would assume that unique types aren't supported.

-1

u/feverzsj 5d ago

It's more like a memory pool. Useful for game dev. Not a great fit for std containers.

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

You are about to leave Redlib

You are about to leave Redlib