commit 93b97a59aa8f7c193cdb78363ccc6e64a96b82df
author Shahbaz Youssefi <syoussefi@chromium.org> Sat Nov 04 02:07:23 2023
committer Angle LUCI CQ <angle-scoped@luci-project-accounts.iam.gserviceaccount.com> Fri Nov 10 20:15:19 2023
tree 0a45ec8a5370fa6308710680d9b5bbab09e92958
parent aec4ffac02c0a093c7ff03d2069c4660ce552599

Make link job directly wait on compile job

Previously, program link waited on the compile job on the calling thread
before launching the link job.  As a result, sequences of intermixed
compile and link would get largely serialized as such:

Main Thread       Thread 1       Thread 2       Thread 3       Thread 4
 Compile -------> Compile
 Compile -----------|----------> Compile
 Link               |              |
   Wait             |              |
   |                |              |
   |<--------------/--------------/
   \------------------------------------------> Link
 Compile -------> Compile                        |
 Compile -----------|----------> Compile         |
 Link               |              |             |
   Wait             |              |             |
   |                |              |             |
   |<--------------/--------------/              |
   \---------------------------------------------|-----------> Link
 Compile -------> Compile                        |              |
 Compile -----------|----------> Compile         |              |
 Link               |              |             |              |
   Wait             |              |             |              |
   |                |              |             |              |
   ...

With this change, the main thread no longer waits for compilation to
finish.  It's the link job itself that does the waiting.  This allows
the main thread to go through Compile and Link commands without
blocking, generating as many jobs as needed.  The above scenario
therefore becomes:

Main     T1     T2     T3     T4     T5     T6     T7     T8     T9
 C ----> C
 C ------|----> C
 L ------|------|----> L
 C ------|------|-------W---> C
 C ------|------|-------|-----|----> C
 L ------|------|-------|-----|------|----> L
 C ------|------|-------|-----|------|-------W---> C
 C ------|------|-------|-----|------|-------|-----|----> C
 L ------|------|-------|-----|------|-------|-----|------|----> L
 .        \-----\------>/     |      |       |     |      |       W
 .                     |       \-----\------>/     |      |       |
 .                     |                    |       \-----\------>/
 .                     |                    |                    |
 .                     |                    |                    |

This greatly improves the amount of parallelism compile and link jobs
get.

The careful observer may note that the link job being blocked on the
compile job is now wasting a thread from the thread pool.  While this
change is strictly an improvement, parallelism can be further improved
if the link job is just not assigned to a thread until the corresponding
compile jobs are finished.  This is currently not possible, but may be
if:

- Instead of a thread pool, the operating system's FIFO scheduler is
  used.  Then the operating system would automatically put blocking
  tasks to sleep and pick up another task.  This has the downside of
  requiring threads to be created for each task.
- The thread pool work scheduler is enhanced to be made aware of
  relationship between tasks and avoid scheduling jobs whose
  dependencies are not yet met.

Alternatively, the number of threads in the pool can be increased by 30%
and hope for the best.

Bug: angleproject:8297
Change-Id: If4e6540ade47558a10cfab55e2286f073b904928
Reviewed-on: https://chromium-review.googlesource.com/c/angle/angle/+/5006874
Commit-Queue: Shahbaz Youssefi <syoussefi@chromium.org>
Reviewed-by: Geoff Lang <geofflang@chromium.org>
Reviewed-by: Charlie Lao <cclao@google.com>