Proposal: Limiting concurrency on specific rules

[iannucci]

Hello all,

So for chromium, we're trying to move to using ninja with a distributed compilation solution. As such, we would like to do -j300, or something equally ridiculous. This actually works marvelously for compiles :). However, for links (which happen locally), this is a bit of an issue. 300 simultaneous links is actually unfriendly on the build machines' harddrives (as you might imagine).

We've tried implementing an out-of-ninja solution with mixed results (specifically, we built a tool to sit between ninja and the linker to take a system-wide mutex). This 'works' in the sense that ninja runs many compile steps, but only one link can happen at a time. However, this solution spawns a bunch of extra processes, and can artificially starve ninja (since it thinks that those jobs are doing something, not just hanging around). Plus, this is a single platform solution, the system mutex could potentially leak across build jobs (crashes, etc.), and this requires some extra shenanigans to set up the manifest.

I'd like to propose a simple addition to ninja make this all Better:

  * add an option to rules (max_concurrency), which specifies a uint32 maximum number of instances of this rule to run in parallel (default == 0 == unlimited)

  * in Plan, keep a map<Rule*, Set<Edge*> > stalled_, for all Rule's which have max_concurrency set

  * in Plan, whenever we would insert into ready, see if the to-be-added edge would cause more than edge.rule().max_concurrency edges to exist in ready_. If so, add it to stalled_[&edge.rule()] instead.

  * in Plan::EdgeFinished, if !stalled_[&edge.rule()].empty(), move a job from stalled to ready.

The state of how-many-of-this-rule-are-in-ready_ should probably also live in Plan as a map. I'd hoist all the ready_.insert's into a Plan::AddWork method (to mirror Plan::FindWork). 

What do you think?

If this sounds like a good plan, I'll implement and add a pull on github.

Cheers,

Rob

[Richard Geary]

This would be useful for my build, but I have 100's of binaries to link, some small and some large. Setting max_concurrency to a low number would slow the build too much. What would happen if I set max_concurrency to a build var and set an override on a build edge? It's not clear what that would mean.
Also you might still be running 299 compile units when you spawn the link.

Instead, I suggest adding a "resource" metric. The system would have -j# resources by default, with a -R# command line override. The resource consumed by an edge is 1 by default and could be overridden by setting a "buildcost" rule property or build edge override. Ninja could coordinate with a semaphore, and acquire the buildcost# number of resources whilst running the build edge.

Richard

Sent from my iPhone

[iannucci]

Hm... I can see the value in that. However, it strikes me as odd to have a single pool of 'resource' (some things may be cpu bound, some may be memory bound, disk I/O, storage space space, network bandwidth, etc.).

Maybe:

  * Each rule can specify a resource pool (some arbitrary string)

  * Each rule will additionally specify either:

    - a fixed amount of resource (i.e. some uint32)

    - a runnable which, when invoked, prints out the amount of resource consumed (the script would perhaps take the output path for that edge and all inputs for the edge as command line arguments). I'd like to implement some additional 'tools' inside ninja for the most obvious ones (probably memory proportional to the size of all inputs, and cpu cores).

  * When a rule is first able to be run (i.e. all inputs are satisfied), ninja runs the script (if present) and then caches the weight for that edge. The weight would be min(resource total, calculated amount) to avoid situations where ninja believes that there's not enough resource to build something.

  * A global maximum for each pool is specified in the manifest

  * The scheme I describe in the previous post still applies, except that instad of a map<Rule*, Set<Edge*> >, it's a map<pool, MinHeap<weight, Edge*> >, and then items would be conditionally moved to ready_ if enough resource are available for the top N items in the relavent heap.

It would an error to specify a pool without defining the maximum of that pool.

This approach would also help disparate rules (e.g. link and lib for dynamic and static linking respectively) to share the same resource pool.

I thought about allowing a rule to specify multiple pools and amounts (i.e. some amount of CPU and Memory), Unfortunately, I think that having a rule consume from multiple pools quickly starts to look like a knapsack packing problem or some derivative thereof :). Also, it seems like it might be overly complex and the benefit seems limited.

