Constant Time Array Pattern

John Meschke - January 30, 2019

Background

A very common pattern that appears during game development is the need to iterate over a list of objects and update them. Since objects can come and go in a dynamic world, we would ideally want to insert and remove these from the update list in constant time. Removing an element from an array means you then have to iterate through all following elements and shift them down a spot. A linked list doesn't have this problem, but you still have to iterate from the beginning to find the element you'd like to remove.

In both the array and linked list, insertion of an element is no problem. We just put it at the last position in the data structure. For removal to be efficient, we need know its position in the data structure ahead of time. We then just swap this element with the element in the last position. This keeps the data structure tightly packed, but at the expense of changing the order of its contents. In most cases, this won't matter.

When comparing arrays and linked lists for this purpose, the array becomes the data structure of choice. Linked lists usually need to allocate and deallocate memory for their nodes. In C++, this means longer processing times and possible fragmentation. In Java, we'd be invoking the garbage collector too often if we're adding and removing nodes in a tight loop. There are ways around this like pooling nodes, manual memory management, or making the objects themselves store node data. Arrays are just easier to work with.

Pattern

In the constant time array pattern, inserted objects are placed at the last array position that is not occupied. When we remove an object from the array, that empty position is replaced with the object in the last occupied array position. Thus, the array stays dense and we can always iterate from zero to the number of objects in the array minus one.

constant array

Some Java code to illustrate the item we wish to contain.

package com.terseworks.example;

public class Item
{
	private int index;

	public Item()
	{
		index = -1;
	}

	void setIndex(int index)
	{
		this.index = index;
	}

	int getIndex()
	{
		return index;
	}
}

And this is our container.

package com.terseworks.example;

public class Container
{
	private Item[] items;
	private int itemCount;
 
	public Container(int maxCapacity)
	{
		items = new Item[maxCapacity];
		itemCount = 0;
	}

	public void insert(Item item)
	{
		int index = item.getIndex();
		if (index < 0)
		{
			items[itemCount] = item;
			item.setIndex(itemCount);
			itemCount++;
		}
	}

	public void remove(Item item)
	{
		int index = item.getIndex();
		if (index >= 0 && index < items.length)
		{
			if (item == items[index])
			{
				items[index] = items[itemCount - 1];
				items[itemCount - 1] = null;
				item.setIndex(-1);
				itemCount--;
			}
		}
	}
}

I came upon this pattern when designing the physics engine of my apps. When a game object comes into existence, its rigid body component is inserted into the physics system for simulation. The system iterates over all rigid bodies, updating them in succession. Rigid bodies can be created or destroyed at any time, so having insertion and removal in constant time is a big advantage.

I was pleasantly surprised to see this pattern being used in other physics libraries like Havok and Bullet. This was reassuring to know that others have developed a similar solution.

Design Considerations

There is one caveat. We need to keep track of the index of the element if we want to remove the object without having to search the array. The index therefore needs to be stored on the object. This exposes implementation details to the outside world, but can usually be overcome with features of the language used. In C++, we can use friend classes and in Java we can use package-private access.

We could also use a hash table to put the onus on the container itself. The key being an object pointer and the value being an index into the array of objects. Of course this means more memory, more complexity, and slower access times. You'll have to decide if this is really worth the trouble.

There's also the possibility that we don't need to store the element index anywhere. If we simply flag the object for removal, it can be removed during the iteration and update process.

Despite the limitation of having to store the index, it also has one cool benefit. In the example, we use -1 as a default index value inside the object. We assign a new index when adding to the system and then reset it when removing from the system. Therefore, we know an object is already registered if its index is greater than -1. Checking the index when an object is added to the system will prevent it from being duplicated. This is ideal behavior for many types of data structures where it only makes sense to have all unique objects, such as a tree.

Variation

In the above examples, we assume that our objects are created outside of the container and the container serves the purpose of updating the objects it is given. There are other scenarios in which this pattern makes sense.

Consider an object pool. Everything we need is preallocated and we allow the user to take an object, use it for some purpose, then give it back when it is no longer needed. In my physics system, I have a pool of contact manifolds that functions this way.

package com.terseworks.example;

public class ItemPool
{
	private Item[] items;
	private int itemCount;
 
	public ItemPool(int maxCapacity)
	{
		items = new Item[maxCapacity];
		for (int i = 0; i < items.length; i++) items[i] = new Item();
		itemCount = 0;
	}

	public Item retrieve()
	{
		Item item = items[itemCount];
		item.setIndex(itemCount);
		itemCount++;

		return item;
	}

	public void recycle(Item item)
	{
		int index = item.getIndex();
		if (index >= 0 && index < items.length)
		{
			if (item == items[index])
			{
				Item last = items[itemCount - 1];
				items[index] = last;
				items[itemCount - 1] = item;
				last.setIndex(index);
				item.setIndex(-1);
				itemCount--;
			}
		}
	}
}

Conclusion

The constant time array pattern is useful when you need to iterate through a list of objects and these objects are inserted and removed from the list often. Since the object holds the container index, it can only be stored once in a single container. This is usually what we want though.