Introduction

hive is a formalization, extension and optimization of what is typically known as bucket arrays in game programming circles. Similar data-structures are used in high-performance computing, high performance trading, 3D-simulation, particle simulations, robotics fields.

In a typical game engine, elements within one container often refer to elements in other separate containers. Data is heavily interlinked, iterated often(everytime a frame is rendered) and changing continuously. Most games have an Entity class. Entities link to shared resources such as texture objects, sound data etc. These shared resources are usually located in separate containers so that they can be reused by multiple entities. Entities in turn are referenced by other superstructures within a game engine, such as quadtrees / octrees, level structures and so forth.

Erasing entities or otherwise removing or deactivating objects occurs frequently in game and in realtime (for example, a wall gets destroyed and no longer is required to be processed by the game engine). Creating new objects and adding them into the gameworld on-the-fly is also common (for example, a new enemy is spawned). While this is all happening, the links between entities, shared resources and superstructures such as levels and quadtrees, must stay valid in order for the game to run.

We don’t always know in advance how many elements there will be in a container at the beginning of development, or even at the beginning of a level during playback - an example of this being MMORPG(massively multiplayer online role playing games). In a MMORPG, the number of game entities fluctuates based on how many players are playing.

If we use vector as a container to store game entities, it loses pointer validity to elements within it upon insertion, and pointer/index validity upon erasure.

We desire a container that allows constant-time insertion / erasure, fast iteration performance, yet offers pointer stability.

%load_ext itikz

Workarounds for the failings of std::vector

To meet these requirements, game developers tend to either a) develop their own custom containers or b) develop workarounds for the failings of std::vector.

Tombstone

A tombstone is just a placeholder or marker used in data structures to indicate that a piece of that has been deleted, rather than immediately erasing it. We could, thus, use a boolean flag (or similar) to indicate the inactivity of an object (as opposed to actually erasing the object from the vector). When erasing, we simply adjust the boolean flag, and when iterating, items with the boolean flag set are skipped. External elements refer to elements within the container via indexes rather than pointers. An advantage of this approach is fast erasure.

Consider the boolean skipfield accompanying an array of 10 integers of the below form:

Using boolean skipfield

This means that the 2nd, 3rd, 4th and 8th integers must be respectively skipped during the processing of the array. The pseudocode for a single iteration between two unskipped objects in a sequence of integers using a boolean skipfield could be implemented as follows.

size_t advance(size_t i){
    do{
        i += 1;
    }while(S[i])
}

Boolean skipfields come with two downsides. As you can see, branching code is necessary for every skipfield read, in order to determine whether to proces or skip an element. This large amount of branching can cause performance issues on processors with deep pipelines and poor branch prediction performance. Also, the standard library requires that a containers support \(O(1)\) constant-time ++iter iteration performance. An unpredictable number of reads from the skipfield are necessary to ascertain the next unskipped object.

Utilizing a vector (or array) of group structs

The reference implementation of hive uses a doubly linked-list of group structs. A group consists of (a) a dynamically allocated memory block (b) a dynamically-allocated skipfield and (c) memory block meta data such as size and capacity.

template<typename T>
struct group{
    skipfield_pointer_type skipfield;       // skipfield pointer
    aligned_struct_pointer_type elements;   // pointer to memory block
    size_t size;                            // meta-data
    size_t capacity;

    group* next_group;
    group* previous_group;

    // ...
};

Let’s pause to think, what if we used a vector of group structs instead of a doubly linked-list. When a group becomes empty of elements, it must be removed from the vector 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. Merely erasing the group is not sufficient, as this creates a variable amount of latency during the erasure when the group becomes empty, based on the number of groups after that group which need to be relocated backward in the vector. But, even if you swap the to-be-erased group with the back group, and then pop 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, that iterator would be invalidated.

Using a vector of pointers to group structs

With a vector of pointers to group structs, erasing group still can have high variable latency, but the process of relocating the pointers after the to-be-erased group is cheaper. Also, using the swap-and-pop idiom is still not possible, it would still invalidate an iterator pointing to an element within the back group.

Using a vector of memory blocks

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 also don’t work as it would (a) disallow a growth factor in the memory blocks and (b) invalidate pointers to the elements in subsequent blocks when a memory block became empty of elements and was therefore removed from the vector.

A method of skipping erased elements in \(O(1)\) time during iteration

