Re: Prioritizing non-dependent targets in parallel make

[tom honermann]

On 12/24/2009 7:16 AM, Paul Smith wrote:
> You can already completely control the order in which targets are
> invoked, even when using -j.
>
> At all times, make will try to build prerequisites starting with the
> first one in the prerequisite list, and continuing in order to the last
> one in the list.
>
> Invoking a parallel make does not change this algorithm, the ONLY thing
> it does is control how many jobs can be "in flight" at the same time.
>
> So, if you list your prerequisites in order with the longest ones first
> and the shortest ones last, then you will get the distribution you want.
>   
I rather suspected this was the case, but I couldn't find the behavior 
documented in the make
manual and was thus reluctant to rely on it.  Is this considered 
designed in behavior that is
unlikely to change?  If so, perhaps it could be documented?

Also, this may be the intended behavior, but I am seeing cases where 
make is not behaving like
this.  Here is an example Makefile and output from a 'make -j 3' run on 
an 8 core Linux x86_64
system.  GNU make version is 3.81.

### Begin Makefile
all: $(addsuffix .resolved, a b c d e f g h i j k l)

%.resolved: %.objects
       @echo "$@ started - `date`"
       @sleep 1
       @echo "$@ finished - `date`"

%.objects: objects_prereqs
       @echo "$@ started - `date`"
       @sleep 2
       @echo "$@ finished - `date`"

objects_prereqs:
       @echo "$@ started - `date`"
       @sleep 1
       @echo "$@ finished - `date`"

a.resolved: $(addsuffix .resolved, e)
b.resolved: $(addsuffix .resolved, c d e)
d.resolved: $(addsuffix .resolved, l)
f.resolved: $(addsuffix .resolved, c j k)
#### End Makefile

#### Begin output: make -j 3
objects_prereqs started - Mon Dec 28 17:44:24 PST 2009
objects_prereqs finished - Mon Dec 28 17:44:26 PST 2009
a.objects started - Mon Dec 28 17:44:26 PST 2009
c.objects started - Mon Dec 28 17:44:26 PST 2009
e.objects started - Mon Dec 28 17:44:26 PST 2009
a.objects finished - Mon Dec 28 17:44:28 PST 2009
c.objects finished - Mon Dec 28 17:44:28 PST 2009
e.objects finished - Mon Dec 28 17:44:28 PST 2009
l.objects started - Mon Dec 28 17:44:28 PST 2009
d.objects started - Mon Dec 28 17:44:28 PST 2009
b.objects started - Mon Dec 28 17:44:28 PST 2009
d.objects finished - Mon Dec 28 17:44:30 PST 2009
l.objects finished - Mon Dec 28 17:44:30 PST 2009
b.objects finished - Mon Dec 28 17:44:30 PST 2009
j.objects started - Mon Dec 28 17:44:30 PST 2009
k.objects started - Mon Dec 28 17:44:30 PST 2009
f.objects started - Mon Dec 28 17:44:30 PST 2009
j.objects finished - Mon Dec 28 17:44:32 PST 2009
k.objects finished - Mon Dec 28 17:44:32 PST 2009
f.objects finished - Mon Dec 28 17:44:32 PST 2009
g.objects started - Mon Dec 28 17:44:32 PST 2009
h.objects started - Mon Dec 28 17:44:32 PST 2009
i.objects started - Mon Dec 28 17:44:32 PST 2009
g.objects finished - Mon Dec 28 17:44:34 PST 2009
h.objects finished - Mon Dec 28 17:44:34 PST 2009
i.objects finished - Mon Dec 28 17:44:34 PST 2009
e.resolved started - Mon Dec 28 17:44:34 PST 2009
c.resolved started - Mon Dec 28 17:44:34 PST 2009
l.resolved started - Mon Dec 28 17:44:34 PST 2009
e.resolved finished - Mon Dec 28 17:44:35 PST 2009
c.resolved finished - Mon Dec 28 17:44:35 PST 2009
l.resolved finished - Mon Dec 28 17:44:35 PST 2009
j.resolved started - Mon Dec 28 17:44:35 PST 2009
k.resolved started - Mon Dec 28 17:44:35 PST 2009
g.resolved started - Mon Dec 28 17:44:35 PST 2009
j.resolved finished - Mon Dec 28 17:44:36 PST 2009
k.resolved finished - Mon Dec 28 17:44:36 PST 2009
g.resolved finished - Mon Dec 28 17:44:36 PST 2009
h.resolved started - Mon Dec 28 17:44:36 PST 2009
i.resolved started - Mon Dec 28 17:44:36 PST 2009
a.resolved started - Mon Dec 28 17:44:36 PST 2009
h.resolved finished - Mon Dec 28 17:44:37 PST 2009
i.resolved finished - Mon Dec 28 17:44:37 PST 2009
a.resolved finished - Mon Dec 28 17:44:37 PST 2009
d.resolved started - Mon Dec 28 17:44:37 PST 2009
f.resolved started - Mon Dec 28 17:44:37 PST 2009
d.resolved finished - Mon Dec 28 17:44:38 PST 2009
f.resolved finished - Mon Dec 28 17:44:38 PST 2009
b.resolved started - Mon Dec 28 17:44:38 PST 2009
b.resolved finished - Mon Dec 28 17:44:39 PST 2009
#### End Output

Please forgive this relatively complicated example.  Given your 
description, I would expect make
to focus first on completing a.resolved.  Doing so requires building the 
following targets:

objects_prereqs
e.objects
a.objects
e.resolved
a.resolved

While building the above 5 targets, make is free to build other targets 
- next in line would be
b.resolved and its prerequisites - which make starts to build.  The 
problem is make doesn't seem
to be coming back to finish the prerequisites of a.resolved when I would 
expect it to.

I put the above output into a table below (view with non-proportional 
font) that, I hope, is a fair
representation of the job slots that make may have used for this test.

+------+-------------------------------------------+
| Time |                Jobs Slots (-j 3)          |
+------+--------1--------+-----2------+-----3------+
|    0 | objects_prereqs |            |            |
|    1 | a.objects       | c.objects  | e.objects  |
|    2 | l.objects       | d.objects  | b.objects  |
|    3 | j.objects       | k.objects  | f.objects  |
|    4 | g.objects       | h.objects  | i.objects  |
|    5 | e.resolved      | c.resolved | l.resolved |
|    6 | j.resolved      | k.resolved | g.resolved |
|    7 | h.resolved      | i.resolved | a.resolved |
|    8 | d.resolved      | f.resolved | b.resolved |
+------+-----------------+------------+------------+

Note that objects_prereqs, e.objects, and a.objects were all completed 
by the start of time 2.  However,
make still waited until time 5 to start e.resolved and continued 
building the remaining .objects targets instead.
The building of a.resolved was further delayed until time 7.

In at least this example, placing "high priority" targets earlier in 
prerequisite lists does not seem to help
get make to schedule them earlier.

Tom.