Game Developer

Four ways to link a list (a performance test on linked list architectures)

Posted on

In looking at entity systems for Flash games, and particularly the projects Ember and Xember, I was wondering what is the most efficient architecture for the linked lists used by these systems. So I ran some tests.

The code for these tests is all available on Github.

The lists in these frameworks are used to manage the component sets for the systems that run the game. These lists need to provide three functions - add an item, remove an item, and loop through all the items, and they need to do this as efficiently as possible.

So I created four different architectures for linked lists and ran a few performance tests.

1. The list node contains the data (NodeContainsDataList).

(source code)

This is a classic linked list architecture where the nodes in the list have a data property which contains the data to be added to the list. Because removing data from the list requires finding the node that contains the data, I added a dictionary for quickly finding the node that contains a specific piece of data.

I expect adding an item to the list to be slow because it involves creating a node object. Reading the data from the node requires casting from a dynamic property to the specific data type, which may slow it down a little. Removing data from the list also requires removing data from the dictionary, which will slow it down somewhat.

2. The data extends the list node class (DataExtendsNodeList).

(source code)

In this scenario the data class to be stored in the list extends a list node class. So this architecture uses inheritance rather than composition to create the list node that contains the data. This is the mechanism used in Ember.

Adding and removing data from the list should be quick because the data is the node. There is no casting and no object creation required. However, looping through the list members requires an upcast from the base list node type to the specific data type which is likely to slow it down.

3. The data is the list node (DataIsNodeList).

(source code)

In this scenario the data node is the list node. The data node has two properties, next and previous, which link it in to the list. This is the mechanism used in Xember.

Adding and removing items may be slowed a little by the dynamic casts required, but looping should be very fast since the data type is explicitly known at all times and no type-casting is required.

4. There is no list node (NoNodeList).

(source code)

Rather than using list nodes, this list maintains two dictionaries for mapping between each data item and the next and previous data items in the list.

This is an attempt to find a solution that had the simplicity of the NodeContainsDataList class, where the data requires no modification for storage within the list, but without the penalty of creating nodes for each data item. It does require the use of dictionary objects, which are not particularly fast, so it's interesting to see if it's faster or slower than the other scenarios.

The results

I ran the tests over Flash's native Array and Vector classes too. The tests add 50,000 items to a list, remove 50,000 items from a list, and loop through 500,000 items in a list. I ran the tests four times and display the average of the results below. The tests were run using the release version of Flash Player 11.0.1.152 on a MacBook Pro. The times are measured in milliseconds.

CollectionAddRemoveLoop
Array31182413
Vector41144814
NodeContainsDataList31349
DataExtendsNodeList2523
DataIsNodeList3911
NoNodeList225356

(N.B. Linked list performance is disproportionately affected by using the debug version of the Flash Player. If you run the tests yourself use the release version of the player.)

As expected, the fastest architecture overall is the one where the data is the node (DataIsNodeList). However, lets consider the scenario for an entity & component based game architecture.

Given the size of the data sets, the only overwhelmingly slow results are for removing items from the Array and Vector collections. If we reject these, all four linked list architectures have reasonable speeds.

For an entity system, the most critical aspect of the collection architecture is the loop speed. In this context, only two of the loop architectures stand out as significantly slower, DataExtendsNodeList and NoNodeList. Rejecting these leaves two architectures to choose from.

Of these, NodeContainsDataList is, surprisingly, a little faster on the loop test despite the dynamic cast required to read the data. However, I'm not convinced that the difference is significant relative to other differences.

In the add and removal tests, DataIsNodeList is significantly faster for reasons outlined above. But add and remove are far less critical to the game engine than looping through the list items.

There is one other significant difference between these two list architectures. DataIsNodeList requires the user of the game engine to explicitly add the next and previous properties to the data class, while NodeContainsDataList requires no modification to the data class. This ease of use may outweigh the speed difference, particularly in a framework designed for general use.

What do you think? Is there another, potentially better, architecture that I've missed?

Share this post or a comment online -


Also in the collection Actionscript