On Sun, 30 Dec 2018 09:53:50 +0100, Markus Wichmann <nullp...@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