Re: looking for build order doc in parallel build

[Paul Smith]

On Thu, 2009-11-19 at 16:30 +0900, Yasushi SHOJI wrote:
> From what I have read, I thought that make will pick up what to work
> on in depth-first order, regardless of parallelism. If that's true,
> I'd assume, once 1.fo is done, make will pickup 1.pdf, instead of
> N.fo.

It's true that make will always walk the dependency graph in depth-first
order.  But that doesn't mean that all the jobs that it runs will be run
in depth-first order.

If make always had to run things in strict depth-first order then there
would be no such thing as parallelism at all.  If make needs to run
"1.pdf" before it can think about running the next set of jobs like
"2.fo", and it can't run "1.pdf" until after "1.fo" is completed
(because the former depends on the latter), then how can anything ever
be run in parallel?

Even though make considers targets in depth-first order, if parallelism
is enabled it will invoke multiple targets at the same time, as long as
the second does not list an already-running (or not yet run, of course)
target as a prerequisite.

Here, 2.fo does not depend on 1.fo, so make knows it can build them both
at the same time.

> from the result above, I assume that make is not selecting the next
> work every time a forked sub process finish working (because that'd be
> too expensive?), but decide the work order _before_ the first job
> starts, no?

No.  Make never knows how much work there is to do before it's all done.

Make just walks the dependency graph the same way regardless of whether
there is parallelism or not.  The only difference is when it waits;
without parallelism it waits after each job.  With parallelism, it can
keep going until it runs out of parallelism.

> would you mind to enlighten me, if time permits, how it selects the
> next work?  a pointer to make source code would be very much
> appreciated.

There's no one place you can go to see the algorithm.  It is embedded in
the way make works; you can find it in the combination of remake.c and
job.c in the code.

-- 
-------------------------------------------------------------------------------
 Paul D. Smith <address@hidden>          Find some GNU make tips at:
 http://www.gnu.org                      http://make.mad-scientist.net
 "Please remain calm...I may be mad, but I am a professional." --Mad Scientist