Re: Prioritizing non-dependent targets in parallel make

[Tim Murphy]

Hi,

I'm nobody official.  I have seen Electric Accelerator using history
files which may be doing something a bit like this.

Personally I don't like the idea of priorities very much.  Large
builds that I have done do have big targets but since we are building
5000 of the same kind of target (using a macro to define a generic
template and $eval to instantiate it for each specific target) it
becomes impossible for us to provide hints.  In the end we'd have to
force the users of our build system say  "webkit.dll" is pretty huge
or  "euser.dll" isn't.  Since this is all relative information, how
can we expect a build made up of components that various people
produce to have the right "relative" weights?

So I, personally, want something that learns.  I would like to be able
to store the learned information into source control and use it as the
basis for the next attempt.  One would have to check for patents on
this, I think.

Regards,

Tim

2009/12/24 tom honermann <address@hidden>:
> I'm working on optimizing our GNU make based build system to reduce build
> times.  Consider the
> following dependencies with these run times for each target:
>
>   A:       # 3 minutes
>   B: C D   # 1 minutes
>   C:       # 1 minutes
>   D:       # 1 minutes
>   E:       # 6 minutes
>
> There are many valid orders in which the targets can be built.  When make
> is invoked with the parallel execution (-j) option, the order in which the
> non-dependent targets are scheduled has a significant impact on the total
> run time.  Consider the following schedules for the above dependencies.
> (View with a fixed width font if the tables don't line up properly)
>
> +------+-------------+    +------+-------------+
> | Time | Jobs (-j 2) |    | Time | Jobs (-j 2) |
> +------+------+------+    +------+------+------+
> |    0 |    A |    C |    |    0 |    A |    E |
> |    1 |    A |    D |    |    1 |    A |    E |
> |    2 |    A |    B |    |    2 |    A |    E |
> |    3 |    E |      |    |    3 |    C |    E |
> |    4 |    E |      |    |    4 |    D |    E |
> |    5 |    E |      |    |    5 |    B |    E |
> |    6 |    E |      |    |    6 |      |      |
> |    7 |    E |      |    |    7 |      |      |
> |    8 |    E |      |    |    8 |      |      |
> +------+------+------+    +------+------+------+
>
> The table on the left illustrates a worst-case schedule (9 minutes) and the
> one on the right illustrates a best-case schedule (6 minutes).  The
> difference
> in build times is 30%.
>
> Clearly, make can't be expected to know how long each target will take to
> complete, so any scheduling hints for make would have to be specified in
> the Makefile (or learned from prior runs).  As far as I can tell, GNU make
> doesn't have any features that enable the Makefile author to provide
> scheduling hints.
>
> I am interested to know what others have done to optimize their Makefiles
> for parallel execution.  Has anyone worked on enhancements to GNU make that
> would allow some targets to be prioritized over others (without introducing
> strict dependencies)?
>
> If no prior effort has been made to support target prioritization, I have a
> few proposals for how such support might be added to GNU make.  I don't have
> any insight into the effort required to implement these however.
>
> GNU make has a syntax for order only prerequisites.  A similar extension
> could be used to define relative priorities between targets.  The following
> syntax would specify that the PRIORITY-PREREQUISITES should be started
> before
> building TARGETS.  Naturally, specifying priority prerequisites would have
> no effect in non-parallel make invocations.
>
>   TARGETS : NORMAL-PREREQUISITES | ORDER-ONLY-PREREQUISITES ^
> PRIORITY-PREREQUISITES
>
> Alternatively, priority levels could be specified using a numeric system and
> a syntax similar to the vpath directive.
>
>   priority LEVEL TARGETS
>
> For the dependency example above, the following directives would ensure an
> optimal build schedule.  (for the priority directive example, lower numbers
> have higher priorities, default priority is 0)
>
>   C D B: ^ A E
>
>   priority -1 A E
>
> Comments?
>
> Tom.
>
>
> _______________________________________________
> Bug-make mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/bug-make
>



-- 
You could help some brave and decent people to have access to
uncensored news by making a donation at:

http://www.thezimbabwean.co.uk/