Concurrency

[noahyor]

Currently, Swarm runs on one thread.

At first, this is not really a problem, as Swarm does not have to do much computation. However, as you build more robots, the maximum tick rate decreases due to the constraints of the single core it is running on.

In the extreme case of the Conway's Game of Life Scenario, I took these screenshots. (using WSL, see #1825)

I think one of the most obvious places to add concurrency is in the CESK evaluation of robots.

We could use the async package to do so.

[kostmo]

I would love to make use of concurrency somehow. It may be tricky to apply to evaluation of the robot CESK machines, since <robot 2> must be able to see the new the state of the world after <robot 1> has modified it. Within a single "tick", robots strictly "take turns" without ever executing at the same time.

If it is any help, I started working on a "timing diagram" of the robot execution sequence.

However, there may be an opportunity to run "goal evaluation" in parallel with robot execution, since "goal evaluation" cannot mutate the state of the world. We might need to be able to "roll back" to a previous world state after robot execution if the goal evaluation decided that the scenario has been won/lost.

[kostmo]

Actually there may be an interesting opportunity to impose restrictions (through some kind of effect monad?) on the radius of observability/influence of robots, so that they might be executed concurrently without risk of "race conditions" so long as their "circles of influence" do not intersect.

Since there are quite a few robot commands that act at a distance (as well as system robots for which distance restrictions can be ignored), it would take some effort to cover all of the edge cases.

[xsebek]

@kostmo perhaps we could analyze if the robot could influence others at a distance.

I imagine a lot of robots only run commands that affect neighborhood cells and the others we could run before them.

[noahyor]

Maybe we could have it such that each robot runs asynchronously for their one tick, then returns say, a pair of a new CESK state and some outward-facing action they want to perform. A main thread would then perform said actions deterministically.

[noahyor]

@xsebek Some ideas:

There are some actions which cannot affect other robots, but most of them take 0 ticks to execute. (e.g. scan)

[noahyor]

so that they might be executed concurrently without risk of "race conditions" so long as their "circles of influence" do not intersect.

However a robot's "circle of influence" is infinite because of the improbable effects of the teleport command.

[noahyor]

Actually, thinking about it some more, since the teleport command places random things on the ground, determinism is already gone.

[xsebek]

@noahyor my point was that we could identify robots that want to teleport etc. and do only those synchronously.

[byorgey]

Just wrote up some thoughts inspired by this discussion at #1925. Eager to hear what others think.