At no point would there ever be more than j jobs running. I suppose, if someone wanted to, they could use the resource pools system to fully spec the build, and then set j to infinity (is there a way to do that currently?). Theoretically, one could tune the build to get very-high utilization (dependencies permitting, of course).

Seem a little more plausible?

Robbie

[Elazar Leibovich]

Doesn't it make sense to manage everything outside ninja-build?

For instance, by wrapping ld with a script that locks an ipc semaphore before calling the real ld?

[iannucci]

I tried that in my first post :). It produces suboptimal results, as I mentioned. I think it can be done much better if handled within ninja.

Everything proposed in this thread would be optional (In the C++ sense of "you don't pay for it if you don't use it").

[Richard Geary]

Initially I thought multiple pools was a good extension, but since you mention the knapsack problem I'm not so sure. I think multiple pools might cause confusion; it would be difficult to quantify the values to enter for each build cost, and hard for ninja to optimize when to block & when to process a lighter cost task. A single resource pool would be simpler to implement, and we can tweak it later.

After talking with my colleage about this I should first explain my assumptions on the scheduler : I don't know how the ninja scheduler works currently, but I picture a "ready" list and the -jN threads will each pull the build item off the top of the list and push its dependents once it's complete. With a resource system, I thought that the "pull from the top" could be replaced by an iteration through the list to find the first task which could be completed with the available resources. However, I now realise this would always prioritize the cheapest tasks over the larger tasks. In effect, you would just run the available tasks in the order sorted by resource cost.

Mostly the problem resource is just memory (it would be very hard to quantify disk & network I/O). One issue not yet considered is the pagecache (the OS in-memory cache of files read/written to). At the moment, ninja will compile the object files & then link them together soon after. With a resource system, if the link step was expensive then compilations for all the files would complete before the linking would begin. The pagecache may have flushed the object files for the link by the time it runs, and the linker would take much longer as it has to read in the 10-1000Mb of object files from the disk. This effect could be reduced by forcing the scheduler to run large (high cost) tasks after they've been on the queue for an amount of time. But how long? Instead, if we forget about abstract resource pools and just talk in megabytes, we could count how much data has been read & written since the task was added to the queue, and then prioritize the larger tasks after MemTotal/2 (say) bytes have been processed.

Replying to your points 

 * I like the idea of an invoked command to compute build cost, that would be useful for quickly editing the cost measurement algorithm. 

 * The resource pool maximum should be a global vars (like builddir), set to a uint32 or a command to invoke. eg. I could invoke command "grep MemFree /proc/meminfo | awk '{print $2}' " to get the initial pool size

 * A maximum pool size of 0 should disable the resource checks

 * I get better utilisation by running -j8 on my 4 core box. This is probably as the intel compiler has to do a remote FlexLM license check on each compile. It may be useful to specify the number of logical threads separately from physical threads, with an ability to pin tasks to certain cores (eg. via taskset in linux)

Thanks,

Richard

[iannucci]

(I had a pretty sweet reply, but google groups ate it >_<. This is the condensed version... sorry if it seems terse!)

Let me rephrase the knapsack thing: Multiple pools with rules consuming from a single pool is OK. Multiple pools with rules consuming from multiple pools is chaos. :) I actually think the multi-pool-single-consumption approach would not be difficult to implement quickly/efficiently, and is a superset of the single pool way of doing things.

I'm very new to the ninja codebase, but from what I see, it looks like there's a single ready_ queue which has jobs added to it as edges finish (when those finished edges cause said jobs to be 'ready'). The multi-pool approach I described previously would work by delaying job insertion into that queue until there's enough 'resource' left to add an item from that queue. As items with that resource complete, the delayed jobs for that resource are re-evaluated to see if they'll fit in the ready queue.

I think adding a parameter to each pool (e.g. "max_delay") would solve the starvation issue 'well enough' by enqueuing jobs when EITHER: 1) they've waited more than 'max_delay' opportunities to be enqueued (so if there's a link pool, a rule which consumes from the link pool will be automatically enqueued regardless of weight after "max_delay" link-pool-consumers have completed), or 2) there's enough resource left to enqueue them. I believe if cache invalidation is a concern, a low number here would alleviate that.

