Re: looking for build order doc in parallel build

[Yasushi SHOJI]

Hi Paul,

At Thu, 19 Nov 2009 09:13:00 -0500,
Paul Smith wrote:
> 
> 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?

right. 

I guess I just misunderstood from the idea of "depth-first" that gnu
make uses depth-first order to _search_ the next work.

> 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.

true.

but, what do you think about this hypo-situation:

lets assume that we have the following DAG

all
|
+--------+--------+
|        |        |
1.pdf    2.pdf    3.pdf
|        |        |
1.fo     2.fo     3.fo

that says, "all" depends on 1.pdf, 2.pdf and 3.pdf. those pdfs depends
on 1.fo, 2.fo, 3.fo, respectively.

if you run make with -j 2, two jobs will be spawn and those two jobs
takes 1.fo and 2.fo. and the DAG is now like this:

all
|
+--------+--------+
|        |        |
1.pdf    2.pdf    3.pdf
|        |        |
1.fo=1   2.fo=2   3.fo

=N: job N is working on

now, job 1 finished working on 1.fo, but job 2 is still working on
2.fo, what should job 1 take?

all
|
+--------+--------+
|        |        |
1.pdf#   2.pdf    3.pdf
|        |        |
1.fo*    2.fo=2   3.fo#

*: done
#: possible candidates

I thought make would take 1.pdf because of depth-first order. but
appiaretly the current implementation takes 3.fo. which is not a bug
or anything.  I just thought it wouldn't.

> > 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.

ok. I still don't get why make pick 3.fo even if 1.pdf is a valid
candidate. but, that's the fun part for me to find out in the source. :-)

> > 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.

thanks.  it's a first time to read make source even though I've been
using it a while. I'll dig in to that when I have a bit more of time.

best regards,
-- 
           yashi