Automated threading

[rlipsc]

Goal

Currently threading systems requires the user to explicitly write thread synchronisation. This is inflexible and error prone, and requires human effort. Since Polymorph assures state operations are known at compile-time, we can use this to automate threading without any additional user input. Parallel execution and synchronisation can then be driven directly by system design.

Shared work for automatic threading

Create a ground truth of component-system activity.

• Track read/write access to instance types within systems.
• Track if component access is directly from the system work list (ie; using item.foo or sys.groups).
• Track fetchComponent within systems.

Path threading

Path threading refers to splitting up system execution into non-interacting "paths", where each path contains a sequence of systems that share access to the same components and so must be run serially.

This is done by tracking which components are accessed through their instance types. From this we can determine which systems are being accessed, and in turn define sets of non-interacting systems. Each path may be executed in a separate thread, and joins are performed when different paths interact.

The order a user defines systems informs the joining and splitting of paths.

When enabled, path threading can automatically run systems in parallel using knowledge of component accesses and the order of systems. The design of the ECS being made then defines how threading occurs whilst still guaranteeing the order of execution with no extra user work.

For example given the following systems:

System1 uses [A, B, C]
System2 uses [A]        # Order indicates we expect System1 to have finished.
System3 uses [C]        # Expects System1 to have finished, doesn't care about System2.
System4 uses [A, B]     # Expects System 2 to have finished.
System5 uses [C]        # Expects System3 to have finished.
System6 uses [B, C]     # Both System4 and System5 must be finished.
System7 uses [C]        # System7 must wait for System6.

From this sequence we could derive threading paths as:

Thread1	Thread2
System1	Wait for System1
System2	System3
System4	System5
Wait for System5
System6
System7

Work required for path threading

• Determine minimum non-interacting paths through systems.
• Generate thread procs for each path and apply spawns and joins.

Inner threading

Inner threading refers to the execution of an individual system being split into multiple threads, taking advantage of the fact that within a system each group of components accesses unique memory locations. These systems split their work lists between the desired number of threads and join once all work is complete.

An inner threaded system blocks until all its threads have completed to maintain system order.

Threading is only applied to the all block within a system. Other blocks such as init and finish will be executed in the current path thread.

This feature is more complex than path threading since it requires more analysis of access patterns to ensure safety. Systems may perform actions that alter their own work list, such as removing components and deleting entities, and may use compile-time opaque fetches on stored entities which could also be being processed on another thread.

Considerations

GC access

Seq and Table access must currently be guarded, so there will likely be some limitations on GC types. This affects entity storage, component storage and system storage when configured to use these types.

Arrays shouldn't need any locking provided isolated access can be confirmed, eg:

• Array access is in the same path.

Creating new rows in a running, inner threaded system

Systems that add groups to themselves are easily handled since threads are given a start and end group index, and new groups are added to the end of the list and so are naturally processed next pass.

Deleting rows in a running, inner threaded system

For systems that delete from themselves however, more nuance is required. Potential solutions to this are:

• Disallow any deleting from systems that use inner threading.
• Stage remove and delete operations to execute after systems have finished iterating.

Adding new rows or deleting rows in other systems

Systems that add components which create rows in other systems should be disallowed unless it can be proven that this system is not currently running.

From the perspective of inner threaded systems, other systems aren't running when they are in the same path thread.

Fetching components

Thread-safe fetching:

• The fetched component must not touch systems in another path.
• Fetching components can only ensure access by type.
• It cannot be guaranteed which threads access a user stored entity.
• Access can be safe when fetching only happens from the entity in system groups.

Work required for automatic inner threading:

• Ability to specify a system as threaded:
  • Options for default system threading.
  • System building command to override inner threading defaults.
• Initial implementation:
  • Thread spawning on slices of groups.
  • Fetching components is disallowed.
  • Only allowed access to components from the current system group, item.
  • Only array types.
• GC considerations handled.
• Fetching handled.
• Adding to other systems handled.
• Adding to running system handled.
• Remove from other systems handled.
• Remove from running system handled.
• Delete handled.