I also wanted to point out that things like disk IO or network aren't that hard to quantify if you know the behavior of the tool. For example, you may know that a rule is very disk-heavy, and so you only want one of it to run at a time, no matter what (pool size 1, weight 1). Or you know that a rule can eat roughly a quarter of the available bandwidth (pool size 4, weight 1).

Additionally, resources don't have to precisely reflect any 'real' units. You could create a link pool of, say, 6, and then assign weights of 1, 2, and 4. This will ensure that no more than 1 massive link happens at a time, but will also help keep the 'tiny' links from filling up the queue first (since the weights are much more granular than an actual memory consumption estimate).

I think direct estimation or modeling of the page cache will be difficult/impossible, especially considering that it's implemented totally differently across platforms, and that non-ninja governed tasks can easily nuke it too. I'm thinking that it may also be prudent to buy more memory in a case like this (I think 64GB of memory runs at about $300 these days, which is enough to keep virtually all of chromium (inputs as well as outputs) in memory). I'm not sure about your particular task, but I'm assuming more memory won't hurt :) Also, I think implementing a max_delay like I mentioned above will also help with locality issues like this.

I was also wondering if additionally sorting edges by their indegree/outdegree might be useful. That way ninja could decide between, say, two big links, one which produces a single terminal output, and one which produces an output which enables many subsequent tasks (thus running more edges more quickly).

Rob (again, I apologize for the brevity)

P.S. Ninja is single-threaded :)

[Evan Martin]

On Thu, Sep 13, 2012 at 5:54 PM, iannucci <iann...@chromium.org> wrote:
> I'd like to propose a simple addition to ninja make this all Better:

Thanks for writing this up. We have talked about this a few times in
the past but have always gone in circles about how complicated to make
it.

I think the linking problem is always the example (and we haven't had
many (any?) others), so solving it directly is a good first step.

One higher-level problem to consider: there are potentially multiple
different Ninja rules that are all conceptually "link" steps. Like in
Chrome's build there's link, solink, solink_module. The idea of
string-identified resource pools is appealing to me but then there's
not an obvious place to specify what the concurrency limit of a given
resource pool is.

> * add an option to rules (max_concurrency), which specifies a uint32
> maximum number of instances of this rule to run in parallel (default == 0 ==
> unlimited)

int is fine here.

> * in Plan, keep a map<Rule*, Set<Edge*> > stalled_, for all Rule's which
> have max_concurrency set

I guess a queue is better than a set, maybe?

> * in Plan, whenever we would insert into ready, see if the to-be-added
> edge would cause more than edge.rule().max_concurrency edges to exist in
> ready_. If so, add it to stalled_[&edge.rule()] instead.
> * in Plan::EdgeFinished, if !stalled_[&edge.rule()].empty(), move a job
> from stalled to ready.
>
> The state of how-many-of-this-rule-are-in-ready_ should probably also live
> in Plan as a map. I'd hoist all the ready_.insert's into a Plan::AddWork
> method (to mirror Plan::FindWork).

Multiple parallel maps from Rule* to dynamic state about the Rule
makes me wonder whether it's worth making a data structure
(RuleRunState or something) that includes both the stalled edges and
the currently-running count.


This all sounds pretty good to me, my only last point is to encourage
you to write lots of tests. I frequently develop features in Ninja by
first making tests pass and then verifying it actually does what I
want. This has allowed us to be fairly aggressive when making
changes. (The high-level build scheduling stuff is sadly weak in the
testing department, though>)

[Evan Martin]

On Fri, Sep 14, 2012 at 10:41 AM, Richard Geary <richar...@gmail.com> wrote:
> After talking with my colleage about this I should first explain my
> assumptions on the scheduler : I don't know how the ninja scheduler works
> currently, but I picture a "ready" list and the -jN threads will each pull
> the build item off the top of the list and push its dependents once it's
> complete.

