As we have seen with this post, the sparse set is a great tool for decoupling component pools and creating a much more flexible model.
Another of the big advantages of using sparse sets, although less obvious, is that of being able to easily sort an entire pool of components according to our needs. How easy is it to induce an order in such a complex data structure efficiently?

With this post I’ll try to describe some solutions with which I’ve experimented, emphasizing their pros and cons.

If you haven’t done it yet, read the previous parts of the series before to continue. It will help to fully understand this one.

Introduction

One of the first problems encountered when we want to sort a sparse set is the fact that it’s composed by two vectors, the sparse array and the dense array. Consider std::sort and how we would use it. There is no way to sort two vectors at once directly with it. This gets even worse when the sparse set is used as a base for the pools of components because we have three vectors in this case (at least with EnTT).
However, a sorting algorithm like std::sort would be perfect for in-place sorting. It can sort pools using no auxiliary data structures nor extra memory but for the few variables used to control the algorithm itself.

On the other side, keep in mind that in-place sorting requires to swap elements and therefore to move them here and there. This has a cost and it’s amplified when we’ve to do it on many different vectors.
So, what about an alternative approach that does consume memory but that has also better overall performance? Permutations seems to be the way to go here.

Maybe there is also another solution, though. A method that combines the best of the two worlds. How far can we go with it?

Mr Obvious

The basic case of a sparse set is trivial to sort. If we don’t use it as a base for our pools or similar and therefore we have only two arrays (the dense and the sparse ones), sorting the sparse set means sorting only the dense array, then update the indexes in the sparse array:

std::sort(dense.begin(), dense.end(), compare);

for(auto pos = 0; pos < dense.size(); pos++) {
    sparse[dense[pos]] = pos;
}

Nothing easier. This works also when we combine entities and components in a single object in the dense array, because we still have only two arrays, that is the basic implementation of the sparse set.
However, this doesn’t work that well when we have one or more extra dense arrays like it happens in EnTT. If you are wondering why it’s not enough to merge the dense arrays and return to the basic case, the answer is because I want to have always two separate pointers to the lists of entities and components, without having to load them all in memory during the iterations and then filter what isn’t necessary.

In the sections that follow I’ll refer only to the solutions that are useful in cases in which there are two or more dense arrays associated with a single sparse array.

In-place sorting

In-place sorting is the best approach when we want to keep low memory usage. These algorithms get the job done a swap at a time until the container is fully sorted.

Sorting in-place a sparse set is a bit tricky and cannot be done with the tool offered by the C++ standard library, namely std::sort. This function accepts two iterators to the range to sort and starts to swap elements within the container directly. Unfortunately, we don’t have a single container here. Instead we have two (or even more) of them and therefore this approach isn’t viable.
One of the problems is also the fact that std::sort requires random iterators and they are such that they return actual references rather than proxy objects. Otherwise the problem could be solved with a dedicated class that swaps what’s required in all the arrays when moved around.

The solution is pretty simple: roll your own sorting algorithm and take control of the section where elements are moved. This means writing a very specific function that works only with sparse sets and the performance of which are most likely lower than that of std::sort.
No matter how good programmers we feel: std::sort is developed by people who are probably smarter than us, it’s widely tested and highly optimized for various corner cases. We will hardly do better, but at least we’ll have something that works even with a sparse set!

How does this work?

I won’t give you magic advices on how to implement a sorting algorithm. Whether you’re a young programmer or an experienced programmer, you’ve probably already heard about sorting algorithms an infinite number of times. So, choose the one you prefer and start to sort the dense array of a sparse set. When we get to the point where two elements need swapping, this is where things change and these are the steps to do:

  • Swap the elements in the sparse array using the positions expressed by the dense array.

  • Swap the elements in the dense array. Repeat this step for all the dense arrays.

If you remember how a sparse set works, the dense array is a kind of backward link to the sparse array used for validity checks. Therefore, as the elements in the sparse array literally points to the cells in the dense array, the opposite is true as well. This makes the whole thing straightforward to implement.
The first step makes our elements point to each other values. The second step just swaps the actual values and rebuild the links.

As you can see, ordering a sparse set in-place is pretty trivial. However, when two elements need to be swapped, the number of operations is much higher than usual. The more dense arrays we have, the more this cost increases with the number of swaps, with the risk that it may become too high.
If we combine the cost of the swaps with the fact that our sorting algorithm will probably not be as efficient as for example std::sort, it’s clear why this solution is not always the best one.

Permutation

If you can afford an out-of-place sorting, permutations are the way to go to exploit the performance of std::sort and drastically reduce the number of swaps.
The basic idea is simple: first of all, compute the permutation in an external array. Then apply it to the sparse set. The cost of the first step is that of the sorting algorithm but this time we’re sorting a vector of integers. On the other hand, applying the permutation to a sparse set is linear with the size of the container and this should help to speed up everything quite a lot.

To get our permutation, first of all we need a temporary array the size of which is the the same of the dense array of our sparse set:

std::vector<std::size_t> copy(dense.size());
std::iota(copy.begin(), copy.end(), std::size_t{});

We initialize the array with the numbers from 0 to N-1, where N is the size of our dense array. It will give us at any time the information about what position a given element should have in the sorted sparse set. It goes without saying that the i-th element occupies the i-th cell before to start and that’s why we fill it this way.

To sort our support vector, we use one of the dense arrays (most likely the one that containse the components) and the positions returned by std::sort as:

algo(copy.begin(), copy.end(), [this, compare = std::move(compare)](const auto lhs, const auto rhs) {
    return compare(dense[lhs], dense[rhs]);
});

