3 ms·

Great feature. And shuffle isn't just useful for finding build issues, it can actually improve performance in some really annoying edge cases! The basic idea i

by aseipp 4y ago

Great feature. And shuffle isn't just useful for finding build issues, it can actually improve performance in some really annoying edge cases! The basic idea is this: Let's say you have a target being built and one of the dependencies takes a long time to compile; say, a large auto-generated file. If the time to compile this file is very dominant and outlandish, then you really want to do it as early as possible (while satisfying all dependent constraints), no matter what order the rules are in. This is so that it can overlap with other work as much as possible. If you instead pick it very late in the build process, it can significantly extend the total build time. A concrete example is one I had at a past job. We used CMake on a reasonably-sized and actively developed C codebase. Make took about 5 minutes to do a clean build. Switching to Ninja reduced that to 2:30s, on a clean build. That was great. But then, I used Shake -- a build system that ships with a Ninja-compatible build tool, just called "shake" -- to build the same project. 1m30s total![1] It took me a while to realize this is because shake by default randomizes build plans, both to find errors, and to increase performance in cases like this. By just shuffling the build order, you will get a "smooth" distribution of build times, whereas always deterministically sticking with 1 plan can result in a build plan with very very poor "tail latencies". This was the exact example I mentioned. The project built about 10 executables, and 1 of them was a very large auto-generated tool, and compiling it took 80% of the total wall clock time of all other jobs combined. So shake would often build this tool first or at least very early on, just by chance -- while Ninja and Make would often build it last, every single time. A very big impact on tail latency. So the TL;DR is -- randomize your build plans, knock out the missing dependencies, stabilize and ensure determinism where possible, and be happy! [1] Shake was only better on the "rebuild entirely from scratch" case versus Ninja. When doing incremental rebuilds with small edits, I basically couldn't find any (meaningful) difference in their performance.

salawat 4y ago
So you took the wrong lesson entirely? The real lesson from it would seem to me to be your first thoughts on what steps to do first in your build may be wrong. Profile until you find your best time to build, then lock it in. Non-determinism can be handy for discovering new things about what you're dealing with, nut once you've got it; for heaven sake, lock it in.
- aseipp 4y ago
  > So you took the wrong lesson entirely? No, you just have poor reading comprehension and poor understanding of the problem. > The real lesson from it would seem to me to be your first thoughts on what steps to do first in your build may be wrong. If you list the targets "a b c d e f" in make, then you can move 'f' into the front if it is very slow. If you use something like CMake, or another generator, you will lose control over this ordering, and it isn't always clear how to recover it in a non-fragile way. And yes, Shake has profiling tools. That's how I found out what the critical path is and why Shake was better at this path. > Non-determinism can be handy for discovering new things about what you're dealing with, nut once you've got it; for heaven sake, lock it in. Lol. Bad reading comprehension. Please don't bother commenting on things if you literally have no idea what you're talking about. I realize that's a big ask on this site (where shooting your mouth off and trying to sound smart is more valuable than being smart) but you'll waste less time with it. Thanks.
