Re: improvements for parallel makes ?

[Alexey Neyman]

Hi, there.

I updated the patch to apply against the make sources from CVS, but...
When I tried several more complicated test cases with .WAIT, it 
appeared that the patch misbehaves.

For example, the following Makefile:
<<<<
a: x1 .WAIT x2
b: x2 .WAIT x3
<<<<

when run with "make -j a b", starts the targets in the following 
order: x1 and x3 simultaneously, then, as both them are finished, x2.
Indeed, the ordering information cannot be stored only in the 
dependency chain.

Such information could be stored as a list of predecessors in 'struct 
file'. However, GNU make couldn't distinguish whether a predecessor 
has the 'cs_not_started' state because it is not going to be made at 
all or because the make just hasn't yet traversed the goal chain far 
enough.

The difference is in the ways GNU make and BSD make use to process the 
makefiles. Given a chain of command line goals, GNU make repeatedly 
traverses it (update_goal_chain() in remake.c), on each cycle 
starting the jobs that can be started. When a goal has been finished, 
it is removed from the chain. When the chain is empty (or any of the 
goals failed to be updated and no -k is given), the loop exits.

BSD make uses another approach.

First, each target has the following attributes (see GNode.h):
- 'children' (the list of targets this one depends upon)
- 'parents' (the list of targets that depend on this one),
- 'preds'/'successors' (like children/parents, but being a "truly
  order-only prerequisite"),
- 'make' (this target needs to be made),
- 'unmade' (number of unmade children)

Second, BSD make maintains a list of "runnable" targets (toBeMade in 
make.c).

Given a list of command line goals, make performs a complete top-down 
traversal of the dependency graph, even applying implicit rules 
(Make_Run() in make.c). Each target encountered is marked as "needs 
to be made", but only the terminal targets (those that have no 
prerequisites) are inserted into the toBeMade list initially.

Then, the job server (MakeStartJobs() in make.c) pulls the first 
target from the toBeMade list and checks if it has any predecessors 
that are marked as needing to be made, but have not been made yet. If 
it has, it just drops that target (it will be re-added to the 
toBeMade list later, see below) and pulls the next one. When a 
suitable target is found, a job is started to update it.

Later, when a job for a certain target finishes, make (MakeUpdate() in 
make.c) does the following:
- Checks parents of this target: decrements the 'unmade' counter of 
each parent, if this counter reaches zero, the parent target is 
inserted into the 'toBeMade' list
- Checks successors of this target: if a successor needs to be made, 
has no unmade children, has not been made already and is not already 
in the toBeMade list, it is inserted into that list.

Obviously, to implement the .WAIT behavior correctly, GNU make also 
has to perform the complete top-down traversal of the dependency 
graph upfront. Otherwise, it won't be able to check if the waiting 
behavior needs to be applied due to an implicit rule.

The question is whether such a change in GNU make behavior is welcome. 
Are there any underwater stones foreseen?

The change in behavior that I can predict is that the following 
makefile will no longer work:

<<<<
.SUFFIXES: .c .o

.c.o:
    gcc -c -fPIC $<

a.c:
    touch a.c b.c

x.so: a.o b.o
    gcc -o $@ -shared $^
<<<<

Currently, it works ok (run with "make -r x.so"). After such a change, 
it will be rejected (since 'b.c' is made as a side effect of 'a.c', 
and this make doesn't know this fact). But I'd say, such makefile 
could be considered broken anyway :)

If the maintainers say "go for it", I'll implement .WAIT in BSD-way.

Regards,
Alexey.

On Thursday 06 April 2006 12:57, Christophe LYON wrote:
> Alexey Neyman wrote:
> > Boris,
> > 
> > I'll refresh the patch as soon as I'll be able to; expect next 
> > week. 
> > 
> > Regards,
> > Alexey.
> > 
> 
> Sounds great!
> 
> If everyone is OK with it, do you think it would be 
reasonable/feasible 
> to issue a new official release so close after 3.81?
> 
> Christophe.
> 
> 
> 
> _______________________________________________
> Help-make mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-make
> 

-- 
Please do not try to stop us this time. We are firm in our resolve.
                        -- Pkunks, SC2