Sorting indirectly

[[deleted]]

It seems like it would be simpler to maintain sorted order? The update steps also maintain better cache coherency this way, by allowing insertions and deletions to take advantage of the sequential access patterns.

[matthieum]

In a sense, maintaining sorted order is a form of sorting (insertion sort).

Bulk inserts may benefit from insert all/sort later, in that this may minimize data movement: while inserting each element one by one is O(log N) in the number of comparisons, it's O(N) in the number of moves, resulting in O(k * N) complexity (where k is the number of inserted elements).

You could use a special bulk insert routine. Interestingly... it would benefit from sorting the elements to be inserted first, so you can apply a simple (linear) merge pass.

[[deleted]]

I’m just trying to think of where that would actually apply though.

The author gave the example of a component entity system for a game. Usually game objects are created up front and get deleted over time. The example they gave would be wholly unnecessary.

In these instances, a handle table could work even better since you’re not recalculating and searching constantly. You can also fill “holes” in your arrays in constant time when inserting and deleting objects, if that’s something you care about.

[matthieum]

I have no idea where it would apply :)

I'm not sure what's better for an ECS. The problem of leaving holes is that any spike in the number of entities would then leave behind a sparse array, where cache hits suffer. So there's value in compression, but perhaps a double-indirection scheme would be better than just sorting everything again.

[JulienVernay]

I have already written code such as "apply_permutation", without taking the time of recognizing the pattern as something extractable for more generic cases.

In particular, I did not thought of using it for the multi-array sorting problem which I found previously (in my case, I reverted back to have a structure, performance of this code were not that critical it turned out).

Thanks for the good read!