Where compare is the comparison function provided by the user. From the dense array we get the elements that occupy the given positions and return them instead of the numbers used to fill copy, because the latter have no sense for the users. However, note that those numbers are stable even if they are moved around within copy. Therefore they can be safely used to retrieve the right elements step by step.
If we look at a real world example like EnTT (until version 3.1 at least), it’s really close to the example above. Because users are sorting components and not entities, we use the positions to retrieve the actual instances of the components and return them directly. The logic is exactly the same, in fact we have two dense arrays that are kept in sync and it’s a matter of using the right one to get what we need.

When std::sort returns, we have the permutation to use to sort our sparse set within copy.
To apply the permutation to our sparse set, the basic idea is that we get the i-th element and move it around, one swap at the time, until it reaches its destination. This has the side effect that also all the elements encountered along the path are placed in their final positions.
The way we must move the element is encoded directly within copy:

for(size_type pos{}, length = copy.size(); pos < length; ++pos) {
    auto curr = pos;
    auto next = copy[curr];

    while(curr != next) {
        swap(copy[curr], copy[next]);
        copy[curr] = curr;
        curr = next;
        next = copy[curr];
    }
}

As described above, swap is a function that is in charge of swapping the items both in the sparse array and in the dense array (be aware that we aren’t invoking std::swap, we don’t want to swap the elements within copy).
If it seems complicated and it’s not immediate why the cost is O(N), let’s dissect the snippet and see what’s happening under the hood.

If we get a closer look at the permutation to apply to our vector, we note that we can start from any index and jump to the element that should occupy that position, one element at a time and until the first item reaches its position (this happens when we get to the point where we should jump back to the starting point).
In other terms, we can spot one or more cycles in the support vector. Every element points to the item that reclaims its position and we have a closed path if we put these steps in a row.

Because of this, every time we make a jump, it will be enough to move back the element we find in the new cell and take the initial one with us until we jump to its final position. When the next jump takes us to the starting point, we stop and release the object in the current cell. The snippet above exploits this fact and nothing more. It applies the permutation one thread at a time.

The cost is linear despite the internal loop becasue the while is entered only for the elements that haven’t been moved already to the right position. To skip the elements that were part of the cycles we walked through so far, we use the copy array and update it every time we make a jump. We know that the position we left behind after a jump is occupied now by the right element and therefore we can set copy[i] = i, that is what satisfies the guard of the internal loop.
This way, the loop serves only the purpose of iterating a cycle, it doesn’t make the overall cost grow up fortunately. It also happens that this approach is quite efficient, even though it requires auxiliary memory in order to save our permutation.

Mixing in-place sorting and permutations

Fortunately sparse sets have some feature we can exploit to get the best of the two worlds, that is a kind of permutation based in-place sorting. This will give us all the benefits of in-place sorting and get rid of the extra costs of swapping.
Sounds interesting, doesn’t it?

Permutations use a support vector, that is also why they consume memory. Sorting in-place work with the dense array of the sparse set. The sparse array is what we needed to be able to sort in-place the elements inside the dense array, thus obtaining a permutation, then apply the latter to all the other arrays.
Another of the advantages of this solution is that we don’t have to apply the permutation also to the dense array used as a base to sort the set, which makes us save further.

A possible implementation (quite close to that of EnTT) is this:

template<typename Compare>
void sort(Compare compare) {
    std::sort(dense.begin(), dense.end(), std::move(compare));

    for(std::size_t pos{}, end = dense.size(); pos < end; ++pos) {
        auto curr = pos;
        auto next = sparse[dense[curr]];

        while(curr != next) {
            adjust(dense[curr], dense[next]);
            sparse[dense[curr]] = curr;
            curr = next;
            next = sparse[dense[curr]];
        }
    }
}

It’s not very different from what we’ve already seen, except for a few details.
Basically, the copy support array is no longer necessary. In its place sparse is used to literally keep track of the fact that we’ve already visited some elements. These are then excluded when tested again in the internal loop, keeping the algorithm linear in the length of dense.

Furthermore, the swap function mentioned above is no longer in use. This is because this time we don’t have anymore to swap elements within dense.
However, we introduce thn new function adjust that is invoked when we are going to swap two entities within sparse. By construction, we sorted one of the dense arrays but we have still to update all the other dense arrays as well as the sparse one. Fortunately we can still get the original indexes of the given entities from the sparse array and use them to swap the elements in their data structures, just before we update on of those indexes.
We can define the adjust function as something along this line, repeated for every dense array that is still to be sorted:

std::swap(another_dense[sparse[lhs]], another_dense[sparse[rhs]]);

If it seems complicated, well, I must admit that this time it’s slighlty trickier than what we’ve seen in the previous sections. However, the same algorithm and ideas have been used here, so it’s only a matter of putting the pieces together to understand how the sparse array takes part into the game.
If you’re interested, you can look into the implementation provided with EnTT and follow it step by step to see what’s happening under the hood.

Conclusion

Sorting a sparse set can be simple but also very complicated, depending on the use that is made of it and what constraints are placed on this part. The basic implementation is trivial to sort but things tend to get more complex when we extend it with multiple dense arrays.
With this article I hope to have given you some inspiration to take the first steps in this direction and, why not, to improve my solution further and propose your modifications to the implementation provided with EnTT. It took me some time and several iterations to get to what’s there today, starting with a simple but less powerful version, up to one that I can easily use on a large number of entities without too many worries.

The best part of all this is that maybe I didn’t even get close to the best and I made errors that I can’t notice because I’m so ignorant, so any feedback is welcome!
Every time I look at this algorithm I have the feeling that something is wrong, but maybe it’s just my amazement that it really works.

Let me know that it helped

I hope you enjoyed what you’ve read so far.

If you liked this post and want to say thanks, consider to star the GitHub project that hosts this blog. It’s the only way you have to let me know.

Thanks.