On Sun, 30 Dec 2018 09:53:50 +0100, Markus Wichmann <nullplan_AT_gmx.net> wrote:
> Maybe start with that. Make is a pretty simple algorithm: You build a
> dependency graph (which is a directed acyclic graph), then you find the
> target you are supposed to make (i.e. the first target or the command
> line arguments), rebuild its dependencies, then rebuild the target
> itself.
Keep in mind that if you invert the arrows in the DAG, parallelization becomes
trivial. You keep a reference count of "blocking jobs" for each entry, and
when a dependency is done, unblock the job. When the job is fully unblocked,
the depcount will drop to zero and you can enqueue it.
/* Set up the base case: Nothing is blocking building the leaves. */
for(l in leaves)
enqueue(q, l)
/* Do the build */
while(!count(q) != 0 && count(jobs) != 0){
/* Spin up as many jobs as our parallelism option allows */
while(count(jobs) < opt_maxjobs && count(q) > 0){
job = popjob(q)
pid = spawn(j)
addjob(jobs, pid, job)
}
/*
* We've spun up as many jobs as we can handle, wait for
* one of these to finish, and enable as many jobs as are
* blocked by it.
*/
pid = wait()
job = lookup(jobs, pid)
for(parent in job.parents){
unblock(parent)
if(blockers(parent) == 0)
enqueue(q, parent)
}
delete(jobs, pid)
}
There's a little bit of complexity in marking the dependencies of the
nodes you actually want to build, but not much -- just a recursive walk
of the targets that you want to build.
This approach is used for mbld (Myrddin's build system):
https://git.eigenstate.org/ori/mc.git/tree/mbld/build.myr
And when testing against ninja -- Michael Forney was kind enough
to supply some patches that would convert `.mbld` files to `.ninja`
files -- we were no slower than that build system. Not surprising,
since there's not much overhead in this approach. There's theoretically
room for improvement by ordering the dependencies more carefully, but
for most real world builds I doubt this will matter: C code depends
only on the direct inputs -- ie, the headers.
That being said, if we're talking about designing a new build system, the
interesting part of a new build system to me would be the approach taken to
correctly identifying dependencies. It's always annoying when a build is error
prone and fails to rebuild a .o file when a header it uses changes. GNU make
can deal with this, but it's clunky.
Another nice thing would be to output into an `obj` directory instead
of the current directory. This is something that BSD make does well.
(I've been tempted to modify mbld to build C code -- I don't think it would
be too hard -- but it seems like this is probably not something that'd
generate too much interest.)
--
Ori Bernstein
Received on Tue Jan 01 2019 - 05:47:51 CET