sakerbuild/saker.build

Support dynamic reallocation of computation tokens

Sipkab opened this issue · 0 comments

The build system should support dynamic reallocation of the computation tokens of duplicated inner tasks to increase concurrency.

A scenario when this matters:

  • Task A runs high number of inner tasks with computation tokens. E.g. C++ compilation task
  • Task B wants to run with computation tokens.
  • Task C depends on task B but on on task A.

In cases where task A is started first, it could quickly exhaust all of the computation tokens available on a PC. This causes task B to wait until A is finished as it cannot start due to the lack of computation tokens.

With some additional timing information, we can see how this affects build times.

Task A: 25 CPUmin
Task B: 1 CPUmin
Task C: 4 CPUmin

If the current PC has 5 computation tokens, it will run as follows without token reallocation:
Task A, Task B, Task C = 5 + 1 + 4 = 10 min

With token reallocation, Task B and C can run alongside Task A (as 1 token from A was reallocated to B and C), however, Task A would take longer.
5 mins of running 20 CPUmin of Task A (4 tokens) and 1+4 CPUmin for Task B and C.
1 min for running the remaining 5 CPUmin of Task A.
This totals in 6 minutes that is much less than without reallocation.

Solution is to dynamically reduce the allocated inner task computation tokens of a given task until a minimum of 1 (so it still runs) and reallocate them to new tasks.