The purpose of a container in the standard library cannot be to provide the optimal solution for all scenarios. Inevitably in fields such as high-performance trading or gaming, the optimal solution within critical loops will be a custom-made one that fits that scenario perfectly. However, outside of the most critical of hot paths, there is a wide range of application for more generalized solutions.
Hive is a formalisation, extension and optimization of what is typically known as a 'bucket array' container in game programming circles; similar structures exist in various incarnations across the high-performance computing, high performance trading, 3D simulation, physics simulation, robotics, server/client application and particle simulation fields (see: https://groups.google.com/a/isocpp.org/forum/#!topic/sg14/1iWHyVnsLBQ).
The concept of a bucket array is: you have multiple memory blocks of elements, and a boolean token for each element which denotes whether or not that element is 'active' or 'erased', commonly known as a skipfield. If it is 'erased', it is skipped over during iteration. When all elements in a block are erased, the block is removed, so that iteration does not lose performance by having to skip empty blocks. If an insertion occurs when all the blocks are full, a new memory block is allocated.
The advantages of this structure are as follows: because a skipfield is used, no reallocation of elements is necessary upon erasure. Because the structure uses multiple memory blocks, insertions to a full container also do not trigger reallocations. This means that element memory locations stay stable and iterators stay valid regardless of erasure/insertion. This is highly desirable, for example, in game programming because there are usually multiple elements in different containers which need to reference each other during gameplay and elements are being inserted or erased in real time.
Problematic aspects of a typical bucket array are that they tend to have a fixed memory block size, do not re-use memory locations from erased elements, and utilize a boolean skipfield. The fixed block size (as opposed to block sizes with a growth factor) and lack of erased-element re-use leads to far more allocations/deallocations than is necessary. Given that allocation is a costly operation in most operating systems, this becomes important in performance-critical environments. The boolean skipfield makes iteration time complexity undefined, as there is no way of knowing ahead of time how many erased elements occur between any two non-erased elements. This can create variable latency during iteration. It also requires branching code, which may cause issues on processors with deep pipelines and poor branch-prediction failure performance.
A hive uses a non-boolean method for skipping erased elements, which allows for O(1) amortized iteration time complexity and more-predictable iteration performance than a bucket array. It also utilizes a growth factor for memory blocks and reuses erased element locations upon insertion, which leads to fewer allocations/reallocations. Because it reuses erased element memory space, the exact location of insertion is undefined. In most implementations it's likely (for performance reasons) that unless no erasures have occurred or an equal number of erasures and insertions have occurred, the insertion location would be the back of the container. The container is therefore considered unordered but sortable. Lastly, because there is no way of predicting in advance where erasures ('skips') may occur during iteration, an O(1) time complexity [ ] operator is not necessarily possible (depending on implementation) and therefore, the container is bidirectional but not random-access.
There are two patterns for accessing stored elements in a hive: the first is to iterate over the container and process each element (or skip some elements using the advance/prev/next/iterator ++/-- functions). The second is to store the iterator returned by the insert() function (or a pointer derived from the iterator) in some other structure and access the inserted element in that way. To better understand how insertion and erasure work in a hive, see the following images.
The following images demonstrate how insertion works in a hive compared to a vector when size == capacity (note: images use old name for this proposal, colony. it is the same container).
The following images demonstrate how non-back erasure works in a hive compared to a vector.
There is additional introductory information about the container's structure in this CPPcon talk, though some of it's information is out of date (hive/colony no longer uses a stack but a free list instead, benchmark data is out of date, etc), and more detailed implementation information is available in this CPPnow talk.
None at present.
Note: Throughout this document I will use the term 'link' to denote any form of referencing between elements whether it be via ids/iterators/pointers/indexes/references/etc.
There are situations where data is heavily interlinked, iterated over frequently, and changing often. An example is the typical video game engine. Most games will have a central generic 'entity' or 'actor' class, regardless of their overall schema (an entity class does not imply an ECS). Entity/actor objects tend to be 'has a'-style objects rather than 'is a'-style objects, which link to, rather than contain, shared resources like sprites, sounds and so on. Those shared resources are usually located in separate containers/arrays so that they can re-used by multiple entities. Entities are in turn referenced by other structures within a game engine, such as quadtrees/octrees, level structures, and so on.
Entities may be erased at any time (for example, a wall gets destroyed and no longer is required to be processed by the game's engine, so is erased) and new entities inserted (for example, a new enemy is spawned). While this is all happening the links between entities, resources and superstructures such as levels and quadtrees, must stay valid in order for the game to run. The order of the entities and resources themselves within the containers is, in the context of a game, typically unimportant, so an unordered container is okay.
Unfortunately the container with the best iteration performance in the standard library, vector[1], loses pointer validity to elements within it upon insertion, and pointer/index validity upon erasure. This tends to lead to sophisticated and often restrictive workarounds when developers attempt to utilize vector or similar containers under the above circumstances.
std::list and the like are not suitable due to their poor locality, which leads to poor cache performance during iteration. This is however an ideal situation for a container such as hive, which has a high degree of locality. Even though that locality can be punctuated by gaps from erased elements, it still works out better in terms of iteration performance[1] than every existing standard library container other than deque/vector, regardless of the ratio of erased to non-erased elements.
Some more specific requirements for containers in the context of game development are listed in the appendix.
As another example, particle simulation (weather, physics etcetera) often involves large clusters of particles which interact with external objects and each other. The particles each have individual properties (spin, momentum, direction etc) and are being created and destroyed continuously. Therefore the order of the particles is unimportant, what is important is the speed of erasure and insertion. No current standard library container has both strong insertion and non-back erasure speed, so again this is a good match for hive.
Reports from other fields suggest that, because most developers aren't aware of containers such as this, they often end up using solutions which are sub-par for iterative performance such as std::map and std::list in order to preserve pointer validity, when most of their processing work is actually iteration-based. So, introducing this container would both create a convenient solution to these situations, as well as increasing awareness of better-performing approaches in general. It will also ease communication across fields, as opposed to the current scenario where each field uses a similar container but each has a different name for it.
This is purely a library addition, requiring no changes to the language.
The three core aspects of a hive from an abstract perspective are:
Each memory block houses multiple elements. The metadata about each block may or may not be allocated with the blocks themselves (could be contained in a separate structure). This metadata should include at a minimum, the number of non-erased elements within each block and the block's capacity - which allows the container to know when the block is empty and needs to be removed from the iterative chain, and also allows iterators to judge when the end of one block has been reached. A non-boolean method of skipping over erased elements during iteration while maintaining O(1) amortized iteration time complexity is required (amortized due to block traversal, which would typically require a few more operations). Finally, a mechanism for keeping track of elements which have been erased must be present, so that those memory locations can be reused upon subsequent element insertions.
The following aspects of a hive must be implementation-defined in order to allow for variance and possible performance improvement, and to conform with possible changes to C++ in the future:
However the implementation of these is significantly constrained by the requirements of the container (lack of reallocation, stable pointers to non-erased elements regardless of erasures/insertions).
In terms of the original reference implementation (current reference implementation here) the specific structure and mechanisms have changed many times over the course of development, however the interface to the container and its time complexity guarantees have remained largely unchanged (with the exception of the time complexity for updating skipfield nodes - which has not impacted significantly on performance). So it is reasonably likely that regardless of specific implementation, it will be possible to maintain this general specification without obviating future improvements in implementation, so long as time complexity guarantees for the above list are implementation-defined.
Below I explain the reference implementation's approach in terms of the three core aspects described above, along with descriptions of some alternatives implementation approaches.
In the reference implementation this is essentially a doubly-linked list of 'group' structs containing (a) a dynamically-allocated element memory block, (b) memory block metadata and (c) a dynamically-allocated skipfield. The memory blocks and skipfields in this implementation have a growth factor of 2 from one group to the next. The metadata includes information necessary for an iterator to iterate over hive elements, such as the last insertion point within the memory block, and other information useful to specific functions, such as the total number of non-erased elements in the node. This approach keeps the operation of freeing empty memory blocks from the hive container at O(1) time complexity. Further information is available here.
Using a vector of group structs with dynamically-allocated element memory blocks, using the swap-and-pop idiom where groups need to be erased from the iterative sequence, would not work. To explain, when a group becomes empty of elements, it must be removed from the sequence of groups, because otherwise you end up with highly-variable latency during iteration due to the need to skip over an unknown number of empty groups when traversing from one non-empty group to the next. Simply erasing the group will not suffice, as this would create a variable amount of latency during erasure when the group becomes empty, based on the number of groups after that group which would need to be reallocated backward in the vector. But even if one swapped the to-be-erased group with the back group, and then pop'd the to-be-erased group off the back, this would not solve the problem, as iterators require a stable pointer to the group they are traversing in order to traverse to the next group in the sequence. If an iterator pointed to an element in the back group, and the back group was swapped with the to-be-erased group, this would invalidate the iterator.
A vector of pointers to group structs is more-possible. Erasing groups would still have highly-variable latency due to reallocation, however the cost of reallocating pointers may be negligible depending on architecture. While the number of pointers can be expected to be low in most cases due to the growth factor in memory blocks, if the user has defined their own memory block capacity limits the number of pointers could be large, and this has to be taken into consideration. In this case using a pop-and-swap idiom is still not possible, because while it would not necessarily invalidate the internal references of an iterator pointing to an element within the back group, the sequence of blocks would be changed and therefore the iterator would be moved backwards in the iterative sequence.
A vector of memory blocks, as opposed to a vector of pointers to memory blocks or a vector of group structs with dynamically-allocated memory blocks, would also not work, both due to the above points and because as it would (a) disallow a growth factor in the memory blocks and (b) invalidate pointers to elements in subsequent blocks when a memory block became empty of elements and was therefore removed from the vector. In short, negating hive's beneficial aspects.
A short note about the exchange of user-defined block capacity limits between hives: these generally follow the pattern for allocators - which makes sense as they may have a relationship with user-supplied allocator constraints. They're transferred during move and copy construction, operator = && and swap, but not during splice or operator = &. However they're also transferred during copy construction. Unlike allocators, there is no option to specify new capacity limits in the copy/move constructor, however this makes sense for the move constructor, because specifying limits would cause the constructor to throw if the transferred blocks did not fit within the new limits. If the user wants to specify new capacity limits when copying from another hive, they do the following instead of calling a copy constructor: hive<int> h(hive_limits(10,50)); h = other_hive;
Likewise if they want to specify new capacity limits when moving from another hive, they can: hive<int> h(std::move(other_hive)); r.reshape(10, 50);
The reference implementation currently uses a skipfield pattern called the Low complexity jump-counting pattern. This effectively encodes the length of runs of consecutive erased elements, into a skipfield, which allows for O(1) time complexity during iteration. Since there is no branching involved in iterating over the skipfield aside from end-of-block checks, it can be less problematic computationally than a boolean skipfield (which has to branch for every skipfield read) in terms of CPUs which don't handle branching or branch-prediction failure efficiently (eg. Core2). It also does not have the variable latency associated with a boolean skipfield.
The pattern stores and modifies the run-lengths during insertion and erasure with O(1) time complexity. It has a lot of similarities to the High complexity jump-counting pattern, which was a pattern previously used by the reference implementation. Using the High complexity jump-counting pattern is an alternative, though the skipfield update time complexity guarantees for that pattern are effectively undefined, or between O(1) and O(skipfield length) for each insertion/erasure. In practice those updates result in one memcpy operation which may resolve to a much smaller number of SIMD copies at the hardware level. But it is still a little slower than the Low complexity jump-counting pattern. The method you use to skip erased elements will typically also have an effect on the type of memory-reuse mechanism you can utilize.
A pure boolean skipfield is not usable because it makes iteration time complexity undefined - it could for example result in thousands of branching statements + skipfield reads for a single ++ operation in the case of many consecutive erased elements. In the high-performance fields for which this container was initially designed, this brings with it unacceptable latency. However another strategy using a combination of a jump-counting and boolean skipfield, which saves memory at the expense of computational efficiency, is possible as follows:
This approach has the advantage of still performing O(1) iterations from one non-erased element to the next, unlike a pure boolean skipfield approach, but compared to a pure jump-counting approach introduces 3 additional costs per iteration via (1) a branch operation when checking the bitfield, (2) an additional read (of the erased element's memory space) and (3) a bitmasking operation + bitshift to read the bit. But it does reduce the memory overhead of the skipfield to 1 bit per-element. In the early days of hive/colony I experimented with using both byte-based boolean skipfields and bit-based boolean skipfields. The bit-based ones were always slower, regardless of the technique. And the jump-counting skipfield was faster than both of those.
Another method worth mentioning is the use of a referencing array - for example, having a vector of elements, together with a vector of either indexes or pointers to those elements. When an element is erased, the vector of elements itself is not updated - no elements are reallocated. Meanwhile the referencing vector is updated and the index or pointer to the erased element is erased. When iteration occurs it iterates over the referencing vector, accessing each element in the element vector via the indexes/pointers. The disadvantages of this technique are (a) much higher memory usage, particularly for small elements and (b) highly-variable latency during erasure due to reallocation in the referencing array. Since once of the goals of hive is predictable latency, this is likely not suitable.
Packed arrays are not worth mentioning as the iteration method is considered separate from the referencing mechanism, making them unsuitable for a std:: container.
There are two valid approaches here; both involve per-memory-block free lists, utilizing the memory space of erased elements. The first approach forms a free list of all erased elements. The second forms a free list of the first element in each run of consecutive erased elements ("skipblocks", in terms of the terminology used in the jump-counting pattern papers). The second can be more efficient, but requires a doubly-linked free list rather than a singly-linked free list, at least with a low-complexity jump-counting skipfield - otherwise it would become an O(N) operation to update links in the skipfield, when a skipblock expands or contracts during erasure or insertion.
The reference implementation currently uses the second approach, using three things to keep track of erased element locations:
Using indexes for next and previous links, instead of pointers, reduces the necessary bit-depth of the next and previous links, thereby reducing the necessary over-alignment of the container's element type. If a global (ie. all memory blocks) free list were used, pointers would be necessary, as hive is bidirectional and does not support the [ ] operator. This would potentially increase the necessary over-alignment of the element type to 128 bits for a doubly-linked free list. A global free list would also decrease cache locality when traversing the free list by jumping between memory blocks.
Previous versions of the reference implementation used a singly-linked free list of erased elements instead of a doubly-linked free list of skipblocks. This was possible with the High complexity jump-counting pattern, but not possible using the Low complexity jump-counting pattern as it cannot calculate a skipblock's start node location from a middle node's value like the High complexity pattern can. But using free-lists of skipblocks is a more efficient approach as it requires fewer free list nodes. In addition, re-using only the start or end nodes of a skipblock is faster because it never splits a single skipblock in two (which would require adding a new skipblock to the free list).
The main reason a doubly-linked free list is necessary is for when you erase an element which is in between two skipblocks. In that case two skipblocks must be combined into one skipblock, and the previous secondary skipblock must be removed from that block's free list of skipblocks. If the free list is singly-linked, the hive must do a linear search through the free list to find the skipblock prior to the secondary skipblock mentioned, in order to update that free list node's "next" index link. This is a non-O(1) operation. However if a doubly-linked free list is used, the prior skipblock is linked to from the secondary skipblock mentioned, making updating all free list links O(1). One could however revert to a singly-linked free list of skipblocks for very small value_type's, in order to reduce the overalignment necessary to store both free list nodes in the element memory space, and eat the cost of that reduction.
One cannot use a stack of pointers (or similar) to erased elements for this mechanism, as early versions of the reference implementation did, because this can create allocations during erasure, which changes the exception guarantees of erase(). One could instead scan all skipfields until an erased location was found, or simply have the first item in the list above and then scan the first available block, though both of these approaches would be slow.
In terms of the alternative boolean + jump-counting skipfield approach described in the erased-element-skip-method section above, one could store both the jump-counting data and free list data in any given erased element's memory space, provided of course that elements are aligned to be wide enough to fit both.
A final note: due to the strong variability in terms of time complexity requirements between the different ways of implementing these three core aspects of the container, where there likely to be significant variance based on implementation the time complexity of each implementation will not be included in the technical specification.
Any iterator implementation is going to be dependent on the erased-element-skipping mechanism used. The reference implementation's iterator stores a pointer to the current 'group' struct mentioned above, plus a pointer to the current element and a pointer to its corresponding skipfield node. An alternative approach is to store the group pointer + an index, since the index can indicate both the offset from the memory block for the element, as well as the offset from the start of the skipfield for the skipfield node. However multiple implementations and benchmarks across many processors have shown this to be worse-performing than the separate pointer-based approach, despite the increased memory cost for the iterator class itself.
++ operation is as follows, utilising the reference implementation's Low-complexity jump-counting pattern:
-- operation is the same except both step 1 and 2 involve subtraction rather than adding, and step 3 checks to see if the element pointer is now before the beginning of the memory block. If so it traverses to the back of the previous group, and subtracts the value of the back skipfield node from the element pointer and skipfield pointer.
Iterators are bidirectional but also provide constant time
complexity >, <, >=, <= and <=> operators for convenience
(eg. in for loops when skipping over multiple elements per loop
and there is a possibility of going past a pre-determined end element). This is
achieved by keeping a record of the order of memory blocks. In the reference
implementation this is done by assigning a number to each memory block in its
metadata. In an implementation using a vector of pointers to memory blocks
instead of a linked list, one could use the position of the pointers within the
vector to determine this. Comparing relative order of the two iterators' memory
blocks via this number, then comparing the memory locations of the elements
themselves, if they happen to be in the same memory block, is enough to
implement all greater/lesser comparisons.
advance, prev and next (all variants)For these functions, complexity is dependent on state of hive, position of iterator and amount of distance, but in many cases will be less than linear, and may be constant. To explain: it is necessary in a hive to store metadata both about the capacity of each block (for the purpose of iteration) and how many non-erased elements are present within the block (for the purpose of removing blocks from the iterative chain once they become empty). For this reason, intermediary blocks between the iterator's initial block and its final destination block (if these are not the same block, and if the initial block and final block are not immediately adjacent) can be skipped rather than iterated linearly across, by using the "number of non-erased elements" metadata.
This means that the only linear time operations are any iterations within the initial block and the final block. However if either the initial or final block have no erased elements (as determined by comparing whether the block's capacity metadata and the block's "number of non-erased elements" metadata are equal), linear iteration can be skipped for that block and pointer/index math used instead to determine distances, reducing complexity to constant time. Hence the best case for this operation is constant time, the worst is linear to the distance.
A special case for the latter operation is the back block, where instead of comparing number of non-erased elements with capacity, we compare it with the distance between the start of the block and end(). Depending on implementation there may be other ways to check whether the block is empty (in the reference implementation we can check to see whether the head of the block's free list of erased element locations has the magic value of numeric_limits<skipfield_type>::max()). But the method above will be available to any implementation for the reasons described.
distance (all variants)The same considerations which apply to advance, prev and next also apply to distance - intermediary blocks between first and last's blocks can be skipped in constant time and their "number of non-erased elements" metadata added to the cumulative distance count, while first's block and last's block (if they are not the same block) must be linearly iterated across unless either block has no erased elements, in which case the operation becomes pointer/index math and is reduced to constant time for that block. In addition, if first's block is not the same as last's block, and last is equal to end() or --end(), or is the last element in it's block, last's block's elements can also counted from the "number of non-erased elements" metadata rather than via iteration. If first and last are in the same block but are in the first and last element slots in the block, distance can again be calculated from the "number of non-erased elements" metadata for that block.
iterator insert (all variants)Insertion re-uses previously-erased element memory locations when available, so position of insertion is effectively random unless no previous erasures have occurred, in which case all elements will be inserted linearly to the back of the container, at least in the current implementation. These details have been removed from the standard in order to allow leeway for potentially-better implementations in future - though it is expected that a hive will always reuse erased memory locations, it is impossible to predict optimal strategies for unknown future hardware.
As the technical specification says, this operation shall invalidate iterators pointing to the past-the-end iterator. It should be noted that when erased element memory spaces are reused, the location of end() does not necessarily change - "shall" in this context simply means it can, so the user must assume it will and the implementor can make changes based on that assumption. And regardless of whether it does change, this does not mean to say that those iterators which were pointing to end() are no longer usable - in most implementations "t = h.end(); h.insert(1); --t;" will result in t being an iterator pointing to an active element post-insert (provided the container was not empty prior to insertion, and erase() or clear() etc have not also been called).
But the semantics are that because the past-the-end iterator never points to an active element, inserting means that an iterator which was pointing to end() previously may now be pointing to an active element. The same cannot be said about begin(), the location of which may also change when insert() is called (if elements were erased before the current begin() location, and those memory spaces are reused). begin() always pointed to an active element, and an iterator which pointed to begin() prior to insert() may no longer be pointing to begin(), but is still pointing to an active element so is not invalidated.
void insert (all variants)For range, fill and initializer_list insertion, it is not possible to guarantee that all the elements inserted will be sequential in the hive's iterative sequence, and therefore it is not considered useful to return an iterator to the first inserted element. There is a precedent for this in the various std:: map containers. Therefore these functions return void presently.
In the case of an ordered insertion container, returning an iterator makes sense as the insert function is returning an iterator to the start of the inserted range, and the user can then iterate over that range. In hive, the range that is inserted can be distributed across multiple areas in the container, so when you return an iterator, all you do is give the user an iterator to the first item from the inserted sequence, not an iterator to the start of an iterable sequence which matches the input sequence. As such, returning an iterator Will be confusing to users and Should be disabled.
The same considerations regards iterator invalidation in singular insertion above, also apply to these inserts.
iterator erase(const_iterator position);Firstly it should be noted that erase may retain memory blocks which become completely empty of elements due to erasures, adding them to the set of unused memory blocks which are normally created by reserve(). Under what circumstances these memory blocks are retained rather than deallocated is implementation-defined - however given that small memory blocks have low cache locality compared to larger ones, from a performance perspective it is best to only retain the larger of the blocks currently allocated in the hive. In most cases this would mean the back block would almost always be retained. There is a lot of nuance to this, and it's also a matter of trading off complexity of implementation vs actual benchmarked speed vs latency. In my tests retaining both back blocks and 2nd-to-back blocks while ignoring actual capacity of blocks seems to have the best overall performance characteristics.
There are three major performance advantages to retaining back blocks as opposed to any block - the first is that these will be, under most circumstances, the largest blocks in the hive (given the built-in growth factor) - the only exception to this is when splice is used, which may result in a smaller block following a larger block (implementation-dependent). Larger blocks == more cache locality during iteration, large numbers of erased elements notwithstanding. The second advantage is that in situations where elements are being inserted to and erased from the back of the hive (this assumes no erased element locations in other memory blocks, which would otherwise be used for insertions) continuously and in quick succession, retaining the back block avoids large numbers of deallocations/reallocations. The third advantage is that deallocations of larger blocks can, in part, be moved to non-critical code regions via trim_capacity(). Though ultimately if the user wants total control of when allocations and deallocations occur they would want to use a custom allocator.
A final note about time complexity. In the technical specification there is a note stating that the time complexity of updating the erased-element-skipping mechanism (probably a skipfield of some description) is not factored into the stated time complexity and that it can be constant, linear or otherwise defined. This is to allow of leniency in terms of implementation, but also because abstract time complexity does not always describe hardware time complexity. When the reference implementation was using the high-complexity jump-counting skipfield, it's time complexity for updating the skipfield on erase was linear in the number of skipfield nodes affected (which is impossible to predict from the users's perspective, making this effectively undefined) - however these updates were almost entirely executed in terms of singular memcpy operations which on a hardware level are often a much smaller number of copies using AVX or similar.
Because of this, changing to the low-complexity jump-counting skipfield pattern (which always has abstract O(1) updates) did not affect latency and performance as much as might be expected, though it did affect performance. Hence we need to allow leniency in this area and trust developers to do the right thing in case they come up with a faster erased-element skipping mechanism which doesn't necessarily have O(1) time from an abstract point of view.
iterator erase(const_iterator first, const_iterator last)The same considerations for singular erasure above also apply for range-erasure. Algorithmically, ranged erasure is O(N) if elements are non-trivially-destructible. If they are trivially-destructible, we follow similar logic to the distance specialization above. That is to say, for the first and last blocks in the range, if the number of erased elements in that block is equal to capacity, there are no erasures in the block and we can simply create a skipblock in the skipfield without checking the skipfield values. If there are erasures in that block, we need to process the part of the skipfield which is within the range to identify which elements within the range are already erased, so that we can update size() correctly.
For any intermediary blocks between the first and last blocks, we can simply deallocate or reserve them without calling destructors of elements or processing skipfields. Hence, for trivially-destructible types, the entire operation can be linear in the number of blocks contained within the range (best case O(1)), or linear in the number of elements contained within the range (O(N)).
Lastly, specifying a return iterator for range-erase may seem pointless, as no reallocation of elements occurs in erase so the return iterator will almost always be the last iterator of the const_iterator first, const_iterator last pair. However if last was end(), the new value of end() (if it has changed due to empty block removal) will be returned. In this case either the user submitted end() as last, or they incremented an iterator pointing to the final element in the hive and submitted that as last. The latter is the only valid reason to return an iterator from the function, as it may occur as part of a loop which is erasing elements which ends when end() is reached. If end() is changed by the erasure of an entire memory block, but the iterator being used in the loop does not accurately reflect end()'s new value, that iterator could iterate past end() and the loop would never finish.
void reshape(std::hive_limits block_limits);This function updates the block capacity limits in the hive and, if necessary, changes any blocks which fall outside of those limits to be within the limits. For this reason it may trigger an exception with non-copyable/movable types, and also invalidate pointers/iterators/etc to elements.
The order of elements post-reshape is not guaranteed to be stable in order to allow for optimizations. Specifically in the instance where a given element memory block no longer fits within the limits supplied by the user, depending on the state of the hive as a whole, the elements within that memory block could be reallocated to previously-erased element locations in other memory blocks which do fit within the supplied limits. Or they could be reallocated to the back of the final memory block.
Additionally if there is empty capacity at the back of the last block in the container, at least some of the elements could be moved to that position rather than being reallocated to a new memory block. Both of these techniques increase cache locality by removing skipped memory spaces within existing memory blocks. However whether they are used is implementation-dependent.
static constexpr std::hive_limits block_capacity_hard_limits() noexcept;As opposed to block_capacity_limits(), which returns the current min/max element block capacities for a given instance of hive, this allows the user to get any implementation's min/max 'hard' lower/upper limits for element memory block capacities ie. the limits which any user-supplied limits must fit within. For example, if an implementation's hard limit is 3 elements min, 1 million elements max, all user-supplied limits must be >= 3 and <= 1 million.
This is useful for 2 reasons:
void clear();User expectation was that clear() would erase all elements but not deallocate memory blocks. If deallocation of memory blocks was desired, a clear() call can be followed by a trim_capacity() call. The time complexity for this in terms of the reference implementation is constant for trivially-destructible types and linear in the size of the sequence for non-trivially-destructible types. However in an implementation using a vector of pointers to blocks+metadata rather than a linked list, the time taken to transfer active blocks to the reserved block vector would be linear in the number of active blocks in the sequence. Hence the tech spec allows some leeway here and does not specify as constant for trivially-destructible types.
iterator get_iterator(const_pointer p) noexcept;
const_iterator get_iterator(const_pointer p) const noexcept;Because hive iterators are likely to be large, storing three
pieces of data - current memory block, current element within memory
block and potentially, current skipfield node - a program storing many
links to elements within a hive may opt to dereference iterators to
get pointers and store those instead of iterators, to save memory. This
function reverses the process, giving an iterator which can then be
used for operations such as erase. get_const_iterator was fielded as a workaround for the possibility of someone wanting to supply a non-const pointer
and get a const_iterator back, however as_const fulfills this same role when supplied to get_iterator and doesn't require expanding the interface of hive. Likewise if a user wishes to supply a pointer to iterator get_iterator(const_pointer p), they can use as_const whereas the reverse isn't true.
Note that this function is only guaranteed to return an iterator that corresponds to the pointer supplied - it makes no checks to see whether the element which p originally pointed to is the same element which p now points to. Resolving this problem is down to the end user and could involve having a unique id within elements or something similar (more info in FAQ).
As of P0447R20 the semantics of this function have been re-written to match the standard's policy regarding the reading of pointers to erased elements. That is to say, if this function is called with a pointer to an erased element, behaviour is undefined, because reading the value of a pointer to a destructed element (even without dereferencing it) could potentially crash in a given scenario on a given platform. However this function must be specified to return end() if p does not point to an element in *this, because of the following situation:
hive<int> a = {1, 2, 3};
hive<int> b = {4, 5, 6};
hive<int>::iterator c = a.begin();
int *d = &*c;
hive<int>::iterator e = b.get_iterator(d);
The get_iterator line is a perfectly valid call - except that d points to an element in a, not b. Hence, regardless of the erased/non-erased status of a given element, get_iterator must return end() when d does not match an element in *this. So in most situations, the function should still work as originally intended - returning end() if an element is erased - but this is platform-dependent and undefined behaviour. I have spoken with game developers and this situation is tenable - they deal with UB all the time and it is unproblematic. However if at some point in the future it is found to be untenable, an overload can be added to take a secondary hive-internal pointer type which stores a void* internally and dereferences to the element type on operators * and ->. P2414 is another paper dealing with this issue and problem-resolutions from that paper may factor in.
Please note that if an implementation does check whether a given element is erased, when using the LCJC skipfield pattern as the erased element skipping mechanism the criteria under "Parallel processing" in the LCJC paper must be met.
The function compares pointers against the start and ends of the various memory blocks in *this. There was some confusion that this would be problematic due to obscure rules of the standard which state that a given platform may allow addresses outside of a given memory block to have addresses that are within that memory block, at least in terms of the std::less/std::greater/>/< operators et al. According to Jens Maurer, these difficulties can be bypassed via hidden channels between the library implementation and the compiler.
bool is_active(const_iterator it) const noexcept;This function checks whether it points to a non-erased element in *this. First we must check that the memory block the iterator points to is part of the hive's current blocks - otherwise checking the skipfield might trigger an out-of-bounds exception, as the block might've been deallocated. Then we can directly use the iterator's skipfield pointer (or any other erased-element skipping mechanism) to check the erased/non-erased status of the element in question.
The reference implementation uses overaligned (std::aligned_storage) pointers in iterators, and bit_cast's to the relevant pointer type upon dereferencing, which gets around the C++ standard's concern with reading the value of pointers to erased elements (the pointer comparisons used in this function are between the overaligned pointers, which, while they point to the same memory space, critically do not point to the same type as the actual element which has been constructed/destructed there). I would expect any working implementation to do the same thing (support overaligned types and/or use a different pointer type in order to accomodate the free list mechanisms).
The same criteria for checking for erased elements in get_iterator also applies here.
void shrink_to_fit();
A decision had to be made as to whether this function should, in the context of hive, be allowed to reallocate elements (as std::vector does) or simply trim off unused memory blocks (as std::deque does). Due to the fact that a large hive memory block could have as few as one remaining element after a series of erasures, it makes little sense to only trim unused blocks, and instead a shrink_to_fit is expected to reallocate all non-erased elements to as few memory blocks as possible in order to increase cache locality during iteration and reduce memory use. As with reshape(), the order of elements post-reshape is not guaranteed to be stable, to allow for potential optimizations.
void trim_capacity();
void trim_capacity(size_type n);
The trim_capacity() command was also introduced as a way to free unused memory blocks
which have been previously reserved or transferred from active use to inactive use eg. via erase(), without reallocating elements and
invalidating iterators. The second overload was introduced as a way of allowing the user to say "I want to retain at least n capacity while freeing unused blocks, so that I have room for future insertions without having to allocate again". The specific semantics of the function mean the user doesn't have to know how much unused capacity is actually in (a) unused element memory space at the back of the back block, (b) unused element memory space from prior erasures, or (c) in unused blocks. They just say how much they want to retain, and the implementation will free the remainder (capacity() - n) via deallocating unused blocks if (a) unused blocks exist and (b) they are smaller than the remainder. It is not required to reduce capacity() if this is not the case.
void sort();
It is foreseen that although the container has unordered insertion, there may be circumstances where sorting is desired. Because hive uses bidirectional iterators, using std::sort or similar is not possible. Therefore an internal sort routine is warranted, as it is with std::list. An implementation of the sort routine used in the reference implementation of hive can be found in a non-container-specific form at plflib.org/indiesort.htm - see that page for the technique's advantages over the usual sort algorithms for non-random-access containers. Unfortunately to date there has been no interest in including this algorithm in the standard library. An allowance is made for sort to allocate memory if necessary, so that algorithms such as indiesort can be used internally.
void unique();
template <class BinaryPredicate>
size_type unique(BinaryPredicate binary_pred);
Likewise, if a container can be sorted, unique may be of use post-sort. In this case optimal implementation of unique involves calling the range-erase function where possible, as range-erase has potentially constant time depending on the scenario, as opposed to calling single-element erase repeatedly.
void splice(hive &x);
void splice(hive &&x);
Whether x's blocks are transferred to the beginning or
end of *this's iterative sequence, or interlaced in some way (for example, to preserve relative capacity growth-factor ordering of subsequent blocks) is implementation-defined. Better
performance may be gained in some cases by allowing the source blocks
to go to the front rather than the back, depending on how full the
final block in x's iterative sequence is. This is because
unused elements that are not at the back of hive's iterative sequence
will need to be marked as skipped, and skipping over large numbers of
elements will incur a small performance disadvantage during iteration
compared to skipping over a small number of elements, due to memory
locality.
This function is not noexcept for three reasons - the first is that a length_error exception may be thrown if any of the capacities of the source x's blocks are outside of the range defined by the destination's (*this) minimum and maximum block capacity limits. Second is that an exception may be thrown if the allocators of the two hives are different. Third is that in the case of an implementation using a linked list of group structs (ala the reference implementation) transferring blocks involves no allocation, however in the case of an implementation using a vector of pointers to blocks, an additional allocation may have to be made if the group pointer vector isn't of sufficient capacity to accomodate pointers to the spliced blocks from the source.
Time complexity is a complex issue here - again, for a vector-of-pointers-to-blocks implementation, we need to allow for potentially needing to expand the capacity of the vector and copying both destination and source pointers into it, hence the time complexity is linear in the number of source and destination blocks. In terms of the reference implementation the time complexity is at best constant, at worst linear in the number of source and destination blocks.
Lastly, reserved (unused) memory blocks from the source are not transferred into the destination. They are retained in the source.
resize() (all variants)This is a conscious choice to avoid confusing the user, as insertion location into a hive is undefined. In the case of hive, resizing would not necessarily insert new elements to the back of the container, when the supplied size was larger than the existing size(). New elements could be inserted into erased elements memory locations. This also means the initialization of those non-contiguous elements (if they are POD types) cannot be optimized by use of memset. This removes the main performance reason to allow for resize(). The lack of ability to specify the location of insertion removes the "ease of developer use" reason to include resize().
In practical application the reference implementation is generally faster for insertion and (non-back) erasure than current standard library containers, and generally faster for iteration than any container except vector and deque. For full details, see benchmarks.
Suggested location of hive in the standard is Sequence Containers.
#define __cpp_lib_hive <editor supplied value> // also in <hive>
| Subclause | Header |
| Requirements | |
| Sequence containers | <array>, <deque>, <forward_list>, <list>, <vector>, <hive> |
| Associative containers | <map>, <set> |
| Unordered associative containers | <unordered_map>, <unordered_set> |
| Container adaptors | <queue>, <stack> |
| Views | <span> |
Despite the cute poem, section 2 is removed because the note is inaccurate, misleading and over-simplified. See Appendix J for a more complete basic guide to container selection. Such a guide is too large to fit in the standard and will be subject to changes in architecture in terms of usefulness. The note above conflates time complexity and performance, and oddly recommends vector as a default without mentioning its time complexity, unlike the other containers. Time complexity's relevance to both performance and latency is situational and subject to architectural differences. If the committee chose to re-include such a note, it should simply describe time complexity, not make recommendations.
<hive> synopsis [hive.syn]
#include <initializer_list> // see [initializer.list.syn]
#include <compare> // see [compare.syn]
namespace std {
// class template hive
struct hive_limits;
template <class T, class Allocator = allocator<T>> class hive;
template<class T, class Allocator>
void swap(hive<T, Allocator>& x, hive<T, Allocator>& y)
noexcept(noexcept(x.swap(y)));
template<class T, class Allocator, class U>
typename hive<T, Allocator>::size_type
erase(hive<T, Allocator>& c, const U& value);
template<class T, class Allocator, class Predicate>
typename hive<T, Allocator>::size_type
erase_if(hive<T, Allocator>& c, Predicate pred);
namespace pmr {
template <class T>
using hive = std::hive<T, polymorphic_allocator<T>>;
}
}
hive [hive]hive overview [hive.overview]reshape, and they are copied between hives during copy construction, move construction, operator = (hive &&) and swap. Outside of these functions limits are guaranteed not to change.erase or clear - end example] without being deallocated. Other memory blocks can be allocated without becoming part of the iterative sequence [Example: by reserve - end example]. These are both referred to as reserved blocks. Blocks which form part of the iterative sequence of the container are referred to as active blocks.==, != and <=>. A hive also meets the requirements of a reversible container ([container.rev.reqmts]), of an
allocator-aware container ([container.alloc.reqmts]), and some of the requirements of a sequence container, including several of the optional sequence container requirements ([sequence.reqmts]). Descriptions are provided here only for operations on hive that are not described in that table or for operations where there is additional semantic information.namespace std {
struct hive_limits
{
size_t min;
size_t max;
constexpr hive_limits(size_t minimum, size_t maximum) noexcept : min(minimum), max(maximum) {}
};
template <class T, class Allocator = allocator<T>>
class hive {
private:
hive_limits current-limits = implementation-defined; // exposition only
public:
// types
using value_type = T;
using allocator_type = Allocator;
using pointer = typename allocator_traits<Allocator>::pointer;
using const_pointer = typename allocator_traits<Allocator>::const_pointer;
using reference = value_type&;
using const_reference = const value_type&;
using size_type = implementation-defined; // see [container.requirements]
using difference_type = implementation-defined; // see [container.requirements]
using iterator = implementation-defined; // see [container.requirements]
using const_iterator = implementation-defined; // see [container.requirements]
using reverse_iterator = std::reverse_iterator<iterator>; // see [container.requirements]
using const_reverse_iterator = std::reverse_iterator<const_iterator>; // see [container.requirements]
constexpr hive() noexcept(noexcept(Allocator())) : hive(Allocator()) { }
explicit hive(const Allocator&) noexcept;
explicit hive(hive_limits block_limits) noexcept(noexcept(Allocator())) : hive(block_limits, Allocator()) { }
hive(hive_limits block_limits, const Allocator&) noexcept;
explicit hive(size_type n, const Allocator& = Allocator());
hive(size_type n, hive_limits block_limits, const Allocator& = Allocator());
hive(size_type n, const T& value, const Allocator& = Allocator());
hive(size_type n, const T& value, hive_limits block_limits, const Allocator& = Allocator());
template<class InputIterator>
hive(InputIterator first, InputIterator last, const Allocator& = Allocator());
template<class InputIterator>
hive(InputIterator first, InputIterator last, hive_limits block_limits, const Allocator& = Allocator());
template<container-compatible-range<T> R>
hive(from_range_t, R&& rg, const Allocator& = Allocator());
template<container-compatible-range<T> R>
hive(from_range_t, R&& rg, hive_limits block_limits, const Allocator& = Allocator());
hive(const hive& x);
hive(hive&&) noexcept;
hive(const hive&, const type_identity_t<Allocator>&);
hive(hive&&, const type_identity_t<Allocator>&);
hive(initializer_list<T> il, const Allocator& = Allocator());
hive(initializer_list<T> il, hive_limits block_limits, const Allocator& = Allocator());
~hive();
hive& operator=(const hive& x);
hive& operator=(hive&& x) noexcept(allocator_traits<Allocator>::propagate_on_container_move_assignment::value || allocator_traits<Allocator>::is_always_equal::value);
hive& operator=(initializer_list<T>);
template<class InputIterator>
void assign(InputIterator first, InputIterator last);
template<container-compatible-range <T> R>
void assign_range(R&& rg);
void assign(size_type n, const T& t);
void assign(initializer_list<T>);
allocator_type get_allocator() const noexcept;
// iterators
iterator begin() noexcept;
const_iterator begin() const noexcept;
iterator end() noexcept;
const_iterator end() const noexcept;
reverse_iterator rbegin() noexcept;
const_reverse_iterator rbegin() const noexcept;
reverse_iterator rend() noexcept;
const_reverse_iterator rend() const noexcept;
const_iterator cbegin() const noexcept;
const_iterator cend() const noexcept;
const_reverse_iterator crbegin() const noexcept;
const_reverse_iterator crend() const noexcept;
// capacity
[[nodiscard]] bool empty() const noexcept;
size_type size() const noexcept;
size_type max_size() const noexcept;
size_type capacity() const noexcept;
void reserve(size_type n);
void shrink_to_fit();
void trim_capacity() noexcept;
void trim_capacity(size_type n) noexcept;
// modifiers
template <class... Args> iterator emplace(Args&&... args);
iterator insert(const T& x);
iterator insert(T&& x);
void insert(size_type n, const T& x);
template<class InputIterator>
void insert(InputIterator first, InputIterator last);
template<container-compatible-range <T> R>
void insert_range(R&& rg);
void insert(initializer_list<T> il);
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
void swap(hive&) noexcept(allocator_traits<Allocator>::propagate_on_container_swap::value || allocator_traits<Allocator>::is_always_equal::value);
void clear() noexcept;
// hive operations
void splice(hive& x);
void splice(hive&& x);
size_type unique();
template<class BinaryPredicate>
size_type unique(BinaryPredicate binary_pred);
hive_limits block_capacity_limits() const noexcept;
static constexpr hive_limits block_capacity_hard_limits();
void reshape(hive_limits block_limits);
iterator get_iterator(const_pointer p) noexcept;
const_iterator get_iterator(const_pointer p) const noexcept;
bool is_active(const_iterator it) const noexcept;
void sort();
template <class Compare> void sort(Compare comp);
}
template<class InputIterator, class Allocator = allocator<iter-value-type <InputIterator>>
hive(InputIterator, InputIterator, Allocator = Allocator())
-> hive<iter-value-type <InputIterator>, Allocator>;
template<class InputIterator, class Allocator = allocator<iter-value-type <InputIterator>>
hive(InputIterator, InputIterator, hive_limits block_limits, Allocator = Allocator())
-> hive<iter-value-type <InputIterator>, block_limits, Allocator>;
template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
hive(from_range_t, R&&, Allocator = Allocator())
-> hive<ranges::range_value_t<R>, Allocator>;
template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
hive(from_range_t, R&&, hive_limits block_limits, Allocator = Allocator())
-> hive<ranges::range_value_t<R>, block_limits, Allocator>;
}
An incomplete type T may be used when instantiating hive if the allocator meets the allocator completeness requirements ([allocator.requirements.completeness]). T shall be complete before any member of the resulting specialization of hive is referenced.
explicit hive(const Allocator&) noexcept;
hive(hive_limits block_limits, const Allocator&) noexcept;
current-limits with block_limits.
explicit hive(size_type n, const Allocator& = Allocator());
hive(size_type n, hive_limits block_limits, const Allocator& = Allocator());
T is Cpp17DefaultInsertable into
hive.n default-inserted elements, using
the specified allocator. If the second overload is called, also initializes current-limits with block_limits.(n / current-limits.max) + 1 element block allocations.
hive(size_type n, const T& value, const Allocator& = Allocator());
hive(size_type n, const T& value, hive_limits block_limits, const Allocator& = Allocator());
T is Cpp17CopyInsertable into
hive.n copies of value, using
the specified allocator. If the second overload is called, also initializes current-limits with block_limits.(n / current-limits.max) + 1 element block allocations.
template<container-compatible-range<T> R>
hive(from_range_t, R&& rg, const Allocator& = Allocator());
template<container-compatible-range<T> R>
hive(from_range_t, R&& rg, hive_limits block_limits, const Allocator& = Allocator());hive from *ranges::begin(rg).current-limits with block_limits.ranges::distance(rg). Creates at most (ranges::distance(rg) / current-limits.max) + 1 element block allocations.
hive(initializer_list<T> il, const Allocator& = Allocator());
hive(initializer_list<T> il, hive_limits block_limits, const Allocator& = Allocator());
T is Cpp17CopyInsertable into
hive.il. If the second overload is called, also initializes current-limits with block_limits.il.size(). Creates at most (il.size() / current-limits.max) + 1 element block allocations.size_type capacity() const noexcept;
void reserve(size_type n);
*this remain valid. If n <= capacity() there are no effects.(n / block_capacity_limits().max) + 1 element block allocations.length_error if n > max_size()numbered_note.capacity() >= n is true.numbered_note) uses Allocator::allocate() which may throw an appropriate exception.
void shrink_to_fit();
T is Cpp17MoveInsertable into
hive.capacity() to be closer to size().capacity(), but may reduce capacity(). It may reallocate
elements.*this. - end note]void trim_capacity() noexcept;
void trim_capacity(size_type n) noexcept;
reserve(), clear() or erase(). If such blocks are present, for the first overload capacity() is reduced. For the second overload capacity() will be reduced to no less than n, may not be reduced at all.*this are invalidated.
template <class... Args>
iterator emplace(Args&&... args);
iterator insert(const T& x);
iterator insert(T&& x);
void insert(size_type n, const T& x);
template<class InputIterator>
void insert(InputIterator first, InputIterator last);
template<container-compatible-range <T> R>
void insert_range(R&& rg);
void insert(initializer_list<T> il);T.a.insert(x) for n elements.a.insert(x) for each element in [first,last).a.insert(x) for each element in range rg.a.insert(x) for il.size() elements.
*this.iterator erase(const_iterator position);
position is located within becomes empty of non-erased elements as a result of the function call, that active block is either deallocated or transformed into a reserved block.position is located within does not become empty as a result of this function call. If it does become empty, at worst linear in the number of subsequent blocks in the iterative sequence.iterator erase(const_iterator first, const_iterator last);
*this also invalidates the past-the-end iterator. If any active blocks within the range [first, last) become empty of elements as a result of the function call, those active blocks are either deallocated or transformed into reserved blocks.[first, last) become empty of elements as a result of the function call, at worst linear in the number of subsequent blocks in the iterative sequence.void swap(hive& x) noexcept(allocator_traits<Allocator>::propagate_on_container_swap::value || allocator_traits<Allocator>::is_always_equal::value);
capacity() of
*this with that of x.void clear() noexcept;
*this. Invalidates all references, pointers, and iterators referring to the elements of *this and may invalidate the past-the-end iterator. Transforms active blocks into reserved blocks.empty() returns true.get_allocator() != x.get_allocator().void splice(hive &x);
void splice(hive &&x);
true.x into *this
and x becomes empty. Pointers and references to the moved
elements of x now refer to those same elements but as members
of *this. Iterators referring to the moved elements shall
continue to refer to their elements, but they now behave as iterators into
*this, not into x.length_error if any of x's element memory block capacities are outside of the current minimum and maximum element
memory block capacity limits of *this.get_allocator() != x.get_allocator(). Reserved blocks in x are not transferred into *this.size_type unique();
template<class BinaryPredicate>
size_type unique(BinaryPredicate binary_pred);[begin() + 1, end())
for which binary_pred(*i, *(i - 1)) is true. Invalidates only the iterators and references to the
erased elements.hive_limits block_capacity_limits() const noexcept;
current-limits.static constexpr hive_limits block_capacity_hard_limits();
min and
max members set to the implementation's hard limits.void reshape(hive_limits block_limits);T shall be Cpp17MoveInsertable into
hive.*this. If reallocation
occurs, also linear in the number of elements reallocated.*this. - end note]iterator get_iterator(const_pointer p) const noexcept;
const_iterator get_iterator(const_pointer p) const noexcept;
*this.p. If p does not point to an element in
*this, the past-the-end iterator is returned.p points to an erased element, behaviour is undefined.bool is_active(const_iterator it) const noexcept;
*this.true if and only if it points to an element in *this.void sort();
template <class Compare>
void sort(Compare comp);T shall be Cpp17MoveInsertable and Cpp17MoveAssignable into
hive. lvalues of type T are swappable.operator < or
a Compare function object. If an exception is thrown, the
order of the elements in *this is unspecified. Iterators and
references to elements may be invalidated.N log N comparisons, where N == size().bad_alloc if it fails to allocate any memory necessary for the sort process. comp may also throw.numbered_note) uses Allocator::allocate() which may throw an appropriate exception.
template<class T, class Allocator, class U>
typename hive<T, Allocator>::size_type
erase(hive<T, Allocator>& c, const U& value);return erase_if(c, [&](auto& elem) { return elem == value; });
template<class T, class Allocator, class Predicate>
typename hive<T, Allocator>::size_type
erase_if(hive<T, Allocator>& c, Predicate pred);
auto original_size = c.size();
for (auto i = c.begin(), last = c.end(); i != last; ) {
if (pred(*i)) {
i = c.erase(i);
} else {
++i;
}
}
return original_size - c.size();
Matt would like to thank: Glen Fernandes and Ion Gaztanaga for restructuring
advice, Robert Ramey for documentation advice, various Boost and SG14 members for support, critiques and corrections, Baptiste Wicht for teaching me how to construct decent benchmarks, Jonathan Wakely, Sean Middleditch, Jens Maurer (very nearly a co-author at this point really),
Patrice Roy and Guy Davidson for standards-compliance advice and critiques, support, representation at meetings and bug reports, Henry Miller for getting me to clarify why the intrusive list/free list approach to memory location reuse is the most appropriate, Ville Voutilainen and Gašper Ažman for help with the colony/hive rename paper, Ben Craig for his critique of the tech spec, that ex-Lionhead guy for annoying me enough to force me to implement the original skipfield pattern, Jon Blow for some initial advice and Mike Acton for some influence, the community at large for giving me feedback and bug reports on the reference implementation.
Also Nico Josuttis for doing such a great job in terms of explaining the general format of the structure to the committee.
Using reference implementation.
#include <iostream>
#include <numeric>
#include "plf_hive.h"
int main(int argc, char **argv)
{
plf::hive<int> i_hive;
// Insert 100 ints:
for (int i = 0; i != 100; ++i)
{
i_hive.insert(i);
}
// Erase half of them:
for (plf::hive<int>::iterator it = i_hive.begin(); it != i_hive.end(); ++it)
{
it = i_hive.erase(it);
}
std::cout << "Total: " << std::accumulate(i_hive.begin(), i_hive.end(), 0) << std::endl;
std::cin.get();
return 0;
} #include <iostream>
#include "plf_hive.h"
int main(int argc, char **argv)
{
plf::hive<int> i_hive;
plf::hive<int>::iterator it;
plf::hive<int *> p_hive;
plf::hive<int *>::iterator p_it;
// Insert 100 ints to i_hive and pointers to those ints to p_hive:
for (int i = 0; i != 100; ++i)
{
it = i_hive.insert(i);
p_hive.insert(&(*it));
}
// Erase half of the ints:
for (it = i_hive.begin(); it != i_hive.end(); ++it)
{
it = i_hive.erase(it);
}
// Erase half of the int pointers:
for (p_it = p_hive.begin(); p_it != p_hive.end(); ++p_it)
{
p_it = p_hive.erase(p_it);
}
// Total the remaining ints via the pointer hive (pointers will still be valid even after insertions and erasures):
int total = 0;
for (p_it = p_hive.begin(); p_it != p_hive.end(); ++p_it)
{
total += *(*p_it);
}
std::cout << "Total: " << total << std::endl;
if (total == 2500)
{
std::cout << "Pointers still valid!" << std::endl;
}
std::cin.get();
return 0;
} Benchmark results for the colony (hive) reference implementation under GCC on an Intel Xeon E3-1241 (Haswell) are here.
Old benchmark results for an earlier version of colony under MSVC 2015 update 3, on an Intel Xeon E3-1241 (Haswell) are here. There is no commentary for the MSVC results.
See the final appendix for a more intensive answer to this question, however for a brief overview, as mentioned, it is worthwhile for performance reasons in situations where the order of container elements is not important and:
Under these circumstances a hive will generally out-perform other std:: containers. In addition, because it never invalidates pointer references to container elements (except when the element being pointed to has been previously erased) it may make many programming tasks involving inter-relating structures in an object-oriented or modular environment much faster, and could be considered in those circumstances.
Some ideal situations to use a hive: cellular/atomic simulation, persistent octtrees/quadtrees, game entities or destructible-objects in a video game, particle physics, anywhere where objects are being created and destroyed continuously. Also, anywhere where a vector of pointers to dynamically-allocated objects or a std::list would typically end up being used in order to preserve pointer stability but where order is unimportant.
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 memory blocks in a deque is problematic (though not impossible). A deque and hive have no comparable performance characteristics except for insertion (assuming a good deque implementation). Deque erasure performance varies wildly depending on the 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.
Unlike a std::vector, a hive can be read from and inserted into at the same time (assuming different locations for read and write), however it cannot be iterated over and written to at the same time. If we look at a (non-concurrent implementation of) std::vector's thread-safe matrix to see which basic operations can occur at the same time, it reads as follows (please note push_back() is the same as insertion in this regard):
| std::vector | Insertion | Erasure | Iteration | Read |
| Insertion | No | No | No | No |
| Erasure | No | No | No | No |
| Iteration | No | No | Yes | Yes |
| Read | No | No | Yes | Yes |
In other words, multiple reads and iterations over iterators can happen simultaneously, but the potential reallocation and pointer/iterator invalidation caused by insertion/push_back and erasure means those operations cannot occur at the same time as anything else.
Hive on the other hand does not invalidate pointers/iterators to non-erased elements during insertion and erasure, resulting in the following matrix:
| hive | Insertion | Erasure | Iteration | Read |
| Insertion | No | No | No | Yes |
| Erasure | No | No | No | Mostly* |
| Iteration | No | No | Yes | Yes |
| Read | Yes | Mostly* | Yes | Yes |
* Erasures will not invalidate iterators unless the iterator points to the erased element.
In other words, reads may occur at the same time as insertions and erasures (provided that the element being erased is not the element being read), multiple reads and iterations may occur at the same time, but iterations may not occur at the same time as an erasure or insertion, as either of these may change the state of the skipfield which is being iterated over, if a skipfield is used in the implementation. Note that iterators pointing to end() may be invalidated by insertion.
So, hive could be considered more inherently thread-safe than a (non-concurrent implementation of) std::vector, but still has some areas which would require mutexes or atomics to navigate in a multithreaded environment.
Because erased-element memory locations may be reused by
insert() and emplace(), insertion position is
essentially random unless no erasures have been made, or an equal number of
erasures and insertions have been made.
Though I am happy to be proven wrong I suspect hives/colonies/bucket arrays are their own abstract data type. Some have suggested its ADT is of type bag, I would somewhat dispute this as it does not have typical bag functionality such as searching based on value (you can use std::find but it's o(n)) and adding this functionality would slow down other performance characteristics. Multisets/bags are also not sortable (by means other than automatically by key value). hive does not utilize key values, is sortable, and does not provide the sort of functionality frequently associated with a bag (e.g. counting the number of times a specific value occurs).
Two reasons:
++
and -- iterator operations become undefined in terms of
time complexity, making them non-compliant with the C++ standard. At
the moment they are O(1) amortized, in the reference implementation this constitutes typically one update for both
skipfield and element pointers, but two if a skipfield jump takes the
iterator beyond the bounds of the current block and into the next
block. But if empty blocks are allowed, there could be anywhere between
1 and block_capacity_limits().max empty
blocks between the current element and the next. Essentially you get
the same scenario as you do when iterating over a boolean skipfield. It
would be possible to move these to the back of the hive as trailing
blocks, or house them in a separate list or vector for future usage,
but this may create performance issues if any of the blocks are not at
their maximum size (see below).In my view the default scenario, for reasons of predictability and memory use, should be to free the memory block in most cases. But future implementations may find better strategies, somehow, and it is best not to overly constraint potential implementation. For the reasons described in the design decisions section on erase(), retaining the back block at least has performance and latency benefits, in the current implementation. Therefore retaining no memory blocks is non-optimal in cases where the user is not using a custom allocator. Meanwhile, retaining All memory blocks is bad for performance as many small memory blocks will be retained, which decreases iterative performance due to lower cache locality. However, one perspective is that if a scenario calls for retaining All memory blocks, this should be left to an allocator to manage. This is an open topic for discussion.
The user must obtain the block capacity hard limits of the implementation (via block_capacity_hard_limits()) prior to supplying their own limits as part of a constructor or reshape(), so that they do not trigger undefined behaviour by supplying limits which are outside of the hard limits. Hence it was not perceived by LEWG that there would be a reason for a hive_limits struct to ever be used with non-user-supplied values eg. zero.
There are 'hard' capacity limits, 'default' capacity limits and user-defined capacity limits. Default limits (what a hive is instantiated with if user-defined capacity limits are not supplied) and user-defined limits are not allowed to go outside of an implementation's hard limits. Newly-allocated blocks also have a non-1 implementation-defined growth factor.
While implementations are free to chose their own limits and strategies here, in the reference implementation memory block sizes start from either the dynamically-defined default minimum size (8 elements, larger if the type stored is small) or an amount defined by the end user (with a minimum of 3 elements, as there is enough metadata per-block that less than 3 elements is generally a waste of memory unless the element type is extremely large).
Subsequent block sizes then increase the total capacity of the hive by a factor of 2 (so, 1st block 8 elements, 2nd 8 elements, 3rd 16 elements, 4th 32 elements etcetera) until the current maximum block size is reached. The default maximum block size in the reference implementation is 255 (if the type sizeof is < 10 bytes) or 8192, based on multiple benchmark comparisons between different maximum block capacities, with different sized types. For larger-than-10-byte types the skipfield bitdepth is (at least) 16 so the maximum capacity 'hard' limit would be 65535 elements in that context, for < 10-byte types the skipfield bitdepth is (at least) 8, making the maximum capacity hard limit 255.
No and yes. Yes if you're careful, no if you're not.
On platforms which support scatter and gather operations via hardware (e.g.
AVX512) you can use hive with SIMD as much as you want, using gather to
load elements from disparate or sequential locations, directly into a SIMD
register, in parallel. Then use scatter to push the post-SIMD-process
values elsewhere after. On platforms which do not support this in hardware,
you would need to manually implement a scalar gather-and-scatter operation
which may be significantly slower.
In situations where gather and scatter operations are too expensive, which require elements to be contiguous in memory for SIMD processing, this is more complicated. When you have a bunch of erasures in a hive, there's no guarantee that your objects will be contiguous in memory, even though they are sequential during iteration. Some of them may also be in different memory blocks to each other. In these situations if you want to use SIMD with hive, you must do the following:
Generally if you want to use SIMD without gather/scatter, it's probably preferable to use a vector or an array.
Since this is a container where insertion position is unspecified, situations such as the following may occur:
hive<int> t = {1, 2, 3, 4, 5}, t2 = {6, 1, 2, 3, 4};
t2.erase(t2.begin());
t2.insert(5);
In this case it is implementation-defined as to whether or not t == t2, if the == operator is order-sensitive.
If the == operator is order-insensitive, there is only one reasonable way to compare the two containers, which is with is_permutation. is_permutation has a worst-case time complexity of o(n2), which, while in keeping with how other unordered containers are implemented, was considered to be out of place for hive, which is a container where performance and consistent latency are a focus and most operations are O(1) as a result. While there are order-insensitive comparison operations which can be done in o(n log n) time, these allocate, which again was considered inappropriate for a == operator. Those operations may become the subject of a future paper.
In light of all of this the bulk of SG14 and LEWG considered it more appropriate to remove the ==, != and <=> operators entirely, as these were unlikely to be used significantly with hive anyway. This gives the user the option of using is_permutation if they want an order-insensitive comparison, or std::equal if they want an order-sensitive comparison. In either case, this removes ambiguity about what kind of operation they are expecting, and the time complexity associated with that operation.
insert, emplace, reshape, splice and operator = (where *this is destination).
This was a convenience function to allow programmers to find current container memory usage without using a debugger or profiler, however this was considered out of keeping with current standard practice ie. unordered_map also uses a lot of additional memory but we don't provide such a function. In addition, the context where it would've been useful in realtime ie. determining whether or not it's worth calling trim_capacity(), is better approached by comparing size() to capacity() (although this is not foolproof either since this doesn't tell us anything about whether the empty capacity is in empty blocks or between elements).
This was a hint to the implementation to prioritize for lowered memory usage or performance specifically. In the reference implementation this told the container which skipfield type to use (smaller types limited block sizes due to the constraints of the jump-counting skipfield pattern). In other implementations this could've taken the form of using a bitfield with jump-counting information pushed into the erased element memory space, for the memory usage priority. However, prior to a particular LEWG meeting there had not been sufficient benchmarking and memory testing done on this - all benchmarking had been done at an earlier time without checking memory usage.
When more thorough benchmarking including memory measurements were done it was found that the vast bulk of unnecessary memory usage came from erased elements in hive when an element memory block is not yet empty (and therefore freed to the OS or retained depending on implementation), rather than the skipfield type itself. This meant that assuming a randomised erasure pattern, smaller block capacities had far more to do with how much memory was wasted than the skipfield type, as they were more likely to be freed than larger ones. And block capacities could already be specified by the user. Further, the better performance in some benchmarks was primarily related to this fact - reusing erased element memory space in existing blocks was much faster than having to deallocate/reserve blocks and subsequently allocate/unreserve new blocks.
The only caveat to this was when using low sizeof types such as scalars, where the additional memory from the skipfield (proportional to the type sizeof) was significant, and this use-case can be worked around at compile-type by switching to a smaller skipfield type (or bitfield as described) based on sizeof(type), either using concepts and overloads or another mechanism. I personally think the priority parameter would've also been useful for a number of other compile-time decision processes, such as deciding what block retention strategy to use when erasing and a block becomes empty of elements. Also, having a priority tag gave the ability to specify new priority values in future as part of the standard, potentially allowing for new and better changes without breaking ABI in implementations.
These are useful for several reasons:
Primarily to allow for implementation improvement. While the reference implementation uses a mechanism that is O(1), it is possible that someone in future could come up with a mechanism that was not O(1), but still out-performed the reference implementation's mechanism substantially and was never slower. In that case we would want to switch to that mechanism. Further, since the effects of time complexity on implementation performance are both constrained by hardware and software, it's relevance is situation-dependent. But it's relevance to, for example, reallocation of elements is more reliably understood in this context, as this can be calculated based on sizeof(value_type), whereas the erased-element skipping mechanism could take many forms.
The same logic applies for the erased-element recording mechanism.
Two reasons, one is that a new block may have to be allocated or transferred from the reserved blocks if all active blocks are full. Second reason is that (at least in the current reference implementation at time of writing) in the event of a block allocation or transfer there is an update of block numbers which may occur if the last current active block has a group number == std::numeric_limits<size_type>::max(). The occurence of this event is 1 in every std::numeric_limits<size_type>::max() block allocations/transfers. It updates the group numbers in every active block. The number of active blocks at this point could be small or large.
In addition, if a hive were implemented as a vector of pointers to groups, rather than a linked list of groups, this would also necessitate amortized time complexity as when the vector became full, all group pointers would need to be reallocated to a new memory block.
Hence O(1) amortized.
See paper number 2332R0.
As noted the container was originally designed for highly object-oriented situations where you have many elements in different containers linking to many other elements in other containers. This linking can be done with pointers or iterators in hive (insert returns an iterator which can be dereferenced to get a pointer, pointers can be converted into iterators with the supplied functions (for erase etc)) and because pointers/iterators stay stable regardless of insertion/erasure, this usage is unproblematic. You could say the pointer is equivalent to a key in this case (but without the overhead). That is the first access pattern, the second is straight iteration over the container, as you say. Secondly, the container does have (typically better than O(n)) advance/next/prev implementations, so multiple elements can be skipped.
I'm not really sure how to answer this, as I don't see the resemblance, unless you count maps, vectors etc as being allocators also. The only aspect of it which resembles what an allocator might do, is the memory re-use mechanism. It would be impossible for an allocator to perform a similar function while still allowing the container to iterate over the data linearly in memory, preserving locality, in the manner described in this document.
This is true for many/most AAA game companies who are on the bleeding edge, but they also do this for vector etc, so they aren't the target audience of std:: for the most part; sub-AAA game companies are more likely to use third party/pre-existing tools. As mentioned earlier, this structure (bucket-array-like) crops up in many, many fields, not just game dev. So the target audience is probably everyone other than AAA gaming, but even then, it facilitates communication across fields and companies as to this type of container, giving it a standardized name and understanding.
The only current analysis has been around the question of whether it's possible for this specification to fail to allow for a better implementation in future. This is unlikely given the container's requirements and how this impacts on implementation. Bucket arrays have been around since the 1990s, there's been no significant innovation in them until now. I've been researching/working on hive since early 2015, and while I can't say for sure that a better implementation might not be possible, I am confident that no change should be necessary to the specification to allow for future implementations, if it is done correctly. This's in part because of the C++ container requirements and how these constrain implementation.
The requirement of allowing no reallocations upon insertion or erasure, truncates possible implementation strategies significantly. Memory blocks have to be independently allocated so that they can be removed (when empty) without triggering reallocation of subsequent elements. There's limited numbers of ways to do that and keep track of the memory blocks at the same time. Erased element locations must be recorded (for future re-use by insertion) in a way that doesn't create allocations upon erasure, and there's limited numbers of ways to do this also. Multiple consecutive erased elements have to be skipped in O(1) time in order for the iterator to meet the C++ iterator O(1) function requirement, and again there's limits to how many ways you can do that. That covers the three core aspects upon which this specification is based. See Design Decisions for the various ways these aspects can be designed.
The time complexity of updates to whatever erased-element skipping mechanism is used should, I think, be left implementation-defined, as defining time complexity may obviate better solutions which are faster but are not necessarily O(1). These updates would likely occur during erasure, insertion, splicing and container copying.
UPDATE May 2022: Re-testing these assumptions, later compiler versions appear to not suffer from the issues around codegen and speed (although codegen is still very much different for versions of the container with constexpr specified for all functions). There are still however issues with compilation and I think a staggered approach to rolling out constexpr containers is still the right one, so that any potential "gotcha"s can be addressed before ABIs in the various STL flavours essentially become frozen. Original text follows.
TLDR; this may be possible in future with better understanding of constexpr container problems and advantages, presently both compiler support and programmer experience is lacking, and tests result in less performance in runtime code when constexpr is enabled on all of hives container methods. Updating at a later stage is unproblematic, and I think this is a wait-and-see scenario.
non-TLDR: I am somewhat awkwardly forced into a position where I have to question and push back slightly against the current enthusiasm around constexpr containers. At the time of writing there are no compilers which both support constexpr non-trivial destructors and also have a working implementation of a constexpr container. Until that is remedied, we won't really know what we're dealing with. My own testing in terms of making hive functions constexpr has not been encouraging. 2% performance decrease in un-altered benchmark code was common, and I suspect the common cause of this was the caching of return values from functions called at compile-time when it was cheaper to calculate them on-the-fly than to return them from main memory. This suspicion was based on the substantial increases in executable size in the constexpr versions. It is also a well-known situation in modern game development.
For an example of the latter, think about size() in std::vector. This can be calculated in most implementations by (vector.end_iterator.pointer - vector.memory_block), both of which will most likely be in cache at the time of calling size(). That's if size isn't a member variable or something. Calculating a minus operation on stuff that's already in cache is about 100x faster than making a call out to main memory for a compile-time-stored value of this function, if that is necessary. Hence calculating size() will typically be faster than storing it, but a constexpr implementation and compiler currently won't make that distinction.
None of which is an issue if a container is being entirely used within a constexpr function which has been determined to be evaluated at compile time. The problems occur when constexpr containers are used in runtime code, but certain functions such as size() are determined to be able to be evaluated at compile time, and therefore have their results cached. If there was a mechanism which specified that for a given class instance, its constexpr functions may not be evaluated at compile time, then I would give the go-ahead. Or if there were a rule which stated that a class instance's member functions may only be evaluated at compile time if the class instance is entirely instantiated and destructed at compile time, I would give the go-ahead. This does not appear to be the situation we have, as far as I can tell at the moment. If however my benchmark results above are in fact the result of compiler bugs, I will eat my words.
Time may sort these issues out, though I am personally happier for std::array and std::vector to be the "canaries in the coalmine" here.
Yes. zLib license is compatible with both GPL3 and Apache licenses (libc++/MS-STL). zLib is a more permissive license than all of these, only requiring the following:
This software is provided 'as-is', without any express or implied
warranty. In no event will the authors be held liable for any damages
arising from the use of this software.
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:
The origin of this software must not be misrepresented; you must not
claim that you wrote the original software. If you use this software
in a product, an acknowledgment in the product documentation would be
appreciated but is not required.Altered source versions must be plainly marked as such, and must not be
misrepresented as being the original software.This notice may not be removed or altered from any source distribution.Please note that "product" in this instance doesn't mean 'source code', as in a library, but a program or executable. This is made clear by line 3 which clearly differentiates source distributions from products.
In addition, high-level representatives from libc++, libstdc++ and MS-STL have stated they will either use the reference or may use it as a starting point and that licensing is unproblematic (with the exception of libc++ who stated they would need to run it past LLVM legal reps). However if in any case licensing becomes problematic as the sole author of the reference implementation I am in a position to grant use of the code under other licenses as I see fit.
It doesn't. Detecting these cases is down to the end user, as it is in deque or vector when elements are erased. In the case of hive I would recommend the use of either a generation counter or some other kind of unique ID within the element itself. The end user can build their own "handle" wrapper around a pointer or iterator which stores a copy of this ID, then compares it against the element itself upon accessing it.
In terms of guarantees that an element has not been replaced via hive usage, replacement may occur if:
Here are some more specific requirements with regards to game engines, verified by game developers within SG14:
std::vector in its default state does not meet these requirements due to:
Game developers therefore either develop custom solutions for each scenario or implement workarounds for vector. The most common workarounds are most likely the following or derivatives:
Hive brings a more generic solution to these contexts. While some developers, particularly AAA developers, will almost always develop a custom solution for specific use-cases within their engine, I believe most sub-AAA and indie developers are more likely to rely on third party solutions. Regardless, standardising the container will allow for greater cross-discipline communication.
One of the requirements of hive is that pointers to non-erased elements stay valid regardless of insertion/erasure within the container. For this reason the container must use multiple memory blocks. If a single memory block were used, like in a std::vector, reallocation of elements would occur when the container expanded (and the elements were copied to a larger memory block). Instead, hive will insert into existing memory blocks when able, and create a new memory block when all existing memory blocks are full. This keeps insertion at O(1) amortized.
If hive is structured as a vector of pointers to memory blocks instead of a linked list of memory blocks, creation of a new memory block would occasionally involve expanding the vector, itself O(n) in the number of blocks, but this is still within amortized limits since it is only occasional.
Multiple insertions may allow an implementation to reserve suitably-sized memory blocks in advance, reducing the number of allocations necessary (whereas singular insertion would generally follow the implementation's block growth pattern, possibly allocating more than necessary). However when it comes to time complexity it has no advantages over singular insertion, is linear to the number elements inserted.
Erasure is a simple matter of destructing the element in question and updating whatever data is associated with the erased-element skipping mechanism eg. the skipfield. Since we use a skipping mechanism to avoid erasures during iterator, no reallocation of subsequent elements is necessary and the process is O(1). Additionally, when using a Low-complexity jump-counting pattern the skipfield update is also always O(1).
Note: When a memory block becomes empty of non-erased elements it must be freed to the OS (or reserved for future insertions, depending on implementation) and removed from the hive's sequence of memory blocks. It it was not, we would end up with non-O(1) iteration, since there would be no way to predict how many empty memory blocks there would be between the current memory block being iterated over, and the next memory block with non-erased (active) elements in it.
In this case, where the element is non-trivially destructible, the time complexity is O(N), with infrequent deallocation necessary from the removal of an empty memory block as noted above. However where the elements are trivially-destructible, if the range spans an entire memory block at any point, that block and its metadata can simply be removed without doing any individual writes to its metadata or individual destruction of elements, potentially making this a O(1) operation.
In addition (when dealing with trivially-destructible types) for those memory blocks where only a portion of elements are erased by the range, if no prior erasures have occurred in that memory block you may be able to erase that range in O(1) time, as, for example, if you are using a skipfield there will be no need to check the skipfield within the range for previously erased elements. The reason you would need to check for previously erased elements within that portion's range is so you can update the metadata for that memory block to accurately reflect how many non-erased elements remain within the block. The non-erased element-count metadata is necessary because there is no other way to ascertain when a memory block is empty of non-erased elements, and hence needs to be removed from the hive's iteration sequence. The reasoning for why empty memory blocks must be removed is included in the Erase(single) section, above.
However in most cases the erase range will not perfectly match the size of all memory blocks, and with typical usage of a hive there is usually some prior erasures in most memory blocks. So, for example, when dealing with a hive of a trivially-destructible type, you might end up with a tail portion of the first memory block in the erasure range being erased in O(N) time, the second and intermediary memory block being completely erased and freed in O(1) time, and only a small front portion of the third and final memory block in the range being erased in O(N) time. Hence the time complexity for trivially-destructible elements is between O(1) and O(N) depending on the start and end of the erasure range.
This relies on basic iteration so is O(N).
Hive only does full-container splicing, not partial-container splicing (use range-insert with std::make_move_iterator to achieve the latter, albeit with the loss of pointer validity to the moved range). When splicing, the memory blocks from the source hive are transferred to the destination hive without processing the individual elements. These blocks may either be placed at the front of the hive or the end, depending on how full the source back block is compared to the destination back block. If the destination back block is more full ie. there is less unused space in it, it is better to put it at the beginning of the source block - as otherwise this creates a larger gap to skip during iteration which in turn affects cache locality. If there are unused element memory spaces at the back of the destination container (ie. the final memory block is not full) and a skipfield is used, the skipfield nodes corresponding to those empty spaces must be altered to indicate that these are skipped elements.
In the reference implementation splice is only O(n) if the user is using user-defined block capacity limits, and these limits differ significantly between the source hive and destination hive. However in the event that hive is implemented structurally as a vector of pointers to element blocks + metadata, splice will always be O(n) in the number of memory blocks due to the need to copy the block pointers to the destination hive.
Generally the time complexity is O(1), and if a skipfield is used it must allow for O(1) skipping of multiple erased elements. However every so often iteration will involve a transistion to the next/previous memory block in the hive's sequence of blocks, depending on whether we are doing ++ or --. At this point a read of the next/previous memory block's corresponding skipfield would be necessary, in case the front/back element(s) in that memory block are erased and hence skipped. So for every block transition, 2 reads of the skipfield are necessary instead of 1. Hence the time complexity is O(1) amortized.
If skipfields are used they must be per-element-memory-block and independent of subsequent/previous memory blocks, as otherwise you end up with a vector for a skipfield, which would need a range reallocated every time a memory block was removed from the hive (see notes under Erase, above), and reallocation to a larger skipfield memory block when a hive expanded. For both of these procedures you could have thousands of skipfield nodes needing to be reallocated based on a single erasure (from within a memory block which only had one non-erased element left and hence would need to be removed from the hive). This is unacceptable latency for any field involving high timing sensitivity (all of SG14).
For most implementation these should generally be stored as member variables and so returning them is O(1).
The reasoning for this is similar to that of Erase(multiple), above.
Complexity is dependent on state of hive, position of iterator and length of
distance, but in many cases will be less than linear. It is
necessary in a hive to store metadata both about the capacity of each block
(for the purpose of iteration) and how many non-erased elements are present
within the block (for the purpose of removing blocks from the iterative chain
once they become empty). For this reason, intermediary blocks between the
iterator's initial block and its final destination block (if these are not the
same block, and if the initial block and final block are not immediately
adjacent) can be skipped rather than iterated linearly across, by subtracting
the "number of non-erased elements" metadata from distance for
those blocks.
This means that the only linear time operations are any iterations within the initial block and the final block. However if either the initial or final block have no erased elements (as determined by comparing whether the block's capacity metadata and the block's "number of non-erased elements" metadata are equal), linear iteration can be skipped for that block and pointer/index math used instead to determine distances, reducing complexity to constant time. Hence the best case for this operation is constant time, the worst is linear to the distance.
The same considerations which apply to advance, prev and next also apply to distance - intermediary blocks between iterator1 and iterator2's blocks can be skipped in constant time, if they exist. iterator1's block and iterator2's block (if these are not the same block) must be linearly iterated across using ++ unless either block has no erased elements, in which case the operation becomes pointer/index math and is reduced to constant time for that block. In addition, if iterator1's block is not the same as iterator2's block, and iterator2 is equal to end() or (end() - 1), or is the last element in that block, iterator2's block's elements can also counted from the metadata rather than iteration.
This proposal and its reference implementation and the original reference implementation have several key differences, one is that the original is named 'colony', for historical and userbase reasons. Other differences follow:
"I'm the lead of the Editors team at Creative Assembly, where we make tools for the Total War series of games. The last game we released was Three Kingdoms, currently doing quite well on Steam. The main tool that I work on is the map creation editor, kind of our equivalent of Unreal Editor, so it's a big tool in terms of code size and complexity.
The way we are storing and rendering entities in the tool currently is very inefficient: essentially we have a quadtree which stores pointers to the entities, we query that quadtree to get a list of pointers to entities that are in the frustum, then we iterate through that list calling a virtual draw() function on each entity. Each part of that process is very cache-unfriendly: the quadtree itself is a cache-unfriendly structure, with nodes allocated on the heap, and the entities themselves are all over the place in memory, with a virtual function call on top.
So, I have made a new container class in which to store the renderable versions of the entities, and this class has a bunch of colonies inside, one for each type of 'renderable'. On top of this, instead of a quadtree, I now have a virtual quadtree. So each renderable contains the index of the quadtree node that it lives inside. Then, instead of asking the quadtree what entities are in the frustum, I ask the virtual quadtree for a node mask of the nodes what are in the frustum, which is just a bit mask. So when rendering, I iterate through all the renderables and just test the relevant bit of the node mask to see if the renderable is in the frustum. (Or more accurately, to see if the renderable has the potential to be in the frustum.) Nice and cache friendly.
When one adds an entity to the container, it returns a handle, which is just a pointer to the object inside one of the colonies returned as a std::uintptr_t. So I need this to remain valid until the object is removed, which is the other reason to use a colony."
"I implemented a standalone open source project for the thread liveness monitor: https://github.com/shuvalov-mdb/thread-liveness-monitor. Also, I've made a video demo of the project: https://youtu.be/uz3uENpjRfA
The benchmarks are in the doc, and as expected the plf::colony was extremely fast. I do not think it's possible to replace it with any standard container without significant performance loss. Hopefully, this version will be very close to what we will put into the MongoDB codebase when this project is scheduled."
"I'm using it as backing storage for a volumetric data structure (like openvdb). Its sparse so each tile is a 512^3 array of float voxels.
I thought that having colony will allow me to merge multiple grids together more efficiently as we can just splice the tiles and not copy or reallocate where the tiles dont overlap. Also adding and removing tiles will be fast. Its kind of like using an arena allocator or memory pool without having to actually write one."
Note: this is a private project Daniel is working on, not one for Weta Digital.
"Internally we use it as a slab allocator for objects with very different lifetime durations where we want aggressive hot memory reuse. It lets us ensure the algorithms are correct after the fact by being able to iterate over the container and verify what's alive.
It's a great single-type memory pool, basically, and it allows iteration for debugging purposes :)
Where it falls slightly short of expectation is having to iterate/delete/insert under a lock for multithreaded operation - for those usecases we had to do something different and lock-free, but for single-threaded applications it's amazing."
Guides and flowcharts I've seen online have either been performance-agnostic or incorrect. This is not a perfect guide, nor is it designed to suit all participants, but it should be largely correct in terms of it's focus. Note, this guide does not cover:
These are broad strokes and can be treated as such. Specific situations with specific processors and specific access patterns may yield different results. There may be bugs or missing information. The strong insistence on arrays/vectors where-possible is to do with code simplicity, ease of debugging, and performance via cache locality. I am purposefully avoiding any discussion of the virtues/problems of C-style arrays vs std::array or vector here, for reasons of brevity. The relevance of all assumptions are subject to architecture. The benchmarks this guide is based upon are available here, here. Some of the map/set data is based on google's abseil library documentation.
a = yes, b = no
0. Is the number of elements you're dealing with a fixed amount? 0a. If so, is all you're doing either pointing to and/or iterating over elements? 0aa. If so, use an array (either static or dynamically-allocated). 0ab. If not, can you change your data layout or processing strategy so that pointing to and/or iterating over elements would be all you're doing? 0aba. If so, do that and goto 0aa. 0abb. If not, goto 1. 0b. If not, is all you're doing inserting-to/erasing-from the back of the container and pointing to elements and/or iterating? 0ba. If so, do you know the largest possible maximum capacity you will ever have for this container, and is the lowest possible maximum capacity not too far away from that? 0baa. If so, use vector and reserve() the highest possible maximum capacity. Or use boost::static_vector for small amounts which can be initialized on the stack. 0bab. If not, use a vector and reserve() either the lowest possible, or most common, maximum capacity. Or boost::static_vector. 0bb. If not, can you change your data layout or processing strategy so that back insertion/erasure and pointing to elements and/or iterating would be all you're doing? 0bba. If so, do that and goto 0ba. 0bbb. If not, goto 1. 1. Is the use of the container stack-like, queue-like or ring-like? 1a. If stack-like, use plf::stack, if queue-like, use plf::queue (both are faster and configurable in terms of memory block sizes). If ring-like, use ring_span or ring_span lite. 1b. If not, goto 2. 2. Does each element need to be accessible via an identifier ie. key? ie. is the data associative. 2a. If so, is the number of elements small and the type sizeof not large? 2aa. If so, is the value of an element also the key? 2aaa. If so, just make an array or vector of elements, and sequentially-scan to lookup elements. Benchmark vs absl:: sets below. 2aab. If not, make a vector or array of key/element structs, and sequentially-scan to lookup elements based on the key. Benchmark vs absl:: maps below. 2ab. If not, do the elements need to have an order? 2aba. If so, is the value of the element also the key? 2abaa. If so, can multiple keys have the same value? 2abaaa. If so, use absl::btree_multiset. 2abaab. If not, use absl::btree_set. 2abab. If not, can multiple keys have the same value? 2ababa. If so, use absl::btree_multimap. 2ababb. If not, use absl::btree_map. 2abb. If no order needed, is the value of the element also the key? 2abba. If so, can multiple keys have the same value? 2abbaa. If so, use std::unordered_multiset or absl::btree_multiset. 2abbab. If not, is pointer stability to elements necessary? 2abbaba. If so, use absl::node_hash_set. 2abbabb. If not, use absl::flat_hash_set. 2abbb. If not, can multiple keys have the same value? 2abbba. If so, use std::unordered_multimap or absl::btree_multimap. 2abbbb. If not, is on-the-fly insertion and erasure common in your use case, as opposed to mostly lookups? 2abbbba. If so, use robin-map. 2abbbbb. If not, is pointer stability to elements necessary? 2abbbbba. If so, use absl::flat_hash_map<Key, std::unique_ptr<Value>>. Use absl::node_hash_map if pointer stability to keys is also necessary. 2abbbbbb. If not, use absl::flat_hash_map. 2b. If not, goto 3. Note: if iteration over the associative container is frequent rather than rare, try the std:: equivalents to the absl:: containers or tsl::sparse_map. Also take a look at this page of benchmark conclusions for more definitive comparisons across more use-cases and hash map implementations. 3. Are stable pointers/iterators/references to elements which remain valid after non-back insertion/erasure required, and/or is there a need to sort non-movable/copyable elements? 3a. If so, is the order of elements important and/or is there a need to sort non-movable/copyable elements? 3aa. If so, will this container often be accessed and modified by multiple threads simultaneously? 3aaa. If so, use forward_list (for its lowered side-effects when erasing and inserting). 3aab. If not, do you require range-based splicing between two or more containers (as opposed to splicing of entire containers, or splicing elements to different locations within the same container)? 3aaba. If so, use std::list. 3aabb. If not, use plf::list. 3ab. If not, use hive. 3b. If not, goto 4. 4. Is the order of elements important? 4a. If so, are you almost entirely inserting/erasing to/from the back of the container? 4aa. If so, use vector, with reserve() if the maximum capacity is known in advance. 4ab. If not, are you mostly inserting/erasing to/from the front of the container? 4aba. If so, use deque. 4abb. If not, is insertion/erasure to/from the middle of the container frequent when compared to iteration or back erasure/insertion? 4abba. If so, is it mostly erasures rather than insertions, and can the processing of multiple erasures be delayed until a later point in processing, eg. the end of a frame in a video game? 4abbaa. If so, try the vector erase_if pairing approach listed at the bottom of this guide, and benchmark against plf::list to see which one performs best. Use deque with the erase_if pairing if the number of elements is very large. 4abbab. If not, goto 3aa. 4abbb. If not, are elements large or is there a very large number of elements? 4abbba. If so, benchmark vector against plf::list, or if there is a very large number of elements benchmark deque against plf::list. 4abbbb. If not, do you often need to insert/erase to/from the front of the container? 4abbbba. If so, use deque. 4abbbbb. If not, use vector. 4b. If not, goto 5. 5. Is non-back erasure frequent compared to iteration? 5a. If so, is the non-back erasure always at the front of the container? 5aa. If so, use deque. 5ab. If not, is the type large, non-trivially copyable/movable or non-copyable/movable? 5aba. If so, use hive. 5abb. If not, is the number of elements very large? 5abba. If so, use a deque with a swap-and-pop approach (to save memory vs vector - assumes standard deque implementation of fixed block sizes) ie. when erasing, swap the element you wish to erase with the back element, then pop_back(). Benchmark vs hive. 5abbb. If not, use a vector with a swap-and-pop approach and benchmark vs hive. 5b. If not, goto 6. 6. Can non-back erasures be delayed until a later point in processing eg. the end of a video game frame? 6a. If so, is the type large or is the number of elements large? 6aa. If so, use hive. 6ab. If not, is consistent latency more important than lower average latency? 6aba. If so, use hive. 6abb. If not, try the erase_if pairing approach listed below with vector, or with deque if the number of elements is large. Benchmark this approach against hive to see which performs best. 6b. If not, use hive. Vector erase_if pairing approach: Try pairing the type with a boolean, in a vector, then marking this boolean for erasure during processing, and then use erase_if with the boolean to remove multiple elements at once at the designated later point in processing. Alternatively if there is a condition in the element itself which identifies it as needing to be erased, try using this directly with erase_if and skip the boolean pairing. If the maximum is known in advance, use vector with reserve().