7 ms·

I want to stop doing -j with make, and instead allow the OS scheduler --- which alone is in the position to make the right call ---- to "pull" more batch jobs t

I want to stop doing -j with make, and instead allow the OS scheduler --- which alone is in the position to make the right call ---- to "pull" more batch jobs to run as system resources allow. Perhaps one can do this or almost do this with io_uring?

alchemist1e9 4y ago
That would be a really neat feature. I do run slurm on single nodes and sbatch with dependencies to emulate some of the effect you are asking for.
- Ericson2314 4y ago
  Glad to hear you think so too!
gtirloni 4y ago
> which alone is in the position to make the right call Why is the OS scheduler alone in a better position than make itself to make the right call?
- Ericson2314 4y ago
  Everyone else is guessing how may "fork" commands to throw out the OS. The OS itself has much more information at its disposal about what resources are being used, where the bottle necks are etc. An elegant design on doing this in userspace probably boils down to going well on the awy to making a micro kernel.
  - nyanpasu64 4y ago
    Specifically one failure mode I've seen with Ninja is that it starts 12 processes for my 12-threaded CPU, each process eats 2 gigabytes of RAM, and I only have 16 gigabytes of RAM total, so it sends my system into swap or oomkiller. Ideally when the RAM fills up (whether because of compilers spawned by Ninja, or because I opened Discord), Ninja would kill one of the build processes and send it back onto the build queue, and reduce the number of compilers running at a time by 1 until I either tell it, or (some heuristic like) over 1.5 times the maximum RAM taken by a single compiler so far gets freed up. I don't know if this is best handled by the OS, userspace Ninja, or some combination (like cgroups).
  - Mister_Snuggles 4y ago
    This sounds a lot like the idea behind Dispatch[0] (aka, Grand Central Dispatch) on Apple systems. [0] https://developer.apple.com/documentation/DISPATCH https://developer.apple.com/documentation/DISPATCH
jrockway 4y ago
I don't think either make or the OS have enough understanding to do a perfect job here. Think about the case where you have 32 CPUs, and so make starts 32 of the first tasks in the dependency graph. 31 of those tasks are routine compilations, but 1 task computes some data that a ton of other compilations need. What make and the OS don't know is that task would be 32x faster if was using all 32 CPUs. So by starting 31 random compilations, it's actually increasing the end-to-end latency dramatically, because so many things depend on that 1 job running as quickly as possible. make and the OS basically only solve one tiny part of the problem of fast builds; maximize cpu utilization right now. They don't have enough data to make the latency of the build faster. It's very much a "good enough" approach; lots of people have faster builds because of "make -j32", but it could hardly be considered general enough to guarantee the fastest possible end-to-end build time. (And even things like Bazel don't quite have enough information to do this. Imagine you have some test that does "sleep 60" in the middle; you really want parallelism to go up to 33 when the test enters that state, and you want to ensure that you start it 60 seconds before the rest of the tests will be finished. There isn't enough data in the BUILD file to do that, though, so you're just stuck.) Anyway, one thing you can do is get more memory and set -j higher than the number of cores/vCPUs. I think the kernel does a good job ensuring that each job makes progress, so if you have a scenario where something like a test benefits from starting as early as possible in the build and then basically goes to sleep, you'll still use 100% of your CPU, but make progress on that wait. The downside is that these things use a lot of RAM. I remember trying to build Envoy on a 64 vCPU machine once; each C++ process used over a gig of RAM, and I simply didn't have enough. I got more, and found that running 64 parallel compiles with SMT was about 10% faster than 32 parallel compiles. But, requires double the RAM (think it was about 80GB). TL;DR lots of constraints to balance and optimize. Make is probably going to be the worst performing build system that you can use, but the field is hardly a "solved problem", and further research could probably yield general improvements. Also, buy yourself a lot of RAM when it's cheap. Having some code paged in and ready to go when the CPU is free is good for throughput.
- Ericson2314 4y ago
  Yes it would be nice to share that information with the scheduler too. This would be were some sort of microkernel userland scheduler one can augment with arbitrary information would do well.
astrange 4y ago
The reason it’s pushed down to make is the OS scheduler doesn’t know what gcc is. make, of course, doesn’t know what gcc is either but at least it has a better chance of learning. (The OS does know what resources current processes are using, but that doesn’t help because it doesn’t know what any future process will do. Designs like GCD solve this with priority levels, but that doesn’t help because all your make tasks are the same high priority.)
foxhill 4y ago
if i recall correctly, this is basically the premise of apple’s Grand Central Dispatch API. which, unfortunately, never seemed to go anywhere..

