Repository navigation
achive better parallelism when building deps #5014
Description
Note: this is an oversimplified example.
Lets say my crate dependencies are like this:
A -requires-> B , C
B -requires-> D , E
A
├── B
C ├── D
E
I noticed that cargo would build C and D or E in parallel and then build B in the end and then A.
It would be smarter to realize that we can build D and E in parallel and then B and C in parallel.
before:
| core1 | core2 |
|---|---|
| C | E |
| D | |
| B | |
| A |
suggested:
| core1 | core2 |
|---|---|
| E | D |
| C | B |
| A |
The current behaviour also happens when forcing code gen units to 1.
Activity
alexcrichton commentedon Feb 6, 2018
Indeed! Right now there's no heuristics for "what crate to schedule next", and this sounds like an excellent heuristic to me. The logic would go around here
lukaslueg commentedon Feb 7, 2018
We can do that using Hu's scheduling algorithm. This assumes that all packages take an equal amount of time to compile; that is never true, yet the best bet we can make. We'd be required to compute the path length from the top package to the ready-to-be-scheduled packages, which in turn we can do using a simple topological sort (the
DependencyQueueis guaranteed to never have cycles, right? Right?).As far as I can see we would currently need to recompute that for every call of
dequeuebecauseDependencyQueueis designed to be mutable while jobs are being dequeued (that is, we currently do not pre-compute a definite job schedule ahead of time).I'm wondering if the added complexity in
dequeue()were to be considered worth it. The runtime-cost of doing a topological sort of the dependency-queue for every call todequeue()is probably very small.alexcrichton commentedon Feb 7, 2018
@lukaslueg sounds plausible to me! We could actually estimate the cost of a crate via the size of all its input files probably as well if we wanted to go a bit further. In any case the
DependencyQueuebasically hasn't changed since it was first added to Cargo, and IIRC it's not optimized at all and is already doing a bunch of liner things on each call todequeuealready, so adding more probably can't hurt!And yeah AFAIK there are no cycles there.
Auto merge of #5100 - alexcrichton:better-dep-ordering, r=matklad