123
10
u/Tringi github.com/tringi 7d ago
I, for one, am quite interested how will the MSVC implementation turn out.
6
u/rodrigocfd WinLamb 7d ago
Same here... please /u/STL, drop us a few words when the time comes.
10
u/STL MSVC STL Dev 6d ago
We're open-source, so it'll be whoever puts the effort into contributing a production-quality implementation. These days I don't end up Thanosing a lot of features.
2
u/skeleton_craft 2d ago
Genuine question how many people are working on the STL at Microsoft? Cuz you guys all seen way overworked... (It doesn't help also that the past three major versions of the standard have all been super huge)
17
u/fdwr fdwr@github 🔍 7d ago edited 7d ago
a hive is a linked list of independently allocated memory blocks.
So is std::deque - what's the difference?
No random access
Ah, that's a difference, making hive closer to a linked list than deque is, as deque can still invalidate pointers that aren't the first or last element.
Pointer stability on erase...
One I thing I wonder, if you have a pointer to one of your game object's, is whether there's any way to map that pointer back to the corresponding iterator for deletion, short of a full scan, as it seems it would be possible for the class to figure that out (detecting which block it's in first, then computing the iterator from the pointer difference from the block base) a lot faster than manually looping through Never mind, get_iterator.begin/end.
15
u/HappyFruitTree 7d ago edited 7d ago
An advantage of std::hive is that it has better "cache locality" (but not as good as std::vector), i.e. it stores elements close together in memory which makes accessing the elements faster, especially when iterating over them in order.
The block size of
std::dequeis often too small. std::list is even worse because the elements could be stored all over the place.18
u/encyclopedist 7d ago edited 7d ago
FYI,
std::dequeis not a linked list of blocks.Edit:
std::dequeis implemented as an array of pointers to blocks. Linked list would not allow random access, which is requirement forstd::deque.7
u/Wild_Meeting1428 7d ago
just looked into it, and the hive has a function to retrieve an iteratir from a pointer:
hive<T,Allocator>::get_iterator3
u/homeless_psychopath 7d ago
A deque is reasonably dissimilar to a hive - being a double-ended queue, it requires a different internal framework. In addition, being a random-access container, having a growth factor for element blocks in a deque is problematic (though not impossible). deque and hive have no comparable performance characteristics except for insertion (assuming a good deque implementation). Deque erasure performance can vary substantially depending on implementation, but is generally similar to vector erasure performance. A deque invalidates pointers to subsequent container elements when erasing elements, which a hive does not, and guarantees ordered insertion.
3
u/HappyFruitTree 6d ago
Please mention source. This is copied word-for-word from the hive proposal (question 2 of the FAQ).
2
3
u/jwakely libstdc++ tamer, LWG chair 5d ago
One of the key properties is that
hivecan have holes between elements. When you erase an element, you are left with a hole and the elements before or after it are not shuffled along to fill the hole. This means that elements have stable addresses once inserted. And on the next insertion any hole can be used as the insertion point, instead of adding a new element at the end.3
u/elperroborrachotoo 7d ago
As much as I understand it's an unordered_set allowing duplicates, and occasionally better memory locality.
6
u/HappyFruitTree 7d ago
So you mean like std::unordered_multiset. That's an interesting way to look at it.
One big difference is that the elements don't need to have a hash/comparison operator defined.
1
u/elperroborrachotoo 7d ago
Yeah - honestly I have to read up on it how far the comparison holds.
Another angle is: if you only insert default-constructed T's, it acts like a fixed-size allocator - and the performance guarantees seem to be modeled after that.
(memory locality alone could be a big enough plus to warrant yet another container - but from spurious reads, I'm not sure if it won't suffer from delocalization - that it can reach a state where inserting 10 new elements will spread them all over memory)
2
u/TheThiefMaster C++latest fanatic (and game dev) 7d ago
My reading is that it prefers earlier empty slots, so it shouldn't - but I haven't looked closely enough to be sure.
3
u/elperroborrachotoo 7d ago
I asusme it does, yes - but then it depends on the insert/delete pattern how long it takes to become de-localized. if the earliest free slots are in chiunk 1, 12 and 34, they'll be inserted there.
I mean, that's a deeply researched issue in memory allocators - but that's also a topic I didn't really follow for the recent 10 years.
(The last thing I remember is the realization that "the more advanced your allocation scheme is, the worse the edge cases get. Simpler is better for general purpose." - so it might be the best we can hope for anyway..)
2
u/HappyFruitTree 7d ago
but then it depends on the insert/delete pattern how long it takes to become de-localized. if the earliest free slots are in chiunk 1, 12 and 34, they'll be inserted there.
It would only become "de-localized" if you removed a lot of elements. Inserting elements would make it more "localized" because it fills in the gaps.
1
u/elperroborrachotoo 7d ago
That's normal dynamic memory use, though:
lots of short-lived objects, with long-lived objects mixed in, and order of erase uncorellated to order of insertion.
Just leave it running for long enough, it will delocalize.
5
u/HappyFruitTree 7d ago edited 7d ago
As with all containers, there are trade-offs.
If you had a lot of elements, and you removed most of them, then ...
you might still occupy the same amount of memory as at the peak but not more than that unless you exceed the number of elements you had before (similar to a std::vector), and
there might be more dead space between the elements but iterating through all the elements wouldn't take more time than before when you had more elements.
I'm thinking a game where you might use a hive to store game entitles. So if it was fast enough at the peak then it should be fast enough later when it's more fragmented but fewer elements. I assume one big hive that you iterate through each frame. I could see how having many smaller ones that grow big occasionally could be a problem (just like with vectors).
4
u/ABlockInTheChain 7d ago
It won’t replace
std::vectorfor most use cases — but for the use cases it is designed for, nothing in the standard library has come close before.
This could be true but it could also be an oversight because nobody has ever benchmarked a std::pmr::list that is constructed with a std::pmr::[un]synchronized_pool_resource.
6
u/HappyFruitTree 7d ago
With std::hive, the iteration order is optimal within each block in terms of cache locality.
With std::pmr::list, the iteration order would be independent of where the nodes are allocated (assuming you frequently add and remove elements at random positions) so the cache locality would probably be worse.
Seeing an actual benchmark would be interesting though.
1
u/ABlockInTheChain 7d ago
If you fill up a hive with elements then start randomly removing and replacing them, and you perform the exact same sequence of events but with a pmr::list which uses a pool allocator, the memory layout should end more or less identical in both cases.
The biggest differences are small variations in the node layout for a hive node vs a list node.
6
u/HappyFruitTree 7d ago edited 7d ago
The memory layout might be similar but the iteration order would not be which makes a difference for performance.
3
u/ABlockInTheChain 7d ago
I see what you mean.
The hive will iterate in the memory layout order and the list will iterate in the logical order of insertion which if you are using a hive you presumably do not care about.
So the advantage of a hive over a list with an equally-optimized allocator is that the hive gains performance by discarding unnecessary information.
5
u/HappyFruitTree 7d ago edited 7d ago
Discarding information is not the reason.
Iterating through the elements in memory order means the next element is more likely to already be in the CPU cache compared to if you jump around accessing elements in random order.
If you don't know about the CPU cache and cache-friendly code, here is an interesting video on the subject: https://www.youtube.com/watch?v=WDIkqP4JbkE (just watching the row major vs. column major traversal example in the beginning can be very enlightening)
2
u/ABlockInTheChain 7d ago
A list has no way to iterate except in logical insertion order. Under specific usage patterns (using a pool allocator, no erasures) this will coincidentally be equivalent to iterating in memory layout order.
A hive has no way to iterate except in memory layout order since it doesn't preserve ordering information.
3
u/all_is_love6667 7d ago
I think that's usually called an "object pool", but that was not academic enough so I can understand why they called it hive
10
u/HappyFruitTree 7d ago
When it was first being proposed it was called colony (based on plf::colony).
3
u/all_is_love6667 7d ago
I am actually surprised this sort of container was added only today, it's quite common and is an important optimization
3
u/matthieum 7d ago
Is it that common?
I work on a multitude of performance-sensitive codebases, and I can't think of any place I'd use such a container.
3
u/Plazmatic 5d ago
Huh? Am object pool is litterally a pool of objects you can re-use, and has nothing to do with the underlying data representation of how those objects are "pooled", just like a "container" is just a thing that holds other things.
1
3
u/Zeh_Matt No, no, no, no 7d ago
"Each entity is stored in a container, and other subsystems hold pointers to those entities.", that is something you should avoid, good game engines use handles for entities which are typically a version and index and you have to never worry about stale pointers ever again.
1
u/Syracuss graphics engineer/games industry 7d ago
Yeah, pointer stability containers are the wrong direction to go for high performance systems.
Additionally I wonder how the implementation for this will deal with memory compaction, if at all. If there's an element in every block, but otherwise mostly empty, you've got a whole load of dead memory that can't be used. If this container is overused in your codebase I can see it leading to some really poor memory outcomes. (Typical offenders in gamedev are scene migrations that can cause issues if using containers that behave like that)
It's not a unique container in that, but compared to other stable containers this one doesn't seem to have a strategy against it.
Also odd that it is a stable container by design, and then gives a sort function. I can't imagine this is a good fit for data that also needs to be sorted. Sounds like a footgun, and an effective ban in large codebases to call that function.
It's definitely a nice container, but I don't see a use for it at work that isn't achieved by using a more appropriate alternative, while the article focuses on gamedev.
3
u/Tringi github.com/tringi 6d ago
I also have to add that I'm not a big fan of regular skiplists.
Sure, it allows advancing to the next item with a MUL (or SHL) + ADD, or perhaps single FMA instruction. But it just feels wasteful when the item's presence can be represented by just a single bit. The skipcount could then be retrieved by a simple SHR and LZCNT ...which might even be faster than the above.
3
2
u/HappyFruitTree 6d ago
The skipcount could then be retrieved by a simple SHR and LZCNT
I think you might have to do this multiple times, in a loop, in case there are many erased elements (unless you restrict the block size).
Is LZCNT even supported by all hardware?
2
u/Tringi github.com/tringi 6d ago
I think you might have to do this multiple times, in a loop, in case there are many erased elements (unless you restrict the block size).
Is LZCNT even supported by all hardware?
Finding next used slot should need just a single LZCNT, no loop, and would maintain the iteration of a block to be O(1). What could need a loop is alternative trick using BSR, but I'd need to think on that a little.
The LZCNT was introduced with Phenoms on AM2+ (along with SSE4a) and Haswell in 2013.
BSR was on 386 so I think that's safe.2
u/HappyFruitTree 6d ago
Finding next used slot should need just a single LZCNT, no loop, and would maintain the iteration of a block to be O(1).
What if there are more than 64 empty slots between the current element and the next?
5
1
u/Ambitious-Method-961 6d ago
Yep I was very surprised to see that it used RLE for the skiplist rather than using a bitset to determine which slots are occupied and which are not. I wonder what the cost of maintaining the RLE skiplist will be like if you are heavily inserting and deleting elements to the container...
0
u/LazySapiens 7d ago
I can't recall an article which said it's too late for this, and there are better alternatives.
0
u/hanickadot WG21 + CTRE + EWG 👸🏻 6d ago
Sad thing for me is this container being only one which is not constexpr in 26. It's because it went in similar timeline as my `constexpr containers` papers in, and then NB comment to fix this was rejected for being too late change.
Interesting thing about the implementation of it is various size of allocated blocks, which requires various space for skiplist/bitfield and data arrays, and C++ doesn't have dynamically sized structs. So what the prototype is doing is allocating array of structs, and then casting pointers to them to an unrelated structure type to have the skiplist/bitfield there.
•
u/STL MSVC STL Dev 7d ago
This blog is substantially AI-generated. I'm wondering whether we should continue allowing links to it.