Developer experiences from the trenches
Sat 27 May 2023 by Michael Labbe
tags code
Having linear pools of homogenous objects is good for performance, but eventually a piece of code will need to operate on or reserve a single object from the pool. This is a practical reality in gameplay code where things exist for a short time and interact in one-off situations.
What does freeing and allocating a single object from a preallocated pool mean? Let’s clearly establish the scenario:
It is clear to see that allocating and freeing objects from a pool needs to be quick. It happens hundreds if not thousands of times per frame. Linearly searching the list for a free pool entry is not going to yield acceptable performance.
Further, a non-intrusive solution is needed, as the entire array is commonly iterated over during processing to avoid branching and data about freed objects cannot reliably be stored in-array.
The rest of this article explains a constant-time approach to allocating and freeing from the pool.
The Swap Delete technique was first introduced to me in a GDC Canada 2010 talk titled A Dynamic Component Architecture for High Performance Gameplay. It is a talk by Insomniac’s Lead Systems Engineer, Terence Cohen. Outlined in just a few slides in a much larger talk about dynamic component systems, Swap Delete is a brilliant technique that deserves to be plucked out of his larger talk and explained in depth. Note that this technique can be used with any homogenous object pooling system, with or without a component system sitting atop.
First, let’s establish the terminology we need:
Object Pool: An array of homogenous objects.
n is a handle, pool[n] returns the nth object from the object pool. For the purpose of this article, there is no difference between a handle and an index into an array of objects.Roster Table: A table of handles. No handle is repeated, and every handle from the pool is always in the roster table. Handles are unique indexes into the object pool.
Consider this figure: The roster table‘s six values are handles, from 5 to 0. Here, roster[1] returns the handle 4, which is the fourth object in the pool.
Here, partition == 5, which points to the roster table field containing the value 0. Zero is the handle of an unallocated object from the pool.
The partition always points at the next object to allocate. It always separates the handles in the roster table from the allocated ones.
On allocation a handle for the pool object at the partition’s address is returned. The partition is then incremented by 1.
// alloc pseudocode
assert(partition < pool.length)
new_handle = roster_table[partition]
new_obj = pool[new_handle]
partition++
That takes care of constant time allocation, but what about deletion? Clearly, the partition needs to always point at the next free object in the roster table for this allocation scheme to work.
To delete a handle, swap its roster table entry for the entry just before the partition.
In this figure, pool handle 4 from roster index [1] is being deleted. It is swapped into roster index [4], because the partition is pointing at [5].
Now, simply decrement the partition, so that it points at the newly freed roster index entry.
As you can see in the final figure, the partition points at [4], which contains pool handle 4. This is the freshly deleted pool object.
Consider that the next call to alloc will correctly return pool handle 4.
// free pseudocode
roster_index_for_deletion = handle_to_roster_index(handle)
swap(roster_table[roster_index_for_deletion],
roster_table[partition - 1])
partition--
There is a necessary implementation detail that is not mentioned in Terrence Cohen’s presentation and is also not pictured in the graphics in this article.
All calling code will pass objects in by handle, not roster index. The roster table is an implementation detail of the pool.
When an object is freed, it will be passed in by handle, but the roster index is needed to perform the swap. In order to resolve a handle into a roster index, a lookup table from handle to roster index must be created. Its fields must be swapped whenever the roster table’s values are swapped. It is a reverse lookup that must be kept in sync any time the roster table is updated.
That’s it. In total, there are three arrays that must be maintained:
The roster and handle-to-roster tables are implementation details of the pool’s allocation and free functionality; the caller never interacts with them directly. The caller solely deals with handles.
It is possible that a stale handle could point to an object that used to exist but has been freed and re-allocated. This is possible because handles are reused between alloc/free events.
If heap allocated objects were used instead of a pool, stale pointers would likely crash, which is arguably preferable to stale data making its way into a running program which would subtly display strange behaviour.
Andre Weissflog wrote a thought-provoking article on using handles instead of pointers. In an update at the end of his blog post, he proposes adding a generational counter to handles. An object pooling system based on handles would do well to consider generational checks when mapping a handle into a pool, especially while debugging.
