Re: Are prerequisites made in deterministic order when parallelism is disabled?

[Paul Smith]

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?

[Henrik Carlqvist]

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?

[Kyle Rose]

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?

[David Boyce]

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?

[Brett Stahlman]

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?

[Edward Welbourne]

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?

[Brett Stahlman]

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