That's pretty much right, except the list is unordered (effectively we
pull a task at random).
See some more discussion here:
https://github.com/martine/ninja/issues/232
(It's kind of an orthogonal issue to the topic at hand.)

[iannucci]

Ok, so is your feeling that I should implement the 'simple' version first (that is, one pool-per-rule, all edges in a pool consume a single resource from that pool while running), and then re-raise the discussion about sharing pools across rules afterwards?

Queue would be better (I just copied the signature of ready_ :)). I agree that there's probably the opportunity for a better data structure for the delayed rules. I was assuming that would become more obvious as I got into the implementation. I'm thinking this can be implemented without any significant algorithmic overhead (possibly some map lookups, but even that is probably not necessary if rules pre-allocate themselves an index into a vector of queues that the Plan keeps). Maybe the RuleRunState could look something like: vector< pair<int, deque<Edge*> > >, and the index is always Edge.rule().run_state_index. Int in the pair is the amount of that resource in ready_. Probably don't want the raw stl type though, for readability.

Tests sound like an excellent idea :)

Rob

[iannucci]

Or rather a regular queue instead of a deque. We should never need to iterate over it.

[Evan Martin]

On Fri, Sep 14, 2012 at 2:53 PM, iannucci <iann...@chromium.org> wrote:
> Ok, so is your feeling that I should implement the 'simple' version first
> (that is, one pool-per-rule, all edges in a pool consume a single resource
> from that pool while running), and then re-raise the discussion about
> sharing pools across rules afterwards?

Or if you have good ideas about how to make something more complicated
work now, do that too.
I guess I'm more interested in solving the problems we've observed
than hypothetical future ones, but I'm concerned that the simple
per-rule pool won't be enough for Chrome.

> Queue would be better (I just copied the signature of ready_ :)). I agree
> that there's probably the opportunity for a better data structure for the
> delayed rules. I was assuming that would become more obvious as I got into
> the implementation. I'm thinking this can be implemented without any
> significant algorithmic overhead (possibly some map lookups, but even that
> is probably not necessary if rules pre-allocate themselves an index into a
> vector of queues that the Plan keeps).

All of these structures are O(number of build steps), which is ~10k
even for big projects, and we only need to index into them relatively
rarely (as build edges start and finish). At those scales even linear
scans are probably fine, what's more important is that the code is
simple.

[iannucci]

I think sharing pools across rules could be implemented simply. Having a good place to put the pool maximums in the manifest would be the main issue.

It seems like doing shared pools with an edge weight of 1 should be the first step, and then adding a way to have non-unit edge weights later. I'll try to keep non-unit edge weights in mind as I implement the first version, too. Once the first version is out, people can play with it and see if it's mostly good, or if it badly needs different weights.

Having script-based edge weights is tricky... running the scripts would have to be done as some new sort of virtual edge so that ninja doesn't block, which sounds non-trivial, so I'd be happy to not do that right away. Another possibility would be to have each edge manually specify it's weight in the manifest, which would be simpler for ninja to deal with (and now that I wrote it down, makes a lot of sense, since the edge weights don't need to change between builds without a manifest change. We don't want to have to calc the weights on every build).

Good point on the complexity emphasis... simple code that works is the right place to start.

R

[Nico Weber]

I've only skimmed this thread. Two points:

* It'd be great if whatever you come up with could help with the
compilation of V8DerivedSourcesNN.cpp in webkit. That's ~18 generated
cpp files that all need hundreds of MB of ram and a lot of cpu to
build, and they are all built in parallel. On systems with not much
ram, they cause the machine to swap. (Note: This is compilation, not
linking.) If your approach can handle this, how would it be deployed?
Would we have to tag these files manually in our meta build system
(gyp), or…?

* At least in chromium, linking works fairly well as is, with the
single lock. Several folks have measured if being smarter about this
lock helps, and the answer was always "not really".

Nico

[iannucci]

That's a good use case. I'll have to think about how to incorporate that into

the design. In the current proposal the resource pool is specified per-rule,

