Order of entities

One thing usually glossed over (if not outright ignored) on the topic of data-oriented design is the question of exactly which order/sequence you store your entities in. We know we want them stored contiguously, but that still leaves N! ways to skin a cat. You have to choose, whether consciously or accidentally.

It's important because it affects the spatial and temporal locality of memory accesses between entities, whether directly or as mediated by spatial data structures (etc). Games feature a bunch of entities that don't just inertly transform their own states based on their respective initial states. Entities interact with each other.

Now, the obvious options of entity order I've run into in past projects are very much intertwined with the mechanism that's ensuring contiguity. The options follow:

Swap Trick order. You move the last entity to the destroyed entity's old position (or some fancy batched variant of this). It's doubtful that the swap trick can be beaten for efficiency of removals per se, but it leaves the entities in some crazy order that is impossible to reason about, and probably impossible to exploit for efficiency. Due to anxiety over not knowing exactly what my code was doing, I stopped using the swap trick altogether some years ago.

Collapse order (anyone know a standard name for this?). You write the entity data back over itself based on an "alive" mask, with all dead entity data getting overwritten. This is my go-to for simple cases. It's efficient enough as you only eat the bandwidth cost of iterating the data once. Assuming you're inserting at the back, it leaves the entities in order of age. Long-lived entities cluster toward the beginning of the data, and short-lived ones toward the end. Makes some sense.

Sorted order. You just define some key based on parts of the entity state that are interesting to systems, such as position, prototype index, FSM state etc. Then, you sort the entities every frame. Now, I've rarely had to break out the big guns and go this route, but it has some good properties. Sorting is the only way that completely decouples contiguity-maintenance from order. It's super flexible and reasonable.

Nobody will call sorting "efficient" out of the box; however, the cost of sorting itself is tolerable on modern PC hardware at the sane limit of real-time entity processing, which I take as ~200,000. Re-arranging all the data can be more painful. There, you suffer the structure-of-arrays approach to some extent. Still doable in many cases. Looking at it another way, sorting trades a one-time cost for greater efficiency in any system that pulls together disparate entities. That guarantees some break-off point where sorting comes out ahead. (assuming you're not somehow cramming everything in L1 cache)

Anyway, it's too late and this post is too long, so for now some questions about the ECS and job system:

• exactly what order are entities stored in in the ECS?
• why was this order chosen?
• are there different options planned for direct support?

Cheers!

 

Cool. Please correct me if I'm wrong: it's essentially a bucket sorted order now, with one bucket per archetype. So to lay up jobs which process disparate entities, it can be prudent to do lots of filtering/specialization via components, to keep your working set small. And the same technique is how you avoid heavy branching (or excessive computations merged with predication) in jobs.

It leads to another question:

Do you eat a basically random memory indirection every time you access data via stable Entity ID vs ephemeral Component Index? If so, you should avoid the former unless you really need it, e.g. maintaining references to entities over several frames. I think I see this pattern in the StressTesting demo code.

BTW, I wish this stuff was a major topic in the documentation. Data-oriented design isn't new to me. I'm no hotshot expert, but I've been exposed to the literature from the beginning, and it heavily influenced the way I program. Probably more influential than any other broad idea- all programs really are just "reasonable data transformations". Being exposed to those ideas young helped me transition to more of a graphics programmer (GPU stuff is more intuitive to me now).

Most of the documentation seems like straightforward best practices, even where it's not some specific thing I've ever put to practice. But once you get into the thorny & intertwined issues of compactness, sequence, and maintaining references over time, you're hitting hard problems that necessarily involve serious trade-offs. Programmers need to know exactly which trade-offs were chosen in the underlying system, so they can consciously build their systems on that foundation. Disclaimer: this rant is a request! I know you guys are just getting started on the documentation.

Thanks a lot.

 

@Joachim_Ante So in the future, it will be possible to force certain archetypes to be sorted in a custom and maybe also fixed order (collapse order)? It would definitely make sense in cases where linear memory itself gives no performance benefits because we don't need to iterate through the component data, but instead, we need to navigate within it as if it was a 2D or a 3D array (e.g. mesh generation for voxel objects, A* pathfinding), or when we just need to access a specific subset. Also usually data like that can be pretty static, no entities destroyed or added, and some of them can instead be treated as empty.

Edit: I just figured out how to use arrays on entities, this solves a lot of my problems in theory, except arrays bigger than 10,000 do not work (https://forum.unity.com/threads/lists-of-things-collections-arrays-groups.524532/). Will it be possible to support dictionaries on entities too?

 

^ Bear in mind that due to the way memory paging and caching work, there is bound to be some scale at which logical memory locality in your program has zero correspondence to physical memory locality in the memory system. So some degree of hugeness of a voxel array is unnecessary for good locality. That's one reason why "chunking" is universal to any non-trivial voxel application. Try storing an appropriately-sized chunk of voxels per entity.

That raises just one more clarification. The latter part about random access to data is the indirection I alluded to. Why is there an additional indirection on merely accessing the map from Entity ID to Component Index? The obvious way is just a table storing an integer per Entity, in Entity order, which changes just as often as the bucket changes. Unless I'm missing something peculiar to this new ECS. Cheers!

 

Makes a lot of sense.