Improving the performance of UI list updates

My experience has shown that a recurrent problem in editors is updating lists of objects in a user interface fast. Example: entities in a level. Layers in a scene, etc, etc.

An implementation usually stores the objects separately and an extra list of the object pointers in the UI classes themselves. Such lists might, for instance be stored in an array inside a subclass of a QAbstractItemModel if one works in Qt.

Note: The code below does not use standard library classes, but it should hopefully be somewhat easy to follow

Updating

In a naive, object oriented approach there is a set method in our entity class. An implementation might look like this:

1 2 3 4 5

void Entity::setName(String name) { m_Name = name; m_NameChangedSignal(this); }

Our UI class is a listener of the m_NameChangedSignal (which might be an implementation of signals as in my previous post on variadic templates) and as soon as the name is set, an update is fired.

Our UI class' slot method is triggered. It can look like this:

1 2 3 4 5 6 7 8 9 10 11

class EntityUIList { void onSetName(Entity* entity) { int index = m_entities.find(entity); // gets data from entity at specified index, updates the displayed data updateUIListAtRow(index); } Vector<Entity*> m_entities; }

Now let's say our level includes a million entities. Far fetched? Not at all. Modern game levels can and do have an enormous level of detail and the object count contributes to this a lot.

If we batch update even just a few hundred objects, the cost of searching becomes large enough to notice. Furthermore, since a lot of UI systems are updated on the main thread, such updates might stall your editor for a significant amount of time.

Searching linearly M times takes a mean time of M*N/2 where N is the total number of entities. If we have a million entities in our level, the search time can rise dramatically.

Deletion

Deletion suffers from a similar issue. A naive implementation of deletion can look like that:

1 2 3 4 5 6 7 8

void EntityUIList::onDeletion(Entity* entity) { int index = m_entities.find(entity); beginRemoveRows(index); m_entities.erase(index); endRemoveRows(index); }

In this case not only do we pay the cost of searching, but the cost of erasing as well. Erasing an element at index in an array will usually move all items after index one position towards the start of the array. For M such operations, the mean cost can similarly be M*N/2.

(Yet) Another Fail Of Object Orientated Design

A naive approach to deletion and modification of data might use what we call synchronous notification. Synchronous notifications are executed immediately. Deleted objects will immediately trigger a web of updates and removal of each object from each listener.

An easy way to test if your favorite editor uses synchronous deletion is to make a level with a few hundred thousand entites, select all entities, press delete and enjoy the show. If it takes several seconds for your editor to respond back, you know that you are most likely dealing with a synchronous notification system.

Deleting all entities in a synchronous notification system might in fact hang your editor for a very long time. I'm not kidding. In a level with a few million entities, deleting all entities will trigger a square complexity operation, costing at least a few quadrillion operations. In modern systems where CPUs run with speeds of a few Ghz such operations can take minutes or even hours to execute.

 

...And Using Data Oriented Design To Fix It

So, how do we fix this? I have already implied a solution when I talked about synchronous notification systems. Any good programmer knows that listeners of synchronous notifications should not perform costly operations. 

Another thing that we can abuse is the fact that the UI does not need to be updated immediately; in fact we only need to do the update before the next frame. The update need not be synchronous, in fact we can do it asynchronously.

1 2 3 4 5 6 7

void EntityUIList::onDeletion(Entity* entity) { m_PendingDeletedEntities.push_back(entity); if(!m_updatePending) queueUpdateOnNextFrame(); }

Here we potentially pay the cost of allocation, but that should not be that great. As the size of the pending deletion array gets larger, it will take more between each allocation. Even better, we could improve the code by having a batch deletion function that takes an array of entities that we want to delete all at once. In fact using batch operations is the recommended way to work, since operations for single elements can always be expressed using the batch operations.

Using the function above, we will have a nice list of entities to delete by the end of the frame. We can now use the fact that all our data is nicely packed in arrays to perform a few operations to decrease the cost dramatically.

Improving Search Time

Any student of computer science knows that we can improve the search time in an array of objects if the array is sorted. The problem with such lists is that the UI is usually tied to the positions of data in the original array, thus making it difficult to move the original data arbitrarily.

Instead what we can do is introduce a helper struct that will store indices. Then we will sort an array of those helper structs using pointer arithmetic and after sorting we can lookup the original index. This is how such code will look like:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

void EntityUIList::onUpdate() { if(m_updatePending) { struct SortHelper { int index; Entity* entity; }; Vector <SortHelper> helper; helper.reserve(m_Entities.size()); int i = 0; for (Entity* entity : m_Entities) { helper.emplace_back({i++, entity}); } sort(helper.begin(). helper.end(), [] (const SortHelper * a, const SortHelper * b) { // use pointer arithmetic return a.entity < b.entity; }); Vector <int> indices; indices.reserve(m_PendingDeletedEntities.size()); for (Entity* entity : m_PendingDeletedEntities) { // we can retrieve the helper by searching using the entity pointer, // since helper is sorted using entity pointers SortHelper* helper = find_in_sorted_array(helper, entity); indices.push_back(helper.index); } ...

For N total entities and M deleted entities, this will take N*logN time for the inital sorting, and each search after that can be completed in logN time, for a total of (M + N) * logN. This is vastly better than an M*N time. 

Improving Deletion Time

We are not done yet. We need to somehow improve the time spent moving objects around during deletion. This is hard to avoid, yet there is a way to delete multiple elements from an array and only move non-deleted items once. This can be done trivially if our indices are sorted: Delete the first element, and move each element after it one position back, right up to the next element, whereafter we will move each element two positions back, right up to the third element whereafter we will move each element three positions back, etc etc.

The code is not presented here but it should be easy to implement. In fact this is such a useful function that I'm very surprised a version of it is not present in the standard library.

Conclusion

And there you have it! This was a somewhat niche problem, but I'm sure you'll find a lot of software out there that still does this wrong. I still hope you enjoyed reading.