Matt Bentley proposes using low-complexity jump counting(LCJC) pattern to have \(O(1)\) constant-time complexity for iterating from one unskipped element to the next one. LCJC achieves this without without branching statements, which results in better performance on many processors. Let us walk through a couple of easy examples to understand how LCJC works in practice.

Primer on LCJC

We start by establishing few definitions.

Skipfield. By a skipfield, we mean an array of integers accompanying a data-collection (memory block of elements), that is used to skip over certain elements during iteration. We denote it by \(S\).

Node. A single integer within the skip field array. For a boolean skipfield array, this is always either 0 or 1. For an LCJC skipfield, a node aka an element in the skipfield array could be any non-negative integer.

Skipblock. A contigous sequence of skipped nodes within a skipfield. In the following LCJC skipfield:

Skipblocks within a skipfield array

the nodes at 2nd, 3rd and 4th position form a skipblock. Similarly, the nodes at the 6th, 7th and 8th position form another skipblock.

Start Node. The first node in any skipblock. End Node. The last node in any skipblock. Middle Node. Any node in the skipblock which is not a start or end node.

Iteration

In a boolean skipfield, the skip is only ever of \(1\) node. If S[i] = 1 in the skipfield array, the i-th element is skipped. In the below example, during a forward iteration, each time, we increment the index i, look at the current node in the skipfield array S[i] and if it is 1 instead of 0, we skip the i-th element in the memory block and continue this process until we find an unskipped element.

Iteration using a boolean skipfield

In contrast, in an LCJC skipfield, a non-zero entry S[i] in the skipfield array S encodes the total number of elements to skipped aka jump size.

Iteration using a LCJC skipfield

In the above example, a forward iteration through the memory block will walk through the elements at indices 0, 3, 4, 5, 6, 9, which correspond to 5, 28, 10, 6, 3, 15 in the memory block. If we were to do a reverse iteration, we will walk through the elements at indices 9, 6, 5, 4, 3, 0, which correspond to the data elements 15, 3, 6, 10, 28 (the same elements as in the forward pass, but in reverse order).

The LCJC update algorithm, as you will soon discover, ensures that the forward and reverse pass is consistent. If you look carefully enough, the start and end nodes of every skipblock in an LCJC skipfield both encode the total number of elements to skip (and are equal).

In equation form, forward iteration can be expressed as follows:

\[\begin{align} i := i + 1 \end{align}\]

\[\begin{align} i := i + S[i] \end{align}\]

Similarly, iterating in the reverse can be expressed as:

\[\begin{align} i := i - 1 \end{align}\]

\[\begin{align} i := i - S[i] \end{align}\]

Changing a skipfield from unskipped to skipped

Let’s think about what we need to do, if we want to change a skipfield node from unskipped to skipped.

There are \(4\) potential outcomes in this situation:

If both left and right nodes are non-zero

This means that the current node is between two skipblocks and we must join those skipblocks together. Intuitively, the procedure for doing so must be as follows:

The left neighbour of the current node in the skipfield array is the end node of the LHS skipblock. Similarly, the right neighbour of the current node in the skipfield array is the start node of the RHS skipblock.

If we subtract S[i-1] from the current node’s index i, we reach the start node of the left skipblock. Similarly, if we S[i+1] to the current node’s index i, we reach the end node of the right skipblock.

We want to merge the left and right skipblocks into a single contiguous skipblock having length = length of the left skipblock + length of the right skipblock + 1 (current node). Thus, we set the left skipblock’s start node and the right skipblock’s end node to the value of the left node + the value of the right node + 1.

\[\begin{align} j &:= S[i-1] \\ k &:= S[i+1] \\ S[i-j] = S[i+k] &:= j + k + 1 \end{align}\]

If only the left node is non-zero

This means that the current node has an adjacent skipblock on the left, in which case, we simply add the current node to that skipblock. Intuitively, the procedure for doing so should be as follows:

If we subtract S[i-1] from the current node’s index i, we reach the start node of the left skipblock. We set the value of the left skipblock’s start node and the current node, to the left node’s value + 1.

\[\begin{align} j &:= S[i-1] \\ S[i-j] := S[i] &:= j + 1 \end{align}\]

If only the right node is non-zero

This means that the current node has an adjacent skipblock on the right. Similar, to the above logic, we can perform the following updates:

\[\begin{align} k &:= S[i+1] \\ S[i+k] := S[i] &:= k + 1 \end{align}\]

If both left and right nodes are zero

