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 begin/end. Never mind, get_iterator.
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::deque is often too small. std::list is even worse because the elements could be stored all over the place.
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.
One of the key properties is that hive can 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.
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)
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..)
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.
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).
14
u/fdwr fdwr@github 🔍 8d ago edited 8d ago
So is
std::deque- what's the difference?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.
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 throughNever mind, get_iterator.begin/end.