alchemist1e9 4y ago

That would be a really neat feature. I do run slurm on single nodes and sbatch with dependencies to emulate some of the effect you are asking for.

Ericson2314 4y ago
Glad to hear you think so too!

gtirloni 4y ago

> which alone is in the position to make the right call Why is the OS scheduler alone in a better position than make itself to make the right call?

Ericson2314 4y ago
Everyone else is guessing how may "fork" commands to throw out the OS. The OS itself has much more information at its disposal about what resources are being used, where the bottle necks are etc. An elegant design on doing this in userspace probably boils down to going well on the awy to making a micro kernel.
- nyanpasu64 4y ago
  Specifically one failure mode I've seen with Ninja is that it starts 12 processes for my 12-threaded CPU, each process eats 2 gigabytes of RAM, and I only have 16 gigabytes of RAM total, so it sends my system into swap or oomkiller. Ideally when the RAM fills up (whether because of compilers spawned by Ninja, or because I opened Discord), Ninja would kill one of the build processes and send it back onto the build queue, and reduce the number of compilers running at a time by 1 until I either tell it, or (some heuristic like) over 1.5 times the maximum RAM taken by a single compiler so far gets freed up. I don't know if this is best handled by the OS, userspace Ninja, or some combination (like cgroups).
- Mister_Snuggles 4y ago
  This sounds a lot like the idea behind Dispatch[0] (aka, Grand Central Dispatch) on Apple systems. [0] https://developer.apple.com/documentation/DISPATCH https://developer.apple.com/documentation/DISPATCH

jrockway 4y ago

I don't think either make or the OS have enough understanding to do a perfect job here. Think about the case where you have 32 CPUs, and so make starts 32 of the first tasks in the dependency graph. 31 of those tasks are routine compilations, but 1 task computes some data that a ton of other compilations need. What make and the OS don't know is that task would be 32x faster if was using all 32 CPUs. So by starting 31 random compilations, it's actually increasing the end-to-end latency dramatically, because so many things depend on that 1 job running as quickly as possible. make and the OS basically only solve one tiny part of the problem of fast builds; maximize cpu utilization right now. They don't have enough data to make the latency of the build faster. It's very much a "good enough" approach; lots of people have faster builds because of "make -j32", but it could hardly be considered general enough to guarantee the fastest possible end-to-end build time. (And even things like Bazel don't quite have enough information to do this. Imagine you have some test that does "sleep 60" in the middle; you really want parallelism to go up to 33 when the test enters that state, and you want to ensure that you start it 60 seconds before the rest of the tests will be finished. There isn't enough data in the BUILD file to do that, though, so you're just stuck.) Anyway, one thing you can do is get more memory and set -j higher than the number of cores/vCPUs. I think the kernel does a good job ensuring that each job makes progress, so if you have a scenario where something like a test benefits from starting as early as possible in the build and then basically goes to sleep, you'll still use 100% of your CPU, but make progress on that wait. The downside is that these things use a lot of RAM. I remember trying to build Envoy on a 64 vCPU machine once; each C++ process used over a gig of RAM, and I simply didn't have enough. I got more, and found that running 64 parallel compiles with SMT was about 10% faster than 32 parallel compiles. But, requires double the RAM (think it was about 80GB). TL;DR lots of constraints to balance and optimize. Make is probably going to be the worst performing build system that you can use, but the field is hardly a "solved problem", and further research could probably yield general improvements. Also, buy yourself a lot of RAM when it's cheap. Having some code paged in and ready to go when the CPU is free is good for throughput.

Ericson2314 4y ago
Yes it would be nice to share that information with the scheduler too. This would be were some sort of microkernel userland scheduler one can augment with arbitrary information would do well.

astrange 4y ago

The reason it’s pushed down to make is the OS scheduler doesn’t know what gcc is. make, of course, doesn’t know what gcc is either but at least it has a better chance of learning. (The OS does know what resources current processes are using, but that doesn’t help because it doesn’t know what any future process will do. Designs like GCD solve this with priority levels, but that doesn’t help because all your make tasks are the same high priority.)

foxhill 4y ago

if i recall correctly, this is basically the premise of apple’s Grand Central Dispatch API. which, unfortunately, never seemed to go anywhere..