Add Longest-processing-time-first scheduling #88

old commented 2025年09月20日 05:13:27 +02:00

Currently, we are scheduling independent tasks in a FIFO (in reality, whatever fibers scheduler does). This works great with the job-server protocol.

However, nothing prevents us from creating a priority queue internally. I think it would make sens to prioritize tasks based on their previous run time. The longest an item takes to build, the highest its priority is. This is called LPT.

We already track time for external invocations. We might as well track time for full build-request and associate the duration to the buildable in the cache, given us a priority number for the next run.

Currently, we are scheduling independent tasks in a FIFO (in reality, whatever fibers scheduler does). This works great with the job-server protocol. However, nothing prevents us from creating a priority queue internally. I think it would make sens to prioritize tasks based on their previous run time. The longest an item takes to build, the highest its priority is. This is called [LPT](https://en.wikipedia.org/wiki/Longest-processing-time-first_scheduling). We already track time for external invocations. We might as well track time for full build-request and associate the duration to the buildable in the cache, given us a priority number for the next run.

pastor commented 2025年09月20日 11:26:44 +02:00

I've read the Wikipedia page you've linked, I did not take time to understand the math behind. Please, could you explain what advantage we get from such scheduling algorithm? Does it make a difference?

In the Wikipedia page they explain that the algorithm distributes the load between machines, I'm guessing, for our use case, those machines would be CPU cores. However, can we really provide an efficient scheduling with that regard? For example, for a C build using GCC, I'm guessing we cannot control how many CPU cores the computation of a compilation unit (.o file) would take. So even if we where to distribute the jobs between different CPU cores, we are not in control with what resources the external process would hoard, right?

I'm sure I'm missing something since I'm not familiar at all with this topic.

I've read the Wikipedia page you've linked, I did not take time to understand the math behind. Please, could you explain what advantage we get from such scheduling algorithm? Does it make a difference? In the Wikipedia page they explain that the algorithm distributes the load between machines, I'm guessing, for our use case, those machines would be CPU cores. However, can we really provide an efficient scheduling with that regard? For example, for a C build using GCC, I'm guessing we cannot control how many CPU cores the computation of a compilation unit (.o file) would take. So even if we where to distribute the jobs between different CPU cores, we are not in control with what resources the external process would hoard, right? I'm sure I'm missing something since I'm not familiar at all with this topic.

old commented 2025年09月20日 16:26:51 +02:00

Basically, consider a build with 2 job slots. You have N items that all take 1 minute to run. You also have a single bigger item that takes 2 minutes to run. All items are independent (no dependencies).

The worst case with a FIFO would be to run all small item first, then the big item. So the first N - 1 small items will run first, then the last small item will run along the big item. Thus you get a (N - 1) / 2 + 2 = (N + 3) / 2 minutes total run.

Now if you were to instead run the long item first along a small item, by the time the long item has finished, two small items also have finished (as opposed to before where no items were left to process). Thus you have 2 + (N - 2) / 2 = (N + 2) / 2 minutes. By scheduling the longest item first, you have save 1 / 2 minute on your total run. In reality, this difference can be greater. For example in blue, the blue/build.scm takes around 3 seconds to compile. But I suspect it gets schedule last after all other modules that takes around 1 second to compile. In the end, I have to sit 4 seconds in front of the terminal to see the results instead of 3.

My understanding is that this heuristic can be used to approach the optimal solutions quite closely without requiring much complexity. Mathematically, the worst case scenario is a 33 % overhead on the optimal solution. There are other heuristics that can be made of course, but the current FIFO approach can have a much greater overhead in the worst case scenario.

For example, for a C build using GCC, I'm guessing we cannot control how many CPU cores the computation of a compilation unit (.o file) would take.

GCC can use the MAKEFLAGS environment variable and take job slots for its parallelization. Of course, if between runs the number of job slots that is used to compile the compilation unit is different, the time will vary between run. But this is also the case if your system is under heavy load. What matter is the average times. The more you work on the project, the better the approximation will get. Of course this is not perfect and if your approximation is completely wrong, the scheduling become as worst as FIFO.

There are other possible heuristics that could be used instead, but I think this is one is trivially done and we could manage it as a feature. So if for some reason it does not do good on a certain environment, the user can simply disable it.

Basically, consider a build with 2 job slots. You have N items that all take 1 minute to run. You also have a single bigger item that takes 2 minutes to run. All items are independent (no dependencies). The worst case with a FIFO would be to run all small item first, then the big item. So the first `N - 1` small items will run first, then the last small item will run along the big item. Thus you get a `(N - 1) / 2 + 2 = (N + 3) / 2` minutes total run. Now if you were to instead run the long item first along a small item, by the time the long item has finished, two small items also have finished (as opposed to before where no items were left to process). Thus you have `2 + (N - 2) / 2 = (N + 2) / 2` minutes. By scheduling the longest item first, you have save `1 / 2` minute on your total run. In reality, this difference can be greater. For example in blue, the `blue/build.scm` takes around 3 seconds to compile. But I suspect it gets schedule last after all other modules that takes around 1 second to compile. In the end, I have to sit 4 seconds in front of the terminal to see the results instead of 3. My understanding is that this heuristic can be used to approach the optimal solutions quite closely without requiring much complexity. Mathematically, the worst case scenario is a `33 %` overhead on the optimal solution. There are other heuristics that can be made of course, but the current FIFO approach can have a much greater overhead in the worst case scenario. > For example, for a C build using GCC, I'm guessing we cannot control how many CPU cores the computation of a compilation unit (.o file) would take. GCC can use the `MAKEFLAGS` environment variable and take job slots for its parallelization. Of course, if between runs the number of job slots that is used to compile the compilation unit is different, the time will vary between run. But this is also the case if your system is under heavy load. What matter is the average times. The more you work on the project, the better the approximation will get. Of course this is not perfect and if your approximation is completely wrong, the scheduling become as worst as FIFO. There are other possible heuristics that could be used instead, but I think this is one is trivially done and we could manage it as a feature. So if for some reason it does not do good on a certain environment, the user can simply disable it.

pastor commented 2025年09月20日 23:01:16 +02:00

I see, thanks for the explanation!

Sounds good as a feature that can be disabled, what would be even cooler is if we provide some kind of interface for the user to hook whatever scheduler algorithm they want to use. We would maintain the 2 you suggest, FIFO and LPT, but the user could always bring something that fits their needs.

Would that kind of API be difficult to expose?

I see, thanks for the explanation! Sounds good as a feature that can be disabled, what would be even cooler is if we provide some kind of interface for the user to hook whatever scheduler algorithm they want to use. We would maintain the 2 you suggest, FIFO and LPT, but the user could always bring something that fits their needs. Would that kind of API be difficult to expose?

old commented 2025年09月21日 02:02:21 +02:00

Would that kind of API be difficult to expose?

I want to see how I can make LPT by using a single fiber that manager others. If it works nicely, nothing prevents us from implementing the scheduler as a set of procedures that users could provide yes.

> Would that kind of API be difficult to expose? I want to see how I can make LPT by using a single fiber that manager others. If it works nicely, nothing prevents us from implementing the scheduler as a set of procedures that users could provide yes.