[PATCH] Thread the pathfinder computations to reduce latency

[wraitii]

Follow-up on ​https://wildfiregames.com/forum/index.php?/topic/21330-the-road-to-threads/

I have been looking at threading the pathfinding computations to drastically reduce our turn length and improve the impression of responsiveness.

The problem with threads is that we must guarantee: -no concurrent writes -no reads from something that might change during the thread's lifetime.

I have created a git branch hosted here: ​https://github.com/wraitii/0ad/tree/ThreadPathfinder (see also ​https://github.com/wraitii/0ad/tree/ThreadPathfinder_clean )

I implement threading by computing all paths in between turns and sending messages at the beginning of a turn. Additionally, some paths may be computed during the "Update" phase.

I can guarantee this is write-safe because: -The short-pathfinder now uses a thread-only state and has a read-only access to the pathfinder. It also calls the obstruction manager in a read-only way (enforced by using const). -The long-pathfinder's ComputeJPSPath is now const, so read-only.

The remaining issue is guaranteeing that what we read won't change. This is possible because pathfinder calls do not change the state, and the only external call is in the short-pathfinder, to GetUnitObstructions(). The obstruction manager only changes if a unit moves or an obstruction becomes active (or it's reset). This currently does not happen when sending MT_Update, since position changes happen in the various MT_MOTION and set active is not called by anything.

Now this is 100% safe in-between turns unless we're in Atlas. In Atlas, I currently de-activate the threading. It's safe to do it in parallel to Update, but that may break in the future. However, it'd be a shame to not use the time spent in MT_Update (particularly Timer) which can be quite substantial late-game. Just my 2 cents.

We could enforce the no-write-to-the-obstruction-manager by setting a boolean when computing paths and adding ENSURE calls in the obstruction manager (I will add a debug flag for that later in my branch).

This probably changes the sim hash of replays since calls will usually happen a little later.

[wraitii]

Also TODO: reimplement debug information using mutexes to be safe and remove now-dead code (such as the pathfinder.xml max computations per turn).

Edit: just realized my current way of computing in parallel with update will OOS as it's doing as many as it can in the imparted time, so it's non-deterministic. Will actually need to implement that differently for an effect, or not at all.

[elexis]

Moving to the new WIP milestone.

[wraitii]

Rebased: ​https://github.com/wraitii/0ad/tree/ThreadPathfinder I recommend using this branch for review: ​https://github.com/wraitii/0ad/tree/ThreadPathfinder_clean as it is slightly more squashed and the individual commit diffs should be cleaner. Overall though, this can probably be reviewed in a single unified patch.

[wraitii]

Some comments from IRC on 2016-12-13: Philip: -doesn't like the atlas hack. Recommends switching everything to copying all required data and then run with that instead. -recommends semaphore for "FetchAll…", which is currently idling at 100% CPU -noted accurately that my load balancing is primitive (not sure that's a real problem honestly) -recommends using a message-like system for the debugging, instead of my mutex hack -noted I don't enforce in code calling "FetchAll" before sending new tasks in "StartComputing…" so that should be done.

Main concern with the first point is that obstructions will need to be copied and they are an std::map and that's not extremely convenient, so it should probably be changed beforehand.

Itms noted that my headers appear to not compile even though they do on my machine™ so I'll have to look into that.

[elexis]

Patch ported to ​https://code.wildfiregames.com/D14

[wraitii]

In 25657:

Thread the pathfinder computations using the task manager.

The pathfinder computations are run asynchronously (and potentially on the main thread) in-between simulation turns, thus reducing pathfinder-related lag considerably in common cases.

To make this most efficient, the number of paths computed during a turn via MaxSameTurnMoves is reduced from 64 to 20.

This has a hard dependency on the obstruction manager (via the vertex pathfinder) not being modified in-between simulation turn (or to put it more generally on the simulation state not changing outside of turn computation), otherwise results will be non-deterministic and go OOS. This is currently entirely safe (as in, it indeed does not happen that the simulation state changes in-between turn), but future work towards improving simulation sandboxing would be good.

Thanks to Kuba386 for maintaining & improving the patch in 2020
Thanks to everyone who tested the various iterations of this patch.

Fixes #4324

Differential Revision: ​https://code.wildfiregames.com/D14