Efficiently separating Read/Compute/Write steps for concurrent processing of entities in Entity/Component systems

Question

Setup

I have an entity-component architecture where Entities can have a set of attributes (which are pure data with no behavior) and there exist systems that run the entity logic which act on that data. Essentially, in somewhat pseudo-code:

Entity
{
    id;
    map<id_type, Attribute> attributes;
}

System
{
    update();
    vector<Entity> entities;
}

A system that just moves along all entities at a constant rate might be

MovementSystem extends System
{
   update()
   {
      for each entity in entities
        position = entity.attributes["position"];
        position += vec3(1,1,1);
   }
}

Essentially, I'm trying to parallelise update() as efficiently as possible. This can be done by running entire systems in parallel, or by giving each update() of one system a couple of components so different threads can execute the update of the same system, but for a different subset of entities registered with that system.

Problem

In the case of the shown MovementSystem, parallelization is trivial. Since entities don't depend on each other, and don't modify shared data, we could just move all entities in parallel.

However, these systems sometimes require that entities interact with (read/write data from/to) each other, sometimes within the same system, but often between different systems that depend on each other.

For example, in a physics system sometimes entities may interact with each other. Two objects collide, their positions, velocities and other attributes are read from them, are updated, and then the updated attributes are written back to both entities.

And before the rendering system in the engine can start rendering entities, it has to wait for other systems to complete execution to ensure that all relevant attributes are what they need to be.

If we try to blindly parallelize this, it will lead to classical race conditions where different systems may read and modify data at the same time.

Ideally, there would exist a solution where all systems may read data from any entities it wishes to, without having to worry about other systems modifying that same data at the same time, and without having the programmer care about properly ordering the execution and parallelization of these systems manually (which may sometimes not even be possible).

In a basic implementation, this could be achieved by just putting all data reads and writes in critical sections (guarding them with mutexes). But this induces a large amount of runtime overhead and is probably not suitable for performance sensitive applications.

Solution?

In my thinking, a possible solution would be a system where reading/updating and writing of data is separated, so that in one expensive phase, systems only read data and compute what they need to compute, somehow cache the results, and then write all the changed data back to the target entities in a separate writing pass. All systems would act on the data in the state that it was in at the beginning of the frame, and then before the end of the frame, when all systems have finished updating, a serialized writing pass happens where the cached results from all the different systems are iterated through and written back to the target entities.

This is based on the (maybe wrong?) idea that the easy parallelization win could be big enough to outdo the cost (both in terms of runtime performance as well a code overhead) of the result caching and the writing pass.

The Question

How might such a system be implemented to achieve optimal performance? What are the implementation details of such a system and what are the prerequisites for an Entity-Component system that wants to use this solution?

Answer 1

----- (based on the revised question)

First point: since you don't mention having profiled your release build runtime and found a specific need I suggest you do that ASAP. What does your profile look like, are you thrashing the caches with bad memory layout, is one core pegged at 100%, how much relative time is spent processing your ECS versus the rest of your engine, etc...

Read from an entity and compute something... and hold onto the results somewhere in an intermediate storage area until later? I don't think that you can separate read+compute+store in the way you think and expect this intermediate store to be anything but pure overhead.

Plus, since you're doing continuous processing the main rule you want to follow is to have one thread per CPU core. I think that you are looking at this at the wrong layer, try looking at entire systems and not individual entities.

Create a dependency graph between your systems, a tree of what system needs results from an earlier system's work. Once you have that dependency tree then you can easily send entire systems full of entities off to process on a thread.

So let's say that your dependency tree is morass of brambles and bear traps, a design issue but we have to work with what we have. The best case here is that inside each system each entity does not depend on any other result inside that system. Here you easily subdivide the processing across threads, 0-99 and 100-199 on two threads for an example with two cores and 200 entities that this system owns.

In either case, at each stage you have to wait for results that the next stage depends on. But this is OK because waiting for the results of ten large blocks of data being processed in bulk is far superior to synchronizing a thousand times for small blocks.

The idea behind building a dependency graph was to trivialize the seemingly impossible task of "Finding and assembling other systems to run in parallel" by automating it. If such a graph shows signs of being blocked by constant waiting for previous results then creating a read+modify and delayed write only moves the blockage and does not remove the serial nature of the processing.

And serial processing can only be turned parallel between each sequence point, but not overall. But you realize this because it is the core of your problem. Even if you cache reads from data that haven't been written yet you still need to wait on that cache to become available.

If creating parallel architectures were easy or even possible with these kinds of constraints then computer science wouldn't have been struggling with the problem since Bletchley Park.

The only real solution would be to minimize all these dependencies to make the sequence points as rarely needed as possible. This may involve subdividing systems into sequential processing steps where, inside each subsystem, going parallel with threads becomes trivial.

Best I got for this problem and it's really nothing more than recommending that if hitting your head on a brick wall hurts then break it into smaller brick walls so you're only hitting your shins.

Answer 2

I've heard of an interesting solution to this problem: The idea is that there would be 2 copies of the entity data (wasteful, I know). One copy would be the present copy, and the other would be the past copy. The present copy is strictly write only, and the past copy is strictly read only. I'm assuming that systems don't want to write to the same data elements, but if that's not the case, those systems should be on the same thread. Each thread would have write-access to the present copies of mutually exclusive sections of the data, and every thread has read-access to the all past copies of the data, and thus can update the present copies using data from the past copies with no locking. Between each frame, the present copy becomes the past copy, however you want to handle the swapping of roles.

This method also removes race conditions because all systems will be working with a stale state that will not change before/after the system has processed it.

Answer 3

I know 3 software designs handling parallel processing of data:

1. Process the data sequentially: This may sound wierd since we want to process the data using multiple threads. However, most scenarios require multiple threads just in order for work to be completed while other threads wait or do long running operations. Most common usage are UI threads that update the user interface in a single thread, while other threads may run in the background, but are not allowed to directly access the UI elements. In order to pass results from the background threads, job queues are used that will be processed by the single thread at the next reasonable opportunity.
2. Synchronize the data access: this is the most common way to handle multiple threads accessing the same data. Most programming languages have build in classes and tools in order to lock sections where data is read and/or written by multiple threads concurrently. However, caution should be taken to not block operations. On the other hand, this approach costs a lot overhead in real-time applications.
3. Handle concurrent modifications only when they happen: this optimistic approach can be done if collisions occur rarely. The data will be read and modified if there was no multiple access at all, but there is a mechanism that detects when the data was updated concurrently. If that happens, the single computation will just be executed again until success.

Here some examples for each approach that may be used in an entity system:

1. Lets think of a CollisionSystem that reads Position and RigidBody components and should update a Velocity. Instead of manipulating the Velocity directly, the CollisionSystem will instead put a CollisionEvent in the work queue of an EventSystem. This event will be then processed sequentially with other updates to the Velocity.
2. An EntitySystem defines a set of components that it needs to read and write. For each Entity it will aquire a read lock for each component that it wishes to read, and a write lock for each component that it wishes to update. Like this, every EntitySystem will be able to concurrently read components while update operations are synchronized.
3. Taking the example of the MovementSystem, the Position component is immutable and contains a revision number. The MovementSystem savely reads the Position and Velocity component and computes the new Position, incrementing the read revision number and tries updating the Position component. In case of a concurrent modification, the framework indicates this on the update and the Entity will be put back in the list of entities that have to be updated by the MovementSystem.

Depending on the systems, entities and update intervals, each approach might be good or bad. An entity system framework might allow the user to choose between those options to tweak the performance.

I hope I could add some ideas to the discussion and please let me know if there are some news about it.