System dependencies

[torkleyy]

cc @Frizi @kabergstrom

As far as I understood, there should be an explicit notion of stages, which are the only thing systems can depend on.

Some questions:

• Do stages depend on stages?
• Are all systems organized in a stage? Or are there systems which do not have an explicit stage and just get inserted in a way that meets their dependencies?

[Frizi]

All systems would be organized in a stage. Here is a more detailed post about that idea.

https://community.amethyst-engine.org/t/igneous-a-path-to-a-usable-engine/422/19?u=frizi

[torkleyy]

Ah, okay, thanks!

I'm a bit unsure - doesn't this limit parallelism too much? If things are too organized into phases, that could result in very sequential execution, especially when considering that phases are about one specific process ("physics"), which often means the same storages are mutated.

Can you elaborate more on how many and which stages you'd have in a typical game?

[kabergstrom]

I'm a bit unsure - doesn't this limit parallelism too much? If things are too organized into phases, that could result in very sequential execution, especially when considering that phases are about one specific process ("physics"), which often means the same storages are mutated.

Phases only define a relative ordering constraint where previously it would be in system registration order or based on system dependency constraints. It does not limit parallelism in as much as it limits the execution ordering of systems, right?

[Frizi]

Think of phases as a scaffolding for dependency graph. If you have a systems A and B that are registered one after another, B depends on A only if it reads or writes any resource that A writes. This can be easily extended to arbitrary number of systems in sequence, you only check last producers of system's resources in reverse registration order to figure out exact dependencies. If you have a physics phase and the systems inside it only ever write to position/velocity and such physics-related components, everything that doesn't read them can run in parallel. On the other hand, anything that wants to know a position and is registered in a phase that runs after physics, it HAS to wait for physics to complete. This is a desired behaviour, you have to wait in order to make sure that the position is updated before further processing.

As far as dependencies between the systems inside the "physics" phase goes, you can't get around that problem. If you have many systems mutating the same resource, you can't schedule them to run in parallel anway.

[torkleyy]

Thank you both! I think I understood now.

Just one example to make sure I really did; let's say there are two phases, with one system each. Both systems are not conflicting. Thus, they can run in parallel. Is that correct?

[kabergstrom]

Just one example to make sure I really did; let's say there are two phases, with one system each. Both systems are not conflicting. Thus, they can run in parallel. Is that correct?

Yes! You can express the execution of systems as a DAG, and can actually get an execution ordering using the toposort algorithm in petgraph.

To express it as a DAG in petgraph,

1. Assign a number to each phase based on their relative ordering
2. Put all systems in a list sorted by phase and registration order
3. Create a dummy root node
4. Create a map to keep track of the last observed system node that mutated a resource
5. Iterate over the systems, creating a new node for each system:

• For each resource accessed by the system:
  • Create an edge from the system node that last accessed the resource mutably (or root if none) to the current system node.
  • If the resource is accessed mutably, update the map created in step 4

If you want to retain the feature of explicit dependencies, you need to consider those ordering constraints in the sorting steps 1,2. But I'm not sure if the concepts are compatible, since you could potentially be introducing cycles by having both features.

Once you have an ordering, during dispatch you only need to ensure that a system's dependencies in the graph have completed before dispatching a system. In your example, the system nodes would not have graph dependencies on each other, and therefore can be dispatched without waiting on completion of each other.