4 ms·

[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

by 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 evmar 4y ago

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.