Add some kind of fairness-mechanism to benchmark scheduling

[michaelwoerister]

Currently there's a case where a try-build has been executed for a while but the baseline for is way towards the end of the benchmarking queue, while at the same time new jobs get pushed to the front of the queue almost as fast as they can be processed. As a result it will take an unbounded amount of time until the try-build can be usefully checked for performance regressions.

It would be great if older benchmarking jobs would have a higher priority than newer ones, or jobs that are needed as a baseline for try builds would have a higher priority, or there was at least some randomization of priorities so that no single job will have to wait forever.

In the long run we should probably do benchmarking on more than one machine at once.

[RalfJung]

Seems like actually having a queue (the job that waited the longest runs next) instead of what looks to be more like a stack (the most recently added job runs next) would do it?

[michaelwoerister]

Yes, that would be an improvement.

[Mark-Simulacrum]

That's not quite ideal because if we've missed one commit a couple days ago it's not generally critical that we get data for it, whereas data for more recent commits is generally more desirable.

[Mark-Simulacrum]

I believe we've not had too many issues with this lately. The current algorithm, roughly, is that a try commit gets priority and hoists its parent to run before it (such that when the try commit's own build is finished, the results are fully ready). Beyond that we schedule most recent commits first.

[nnethercote]

I agree the current algorithm is working well.