evmar 4y ago
[ninja author] Ninja build targets in a semi-arbitrary order: the memory order of the pointers to the objects representing the build steps. This was chosen in part because it was easy but also because it was a little unpredictable (in the same sense as this nice shuffling idea). In practice I might expect the pointers to get allocated in the order they're encountered while parsing though, so perhaps similar to Make. My recollection is we experimented a bit with different prioritizations but didn't find any that reliably were better. It does seem like you could try prioritizing "longer" tasks. (There are also more complex models that take into account the graph; I have been mentally drafting a blog post about this area, there's some interesting research history...) To do so you'd need to keep around data from previous executions of those tasks, and perhaps multiple runs (for the case where a given task can take a varying amount of time). In my newer n2 experiment, which was designed to be a little easier to hack on, the place you could play with prioritization is right here: https://github.com/evmar/n2/blob/d64412ae74ddff4e85329f390a0eb713b84cd5e5/src/work.rs#L248 https://github.com/evmar/n2/blob/d64412ae74ddff4e85329f390a0... The "available to run" tasks are in a deque there (which also means steps go in parse order) but you could easily imagine changing it to some sort of priority structure.
- aseipp 4y ago
  Thanks for the input, I haven't tried n2 yet. I don't have access to that code anymore but synthesizing an example to have the same outcome wouldn't be hard. I realized later on that Ninja used pointers when it traverses the build graph (by actually reading your blog, I think) which is where the more stable ordering came from. IIRC, when I asked Neil (shake author) about the randomness, I believe he said he added shuffling to mainly find bugs like the OP said, but also found it turned out to also win out in some cases like this where you have a weird distribution of build times with large outliers. > To do so you'd need to keep around data from previous executions of those tasks, and perhaps multiple runs (for the case where a given task can take a varying amount of time). Shake does do this actually, but only for ETA predictions, it doesn't use it for build ordering. It might be an interesting approach to try, but I'm not sure if it's much better than just doing it randomly, especially since if you modify the really expensive build step, you have to fully rebuild it anyway. In the no-op case, you just avoid it. So it would only help on clean rebuilds where you really want to pack the build steps in a better way to reduce the overall time. For CI systems it might be useful since the clean build is more common (this is what I was interested in) but, randomization is like, 80% results for 20% effort, and all.

by aseipp 4y ago

salawat 4y ago

So you took the wrong lesson entirely? The real lesson from it would seem to me to be your first thoughts on what steps to do first in your build may be wrong. Profile until you find your best time to build, then lock it in. Non-determinism can be handy for discovering new things about what you're dealing with, nut once you've got it; for heaven sake, lock it in.

aseipp 4y ago
> So you took the wrong lesson entirely? No, you just have poor reading comprehension and poor understanding of the problem. > The real lesson from it would seem to me to be your first thoughts on what steps to do first in your build may be wrong. If you list the targets "a b c d e f" in make, then you can move 'f' into the front if it is very slow. If you use something like CMake, or another generator, you will lose control over this ordering, and it isn't always clear how to recover it in a non-fragile way. And yes, Shake has profiling tools. That's how I found out what the critical path is and why Shake was better at this path. > Non-determinism can be handy for discovering new things about what you're dealing with, nut once you've got it; for heaven sake, lock it in. Lol. Bad reading comprehension. Please don't bother commenting on things if you literally have no idea what you're talking about. I realize that's a big ask on this site (where shooting your mouth off and trying to sound smart is more valuable than being smart) but you'll waste less time with it. Thanks.

evmar 4y ago

[ninja author] Ninja build targets in a semi-arbitrary order: the memory order of the pointers to the objects representing the build steps. This was chosen in part because it was easy but also because it was a little unpredictable (in the same sense as this nice shuffling idea). In practice I might expect the pointers to get allocated in the order they're encountered while parsing though, so perhaps similar to Make. My recollection is we experimented a bit with different prioritizations but didn't find any that reliably were better. It does seem like you could try prioritizing "longer" tasks. (There are also more complex models that take into account the graph; I have been mentally drafting a blog post about this area, there's some interesting research history...) To do so you'd need to keep around data from previous executions of those tasks, and perhaps multiple runs (for the case where a given task can take a varying amount of time). In my newer n2 experiment, which was designed to be a little easier to hack on, the place you could play with prioritization is right here: https://github.com/evmar/n2/blob/d64412ae74ddff4e85329f390a0eb713b84cd5e5/src/work.rs#L248 https://github.com/evmar/n2/blob/d64412ae74ddff4e85329f390a0... The "available to run" tasks are in a deque there (which also means steps go in parse order) but you could easily imagine changing it to some sort of priority structure.

aseipp 4y ago
Thanks for the input, I haven't tried n2 yet. I don't have access to that code anymore but synthesizing an example to have the same outcome wouldn't be hard. I realized later on that Ninja used pointers when it traverses the build graph (by actually reading your blog, I think) which is where the more stable ordering came from. IIRC, when I asked Neil (shake author) about the randomness, I believe he said he added shuffling to mainly find bugs like the OP said, but also found it turned out to also win out in some cases like this where you have a weird distribution of build times with large outliers. > To do so you'd need to keep around data from previous executions of those tasks, and perhaps multiple runs (for the case where a given task can take a varying amount of time). Shake does do this actually, but only for ETA predictions, it doesn't use it for build ordering. It might be an interesting approach to try, but I'm not sure if it's much better than just doing it randomly, especially since if you modify the really expensive build step, you have to fully rebuild it anyway. In the no-op case, you just avoid it. So it would only help on clean rebuilds where you really want to pack the build steps in a better way to reduce the overall time. For CI systems it might be useful since the clean build is more common (this is what I was interested in) but, randomization is like, 80% results for 20% effort, and all.