Re: Are prerequisites made in deterministic order when parallelism is disabled?
On Tue, 2017-06-13 at 10:33 -0500, Brett Stahlman wrote: > I don't see anything in the Make docs that guarantees prerequisites > will be processed in left to right order. Opinions on the web seems to > be split into 2 camps: > > 1. Make always builds dependencies in left to right order, but a > well-designed Makefile won't rely upon it. > 2. Make is free to build dependencies in any order it likes, provided > it respects the stated dependencies. The answer is #1, with a caveat: all the prerequisites in the rule defining the recipe are always checked first (in the order they appear in that rule), regardless of the order in which the recipe rule appears. So, in both of these situations: foo: biz ; @echo $< foo: bar foo: boz and also: foo: bar foo: boz foo: biz ; @echo $< the order of dependency checking will always be "biz bar boz" (and $< will be "biz" of course). But, in this situation: foo: boz foo: biz blah bleah; @echo $< foo: bar then the order will be "biz blah bleah boz bar". The order is always the same and deterministic in a non-parallel build. When parallelism is introduced, GNU make still follows the same order of checking prerequisites. However, because some prerequisites will be blocked waiting for others, the algorithm will skip those and move on to other parts of the DAG and the actual order in which recipes are invoked is not deterministic (unless the time taken for each build is completely deterministic). ___ Bug-make mailing list Bug-make@gnu.org https://lists.gnu.org/mailman/listinfo/bug-make
Re: Are prerequisites made in deterministic order when parallelism is disabled?
On Wed, 14 Jun 2017 11:25:35 -0400 Kyle Rose wrote: > The right answer is always to write your makefiles so the rules execute > in the required order whether run in parallel or not. Relying on > whichever arbitrary ordering GNU make employs, even if that behavior is > stable(either historically or by design), is likely to result in sadness > at some point, such as when someone calls into your makefile recursively > from their own -j build. Sometimes I write Makefiles considering the performance at parallel builds and those Makefiles get their prerequisites ordered by approximately how much time each prerequisite needs to be built. Let me give you an example of such a rule: final_target: 3_hour_prerequisite 2_hour_prerequisite 1_hour_prerequisite do_something_quickly With the above example calling make without -j will take about 6 hours for all prerequisites to build. On a machine with 3 or more cores calling make with "-j 3" all prerequisites will be finished in 3 hours when also the most time consuming one is done. But what if we have a build machine with only 2 CPU cores? If so, calling make with "-j 2" will be the fastest way to compile, it will still be done in 3 hours. First the 3 hour job and the 2 hour job will be started in parallell, then after 2 hours one job will be finished and the remaining 1 hour job will be started. After a total of 3 hours the 3 hour job and 1 hour job will finish about at the same time. What would happen with "-j 2" if GNU Make changed the order of how prerequisites where compiled? Then it might start with the 1 hour job and the 2 hour job. Not until the 1 hour job where finished the 3 hour job would start and the total build time would be 4 hours instead. Even though the compile would complete successfully I think that not being able to depend on job start order would give a significant lack of performance. I can also come to think of examples when non parallel builds would benefit from a deterministic build order of prerequisites even though none of the prerequisites depend on each other. regards Henrik ___ Bug-make mailing list Bug-make@gnu.org https://lists.gnu.org/mailman/listinfo/bug-make
Re: Are prerequisites made in deterministic order when parallelism is disabled?
The right answer is always to write your makefiles so the rules execute in the required order whether run in parallel or not. Relying on whichever arbitrary ordering GNU make employs, even if that behavior is stable (either historically or by design), is likely to result in sadness at some point, such as when someone calls into your makefile recursively from their own -j build. Tl;dr: underspecified dependencies create hidden technical debt. Kyle On Tue, Jun 13, 2017 at 11:33 AM, Brett Stahlman wrote: > I don't see anything in the Make docs that guarantees prerequisites > will be processed in left to right order. Opinions on the web seems to > be split into 2 camps: > > 1. Make always builds dependencies in left to right order, but a > well-designed Makefile won't rely upon it. > 2. Make is free to build dependencies in any order it likes, provided > it respects the stated dependencies. > > My own recent experience suggests #2 is the correct statement, but I > can't rule out the possibility that a bug in my Makefile is producing > the apparent non-determinism I'm observing. At any rate, can anyone > point me to a definitive source on this? > > Thanks, > Brett S. > > ___ > Bug-make mailing list > Bug-make@gnu.org > https://lists.gnu.org/mailman/listinfo/bug-make > ___ Bug-make mailing list Bug-make@gnu.org https://lists.gnu.org/mailman/listinfo/bug-make
Re: Are prerequisites made in deterministic order when parallelism is disabled?
I've been waiting for Paul to show up with the definitive word but he may be away. I'm 95% sure he's spoken on this before with the gist of it being "While not required by standard, GNU make has always worked left-to-right and this will not change". While I *think* I've correctly channeled his answer, the real thing could probably be found in the archives of the help-make or bug-make mailing lists if you want to search there. David On Wed, Jun 14, 2017 at 7:36 AM, Brett Stahlman wrote: > On Wed, Jun 14, 2017 at 2:00 AM, Edward Welbourne > wrote: > > Brett Stahlman (13 June 2017 17:33) > >> I don't see anything in the Make docs that guarantees prerequisites > >> will be processed in left to right order. Opinions on the web seems to > >> be split into 2 camps: > >> > >> 1. Make always builds dependencies in left to right order, but a > >>well-designed Makefile won't rely upon it. > >> 2. Make is free to build dependencies in any order it likes, provided > >>it respects the stated dependencies. > >> > >> My own recent experience suggests #2 is the correct statement, but I > >> can't rule out the possibility that a bug in my Makefile is producing > >> the apparent non-determinism I'm observing. At any rate, can anyone > >> point me to a definitive source on this? > > > > I suspect most implementations of make do in fact build in left-to-right > > order but none guarantee it; and I won't be surprised if GNU make used > > to but has lately stopped doing so, although I can't give you a > > definitive source either way. I certainly wouldn't ever assume > > deterministic build order; if one prerequisite needs to be built before > > another, the make-file should express that via a dependency (perhaps > > just an order-only one). > > Makes sense. I saw it suggested somewhere that Make has to perform a > complex, inherently unstable, topological sort, which may make it > difficult to preserve left to right order. By experimentation, I > discovered that the order seemed to be affected by the actual target > names: e.g., names such as "foo" and "foo2" produced left to right > order, whereas "foo2" did not. For the vast majority of target names > tried, the order was strictly left to right. > > Thanks, > Brett S. > > > > > Eddy. > > ___ > Bug-make mailing list > Bug-make@gnu.org > https://lists.gnu.org/mailman/listinfo/bug-make > ___ Bug-make mailing list Bug-make@gnu.org https://lists.gnu.org/mailman/listinfo/bug-make
Re: Are prerequisites made in deterministic order when parallelism is disabled?
On Wed, Jun 14, 2017 at 2:00 AM, Edward Welbourne wrote: > Brett Stahlman (13 June 2017 17:33) >> I don't see anything in the Make docs that guarantees prerequisites >> will be processed in left to right order. Opinions on the web seems to >> be split into 2 camps: >> >> 1. Make always builds dependencies in left to right order, but a >>well-designed Makefile won't rely upon it. >> 2. Make is free to build dependencies in any order it likes, provided >>it respects the stated dependencies. >> >> My own recent experience suggests #2 is the correct statement, but I >> can't rule out the possibility that a bug in my Makefile is producing >> the apparent non-determinism I'm observing. At any rate, can anyone >> point me to a definitive source on this? > > I suspect most implementations of make do in fact build in left-to-right > order but none guarantee it; and I won't be surprised if GNU make used > to but has lately stopped doing so, although I can't give you a > definitive source either way. I certainly wouldn't ever assume > deterministic build order; if one prerequisite needs to be built before > another, the make-file should express that via a dependency (perhaps > just an order-only one). Makes sense. I saw it suggested somewhere that Make has to perform a complex, inherently unstable, topological sort, which may make it difficult to preserve left to right order. By experimentation, I discovered that the order seemed to be affected by the actual target names: e.g., names such as "foo" and "foo2" produced left to right order, whereas "foo2" did not. For the vast majority of target names tried, the order was strictly left to right. Thanks, Brett S. > > Eddy. ___ Bug-make mailing list Bug-make@gnu.org https://lists.gnu.org/mailman/listinfo/bug-make
Re: Are prerequisites made in deterministic order when parallelism is disabled?
Brett Stahlman (13 June 2017 17:33) > I don't see anything in the Make docs that guarantees prerequisites > will be processed in left to right order. Opinions on the web seems to > be split into 2 camps: > > 1. Make always builds dependencies in left to right order, but a >well-designed Makefile won't rely upon it. > 2. Make is free to build dependencies in any order it likes, provided >it respects the stated dependencies. > > My own recent experience suggests #2 is the correct statement, but I > can't rule out the possibility that a bug in my Makefile is producing > the apparent non-determinism I'm observing. At any rate, can anyone > point me to a definitive source on this? I suspect most implementations of make do in fact build in left-to-right order but none guarantee it; and I won't be surprised if GNU make used to but has lately stopped doing so, although I can't give you a definitive source either way. I certainly wouldn't ever assume deterministic build order; if one prerequisite needs to be built before another, the make-file should express that via a dependency (perhaps just an order-only one). Eddy. ___ Bug-make mailing list Bug-make@gnu.org https://lists.gnu.org/mailman/listinfo/bug-make
Are prerequisites made in deterministic order when parallelism is disabled?
I don't see anything in the Make docs that guarantees prerequisites will be processed in left to right order. Opinions on the web seems to be split into 2 camps: 1. Make always builds dependencies in left to right order, but a well-designed Makefile won't rely upon it. 2. Make is free to build dependencies in any order it likes, provided it respects the stated dependencies. My own recent experience suggests #2 is the correct statement, but I can't rule out the possibility that a bug in my Makefile is producing the apparent non-determinism I'm observing. At any rate, can anyone point me to a definitive source on this? Thanks, Brett S. ___ Bug-make mailing list Bug-make@gnu.org https://lists.gnu.org/mailman/listinfo/bug-make