Give priority to slow actions

[Colecf]

Android's ninja fork added a feature somewhat recently where long-running actions (using information from a prior build) would be prioritized more highly than quicker actions. This got rid of some periods of time where the build was bottlenecked on a few actions, and reduced our build times by ~15%. N2 would need the same feature for android to adopt it.

In addition, we also pass a manually-defined file that maps from an output file to a priority int to use on clean builds when ninja doesn't know how long actions take yet.

https://android-review.googlesource.com/c/platform/external/ninja/+/2483775
https://android-review.googlesource.com/c/platform/external/ninja/+/2597009

[evmar]

How is the external file generated?

We did some experimentation around this in Ninja but in my recollection we never found a heuristic that reliably improved things. For example maybe you want to prioritize long-running tasks, but then also what matters more is bottlenecks even if they're short, so maybe you want some function involving both, and also maybe if the last build failed on a given step you want to run that step first because the user is likely iterating on some error, and so on.

(Interestingly I recently learned this is a well-researched area of knowledge because it dates back to industrialization: imagine you have a factory with N machines and a process with M steps that use the machines and they take time T etc. etc., you can imagine all the modeling you could do. But I don't know a lot about it.)

In any case I am open to ideas if they are not too invasive. Right here is the place where we pick a task to run from the set of available-to-run tasks, and I could imagine having some thread on the side trying to rearrange the queue there to implement whatever interesting prioritization you come up with.

[Colecf]

The external file for clean builds is just heuristics: There are some hardcoded action types that get high weighting by default, and then after that if the actions have above a certain number of inputs, they're prioritized by number of inputs.