This means the node in question has no skipblocks on either side, in which case we create a new skipblock of \(1\) nodes. We simply set the value of the current node to \(1\).

\[\begin{align} S[i] := 1 \end{align}\]

Changing a skipfield from skipped to unskipped

The node to be modified is the end node of the skipblock

In this case, we truncate the skipblock to the left. Intuitively, the process is as follows -

Subtract \(1\) from the current node’s value and store that result as \(j\). It’s going to be new length of the skipblock to the left.
Subtract \(j\) from the current node’s index to find the index of the skipblock’s start node.
Set the start node of the skipblock and the node to the left of the current node (the new end node of the skipblock) to \(j\).
Set the current node to \(0\).

\[\begin{align} j &:= S[i] - 1\\ S[i-j] := S[i-1] &:= j\\ S[i] &:= 0 \end{align}\]

The node to be modified is the start node of a skipblock

Here we just truncate the skipblock to the right.

\[\begin{align} j &:= S[i] - 1\\ S[i+j] := S[i+1] &:= j \\ S[i] &:= 0 \end{align}\]

The node to be modified is both the start and end node of the skipblock

In this scenario, the current node is a \(1\)-node skipblock and can simply be set to zero.

\[ S[i] := 0 \]

The node to be modified is neither the start nor the end of a skipblock

In this scenario, the node in question is a middle node and the skipblock must be split into two skipblocks as follows:

Subtract the current node’s index from the end node’s index. This is going to be the length of the right skipblock. So, we set the value of the node to the right of the current node, and the end node, to the result.
Subtract the start node’s index from the current node’s index and set the value of the node to the left of the current node, and the start node, to the result.
Set the value of the current node to \(0\).

\[ \begin{align} S[e] := S[i+1] &:= e - i\\ S[s] := S[i-1] &:= i - s\\ S[i] &:= 0 \end{align} \]

Low-level design

The hive has a book-keeping data-structure that has the following member-fields:

a pointer unused_groups_head to the head of a singly linked-list of all reserved memory blocks created by reserve() or retained by erase()/clear().
a pointer erasure_groups_head to the head of a doubly linked-list of all memory blocks that have erased element memory locations available for re-use.
a pair of begin and end iterators. These iterators are of the type hive_iterator. The state of a hive_iterator consists of (group_pointer,element_pointer,skipfield_pointer).

Show the code

%%itikz --temp-dir --tex-packages=tikz,color --tikz-libraries=arrows.meta --implicit-standalone
\begin{tikzpicture}[scale=2.0,transform shape]
  \pagecolor{white}
  \fill[yellow!42] (0,4) rectangle (6.7,-1.84);
  \fill[lime!31] (0,3.59) rectangle (6.72,2.12);
  \fill[lime!31] (-0.01,2.12) rectangle (6.71,0.48);
  \fill[yellow!42] (-0.02,-3.27) rectangle (1.32,-4.63);
  \node[draw=none, node font=\ttfamily, minimum width=191pt, fill=teal!19] at (3.35,3.8) {hive};
  \path[draw opacity=0.85, solid] (0.53,3.69) rectangle (4.08,3.33);
  \node[draw=none, node font=\ttfamily] (node1) at (2.34,-1.52) {- erasure\_groups\_head};
  \node[draw=none, node font=\footnotesize\ttfamily, fill=lime!22, minimum width=38pt] at (0.65,-3.45) {group\_0};
  \fill[yellow!42] (4.19,-3.3) rectangle (5.53,-4.66);
  \node[draw=none, node font=\footnotesize\ttfamily, fill=lime!22, minimum width=38pt] (node3) at (4.86,-3.48) {group\_1};
  \node[draw=none, node font=\ttfamily] at (2.24,-1.22) {- unused\_groups\_head};
  \node[draw=none, node font=\ttfamily] at (2.25,-0.56) {- min\_block\_capacity};
  \node[draw=none, node font=\ttfamily] at (1.88,-0.26) {- total\_capacity};
  \node[draw=none, node font=\ttfamily] at (2.26,-0.89) {- max\_block\_capacity};
  \node[draw=none, node font=\ttfamily, minimum width=190pt, fill=green!28] at (3.35,3.35) {begin\_iterator};
  \node[draw=none, node font=\ttfamily, minimum width=190pt, fill=green!28] at (3.35,1.79) {end\_iterator};
  \node[draw=none, node font=\ttfamily] at (1.83,2.84) {- group\_pointer};
  \node[draw=none, node font=\ttfamily] at (2.01,2.5) {- element\_pointer};
  \node[draw=none, node font=\ttfamily] at (2.19,2.18) {- skipfield\_pointer};
  \node[draw=none, node font=\ttfamily] at (2.15,0.69) {- skipfield\_pointer};
  \node[draw=none, node font=\ttfamily] at (1.5,0.06) {- total\_size};
  \draw[arrows=-Latex] (1.32,-3.57) -- (4.27,-3.57);
  \draw[arrows=-Latex] (8.28,-3.95) -- (5.5,-3.95);
  \draw[arrows=-Latex] (4.15,-3.95) -- (1.23,-3.95);
  \node[draw=none, node font=\ttfamily] at (1.77,1.3) {- group\_pointer};
  \node[draw=none, node font=\ttfamily] at (1.97,0.98) {- element\_pointer};
  \draw[arrows=Circle-Latex] (4.5,-1.22) -- (8.25,-3.27);
  \draw[arrows=Circle-Latex] (node1.east) -- (4.74,-3.27);
  \fill[yellow!42] (8.28,-3.31) rectangle (9.62,-4.67);
  \node[draw=none, node font=\footnotesize\ttfamily, fill=lime!22, minimum width=38pt] (node2) at (8.95,-3.5) {group\_2};
  \draw[arrows=-Latex] (node3.east) -- (node2.west);
