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

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?

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

  1. I’ve also been playing around with ember, and forked it for my own amusement.

    You could have the DataIsNodeList implement an interface (rather than having head, tail, and node untyped) and see if it affects performance.

    I modded ember to hide the list node implementation altogether and just rely on an iterator, but I was going for api clarity, not performance.

  2. Thanks for the idea. I didn’t try the interface because I am sure it will affect performance. First, next and previous become getter methods so that they can be defined in the interface, and second their types become the interface type, so they have to be cast to the data type. That will give the loop worse performance than the DataExtendsNodeList loop. But for completeness I should have created it to see if my assumptions were correct.

    There’s often a trade off between api clarity and performance. I considered extending the proxy class to allow using for each(…) on the collection but assumed that would be slow. Another assumption I should probably test.

  3. I should point out here that the other reason behind this approach in Ember is so we can get code hinting in the loops. As as3 dosn’t have genrerics this is the closest we can get. Its rather clumsy but its the best compomise I could find. Xember improves on this but requires a little more typing for each node. For clarity the ideal would be to have a typed vector yet some how reduce the removal cost.

  4. For better readability, I was trying to apply Visitor pattern to loop operations ( https://github.com/Hyzhak/Four-ways-to-link-a-list/blob/master/src/data/LoopTestVisitor.as  ), and Interface for Data prototype (https://github.com/Hyzhak/Four-ways-to-link-a-list/blob/master/src/lists/IData.as ). But I was disappointed about performance of Visitor. It was predictable for me, but not in 4 times slower.
    https://github.com/Hyzhak/Four-ways-to-link-a-list/blob/master/bin/PerformanceTestRunner.swf 

    Thanks for interesting performance experiment.

  5. Instead of splicing vectors, the class instance which a Vector manages could contain an “index” variable to save it’s index position in that Vector.

    That way, whenever removal is done, you just need to check what position the object was in that vector, and perform a straightforward O(1) pop-removal if the removed item is at the tail of the list, or pop-back replacement operation with the tail object/inside object to be removed. In certain cases, I hold a private len:int property for the vector (to iterate only up to that limit) if you wish to avoid resizing the vector, (and only resize it optionally at certain times or not depending on the needs of your app or adopt a fixed size buffer if one so wishes.

    I find that prepending to a list header works great for DataIsNodeList/DataExtendsNodeList (eg. data.next = dataListHeader; dataListHeader = data; ) and iteration can be done elegantly with a for-loop like: for (var d:DataIsNodeList=dataListHeader; d!=null; d=d.next) {}.

    For iteration through a linked list to update entities and possibly remove/unhook any “dead” entities along the way, I feel the following approach is best used:
    var next:Particle, last:Particle;
    for (var p:Particle = particleHeader; p!=null; p =next ) {
    next = p.next;
    if (p.dead) { // unhook
    if (last!= null) last.next = p.next
    else particleHeader = p.next;
    // return back to pool header
    p.next = pool;
    pool = p;
    continue;
    }
    p.update();
    last = p;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>