so there's no provision for applying the restriction on a per-edge basis. If we

did edge-specified weights, that would permit what you're talking about (all

edges would be weight of 0, except for these troublesome ones which 

could have a weight of 1). That specification would happen in the metabuild

layer.

I was looking at ninja+goma builds on windows, and it seems that the mutex

is much too restrictive. Informally, I saw a big total speedup with a lock count

of 2 (with msbuild), because the second link could allow additional dependent

steps to execute during some of the big links.  I think sorting by outdegree

could also help a lot here. The benefits of a lock degree of 3+ did have rapidly

diminishing returns.

R

[iannucci]

Ok, looks like the comments have died down :). Here is my current proposal for the first version I plan to implement. Keep in mind that all of this will be optional, so current ninja configs are 100% compatible (syntactically and semantically).

I'll add a global section type called pool. It will look like:

pool <name>

  maximum = <number>

  # In the future, other options can go here, like

  # fifo = <bool>  # order jobs with a queue, or order with a priority queue (default)

  # starvation_limit = <number> # forces edges to schedule after this many opportunities

  # override_global_limit = <bool> # in the current version, everything still obeys j. This could let a pool operate outside of that limit.

I'll add the following optional settings to rule:

rule <name>

  ...

  default_pool = <name>

  default_pool_consumption = <number>

I'll add the following optional syntax to build (overrides pool and/or units for this edge's rule). If there is a better way to do this, please comment:

build[<pool name>](<consumption>) ...

The implementation logic will be:

• Each pool will be implemented as a priority queue, ranked by increasing weight followed by decreasing outdegree (to favor jobs that will lead to more jobs) followed by the value of this.
• A job will run as soon as there is enough resource to run it. This could lead to big jobs being delayed for a while (but not indefinitely. Unlike an OS scheduler, there is an end state for this system).
  
• If an edge would otherwise be 'ready', check to see if its pool has enough resource to run it. If not, queue/push it onto the pool.
  
• When an edge finishes, see if one or more edges can be added to the ready queue from this current edge's pool.
  
• Edges without pools will be scheduled normally.

I anticipate that sizeof(Edge) will increase by sizeof(int)+sizeof(void*) (weight + pool_ptr).

Unless there are any major objections, I'd like to start implementing this straight away (I think some of the unit test infrastructure will have to be beefed up, too, and including that, I'd like to get this done quickly :)).

R

[iannucci]

It occurs to me that I may have to store the pool name instead of the actual pool pointer in Edge to maintain separation of state.

[Evan Martin]

Here are some ideas on how to simplify it.

1) You can use one variable name to specify the pool in all contexts:

rule cc
pool = foobar

build bar: cc blah # uses foobar pool, inherited from "cc"
build bar2: cc blah2
pool = foobar2 # uses foobar2 pool

At edge evaluation time, evaluating "pool" will either get the value
set in the build block, or fall back on the rule value. You can also
set pool to the empty string to effectively unset it.

See the discussion of variable shadowing here (and linked from there):
http://martine.github.com/ninja/manual.html#_build_statements

2) Rather than extend the syntax with a pool statement, here's a hacky
way to keep the change smaller -- put the pool depth in the pool name.
It won't work for extending to those other ideas but we're not sure
we need them yet and we still can add them via your syntax if
necessary.

rule cc
pool = foobar/10 # the /10 means "10 slots total"
# perhaps default to a depth of 1 if there's no /X ending

rule cc_other:
pool = foobar/10 # must match the other name to share the same pool

It's maybe fragile in that if you typo a name they don't share a pool
but this is also a pretty obscure corner where it's unlikely you'll
ever need more than one or two pools.

3) Regarding consumption: make 1 the default, so it can be left unspecified.
In fact, until someone needs it maybe just don't include it at all.

4) It might make sense to put all jobs that don't name a pool
specifically into some "default" pool that has unlimited depth. This
might simplify the code related to scheduling since everything comes
from a pool.