\end{tikzpicture}

Each group consists of:

pointers to array of elements and the skipfield array. A single allocation request is made for both the data-elements and the skip-field array for performance reasons and they reside in contigous block.
the free_list_head index number records the index(within the memory block) of the first element of the last(most recently) created skipblock - the head skipblock.
the erasures_list_next_group and erasures_list_prev_group fields of type group* are pointers to the previous and next groups in the doubly linked list of groups with active erased element free lists.

Show the code

%%itikz --temp-dir --tex-packages=tikz,color --tikz-libraries=arrows.meta --implicit-standalone
\begin{tikzpicture}[scale=2.5,transform shape]
  \pagecolor{white}
  \fill[yellow!78!brown!25] (0,2.48) rectangle (5.24,-2.27);
  \node[draw=none, node font=\ttfamily, minimum width=149pt, fill=lime!44] at (2.62,2.25) {group};
  \node[draw=none, node font=\ttfamily] (node1) at (1.2,1.68) {-skipfield};
  \node[draw=none, node font=\ttfamily] at (1.66,0.63) {-previous\_group};
  \node[draw=none, node font=\ttfamily] at (1.31,0.92) {-next\_group};
  \node[draw=none, node font=\ttfamily] (node2) at (1.11,1.34) {-elements};
  \node[draw=none, node font=\ttfamily] at (7.24,3.35) {elements};
  \node[draw=none, node font=\ttfamily] (node3) at (10.12,3.3) {skipfield\_array};
  \node[draw=none, node font=\ttfamily] at (1.62,0.31) {-free\_list\_head};
  \node[draw=none, node font=\ttfamily] at (1.1,-0.02) {-capacity};
  \node[draw=none, node font=\ttfamily] at (0.73,-0.33) {-size};
  \node[draw=none, node font=\ttfamily] at (2.54,-0.72) {-erasures\_list\_next\_group};
  \node[draw=none, node font=\ttfamily] at (1.45,-1.02) {-group\_number};
  \draw[fill=blue!54!cyan!33] (5.67,3.66) rectangle (8.67,4.37);
  \draw[fill=pink!88!yellow!97] (8.5,3.65) rectangle (11.52,4.38);
  \draw (9.25,4.37) -- (9.25,3.63);
  \draw (6.34,4.41) -- (6.34,3.67);
  \draw[arrows=Circle-Latex] (2.32,1.68) -- (6,4);
  \draw[arrows=Circle-Latex] (node2.east) -- (9,4);
  \node[draw=none, node font=\itshape] at (8.34,4.78) {contigous block allocated in a single allocation};
\end{tikzpicture}

The memory space of the first erased element in each skipblock is reinterpret_castd via pointers as two index numbers, the first giving the index of the previous skipblock in that memory block, the second giving the index of the next skipblock in the sequence.

References

Colonies, performance and why should we care, CppCon 2021, Matt Bentley.
Introduction of std::hive to the standard library, proposal, by Matt Bentley.
plf::colony documentation
Low-complexity jump counting pattern(LCJC)
High-complexity jump counting pattern(HCJC)
Bitset-stacking