5) I would skip the priority queue stuff for now. We experimented
with different orderings of builds in Chrome a while back and found
they had counterintuitive effects on end-to-end build time; it'd be a
pain if your pool patch was good but ended up regressing performance
just because you changed how builds were ordered.

That is to say, I think it'd be neat to experiment with priority
ordering in Ninja, I just think you should keep it separate so that we
can measure its effects separately.

[iannucci]

On Monday, September 17, 2012 3:43:27 PM UTC-7, Evan Martin wrote:

Here are some ideas on how to simplify it.

1) You can use one variable name to specify the pool in all contexts:

rule cc
  pool = foobar

build bar: cc blah  # uses foobar pool, inherited from "cc"
build bar2: cc blah2
  pool = foobar2   # uses foobar2 pool

At edge evaluation time, evaluating "pool" will either get the value
set in the build block, or fall back on the rule value.  You can also
set pool to the empty string to effectively unset it.

See the discussion of variable shadowing here (and linked from there):
http://martine.github.com/ninja/manual.html#_build_statements

Perfect... I somehow forgot about variable shadowing...

 

2) Rather than extend the syntax with a pool statement, here's a hacky
way to keep the change smaller -- put the pool depth in the pool name.
 It won't work for extending to those other ideas but we're not sure
we need them yet and we still can add them via your syntax if
necessary.

rule cc
  pool = foobar/10   # the /10 means "10 slots total"
  # perhaps default to a depth of 1 if there's no /X ending

rule cc_other:
  pool = foobar/10   # must match the other name to share the same pool

It's maybe fragile in that if you typo a name they don't share a pool
but this is also a pretty obscure corner where it's unlikely you'll
ever need more than one or two pools.

Hmm.. this strikes me as a bit risky. I suppose since ninjafiles are supposed to be generated anyhow, this isn't too bad.

This is definitely pretty hacky though ;)

 

3) Regarding consumption: make 1 the default, so it can be left unspecified.
In fact, until someone needs it maybe just don't include it at all.

default sgtm.

4) It might make sense to put all jobs that don't name a pool
specifically into some "default" pool that has unlimited depth.  This
might simplify the code related to scheduling since everything comes
from a pool.

Maybe. If the pool has unlimited depth, the pool's queue and count tracker will be allocated and updated, but never used. I'll keep this in mind as a possible patch minification.

 

5) I would skip the priority queue stuff for now.  We experimented
with different orderings of builds in Chrome a while back and found
they had counterintuitive effects on end-to-end build time; it'd be a
pain if your pool patch was good but ended up regressing performance
just because you changed how builds were ordered.

That is to say, I think it'd be neat to experiment with priority
ordering in Ninja, I just think you should keep it separate so that we
can measure its effects separately.

Ok.

So the first whack will allow pool specification per-edge (with a per-rule default), which essentially allows a per-edge weight of 0 (no pool/default pool) or 1 (part of a pool)

I'll make specifying the same pool with different /depths an error.

Afterwards, if people need it, I'll propose a weighted pool approach with potentially different queuing mechanisms.

R

[Nico Weber]

How will generators know when to add this / what to set depths to?

[Robert Iannucci]

I wasn't explicitly thinking about making changes to gyp for this.
Since the syntax change is minor, I was assuming that gyp could
already accomplish it. However, since I'm planning on using chromium
build as my benchmark, I will be making any necessary changes to gyp
in order to produce the ninja files if I find that it's not capable of
producing them already.

In it's simplest form, this will just be one extra line which is added
to a ninja rule (I'm certain gyp can do this already, and if not, it's
a trivial addition). In it's more sophisticated from (i.e. for your
use case with a handful of known-bad compiles), there should be a way
in gyp already to add shadow variables to particular build steps
(though I haven't investigated/confirmed this). If that functionality
doesn't exist in gyp, it should be easy to add.

The correct depths will need to be investigated by a human running
benchmarks, probably. Those values will likely be a function of memory
and/or cpu available, which could be calculated at gyp time.

Or were you asking a different question?

R

[iannucci]

Pull request is up for those who care: https://github.com/martine/ninja/pull/461