New make --shuffle mode
trofi.github.io
trofi.github.io
It was/is a clever combination of remotely running jobs, understand the Makefile DAG of what needs to be built and observing file system accesses to detect when the DAG doesn't reflect the files that are actually accessed (and therefore cause parallelism problems).
The initial version was built by a small group of people led by me and John Ousterhout.
Electric Make is the large scale makefile maintainers dream basically. You're not going to get that much out of it for a small linux package but once you have a build that can manage a lot of parallelism it makes life easy. It makes your build run across a cluster of machines but presents a filesystem on each machine that makes your build think it's on one computer. It has a filesystem module that does this and which also perfectly spots all your dependencies even when they're not C or C++ header files - just any file that got used when a target was being made.
It's so smart that it spots parallelism issues as they happen and reruns everything in the correct ordering that they would have got run in if the build was running on a single core - so it can make horrible old makefiles work properly in parallel without you needing to update them. It remembers what happened so that it gets everything right first time in the next build.
It remembers what build times things had and schedules longer items earlier. Its dependency mechanism lets it cache build objects with great certainty that you'll never pull a stale item out of a the cache.
And the icing on the cake is that it has a visualisation tool that lets you look at your build across all CPUs/computers and see almost at a glance why it is slow and how to fix it.
It's just the last word. But it is not free at all and again my opinion is that it's mostly going to pay off on larger builds. I also think that if you're building something where the developers take build time very seriously and fix problems a lot then it won't help as much.
"Thy build shall be nondeterministic!" is quite a curse to spring on someone :)
For new development, however, a nondeterministic default ensures no one relies on accidental behavior and is good practice. Golang did this with the order of traversing a map and it's wonderful in practice - if you want to depend on an ordering, sort it yourself.
Backwards compatibility is one of the most important things to do to keep people using your product - if I have to debug and change my code to use version 2 of your product, it's not much more work to switch to a competitor. It's also incredibly difficult to deliver backwards compatibility and requires intentional planning in advance.
That all but ensures nobody will care then. Performance is, sadly, not a big motivator in most projects.
Both could be satisfied with a single-threaded make keeps the standard order to ensure backwards compatibility, but `make -j` that also turns on --shuffle. Which is also backwards compatible, because timing of each target might rearrange them.
The worst problems are when nobody realises that a parallelism issue has happened and the binary for some tool on your phone OS gets generated from the old rule instead of the new one and it's just an invisible random bug. Not sure shuffling would help that exact problem of course.
It was pretty smart - I suspect you could write a really crappy makefile and coast.
this was probably 20 years ago.
I did this sort of thing brute force once with a script that used find on a build output to make a big list of all the build artifacts, and then did in effect foreach target in artifacts ; make clean ; make target. Took forever of course, but the set of failed targets is a list of every single target with a missing dependency.
Do I miss something or is this impossible short of duplicating the goals?
E.g., suppose you have goals a, b and c, which are independent and you want to define another goal d which runs first a, then b then c.
My first idea was to define additional goals to capture the dependency structure, like this:
d: x2 c
x2: x1 b
x1: a
But then nothing is stopping the shuffler from running c, b, a, x1, x2, d.
The only solution I see would be to copy the shell commands of b and c into new goals:
d: xc
xc: xb; <shell commands of c>
xb: a; <shell commands of b>
Which seems really unsatisfying.
Is there a better way?
d: a b c
With shuffle, a, b, and c could be made in any order, but you are guaranteed d would be after all of them.
This helps to enforce that a, b, and c are actually independent. If they are not, there is a chance your build will fail. This can happen sometimes when rules get complex and there become hidden dependencies between rules. For example, maybe one target, which always happens to run first, creates a directory that other targets rely on, but those targets would not create that directory if they were run first.
That is the impetus behind this new flag. It would (maybe) expose that there is a hidden dependency on that directory, and it could be made into its own dependency for a, b, and c to depend on, so that it doesn’t matter which runs first.
It might be that `make` is the wrong tool for the job here, but I'm not sure what job you're trying to accomplish. You might be having an XY problem.
I could see it make sense for some "generic" goals which have different dependencies depending on the context they are called. E.g. a "package" goal requiring that something is there to package, but what is there might depend on the top-level goal.
But I agree, this is a bit of a misuse of goals - and definitely the direction that ultimately leads to some makefile from hell when this is invariably overdone.
Do they?
> Otherwise OP wouldn't be able to break so many builds with the --shuffle option.
That's not what I took away from OPs post.
My reading is that a lot of people have goals that they think are independent, but contain hidden dependencies that they'd just not considered. Or, they have goals which have dependencies that were introduced after the makefile was written, and the makefile hasn't caught up yet.
i.e. they don't want "build a then b then c", they want "build a and b and c together if that's at all possible (because I have 48 cores and only a single-threaded compiler) but not if it isn't" - and they just haven't correctly specified what should be possible.
Having thought a bit more, you could do your original request with the following stanza:
d:
make a
make b
make c
Regardless: I haven't tried it yet, but I saw in a changelog that a recent version of make added .WAIT, which sounded like it does what you want.
THIS_FILE := '$(lastword $(MAKEFILE_LIST))'
d:
$(MAKE) -f $(THIS_FILE) a
$(MAKE) -f $(THIS_FILE) b
$(MAKE) -f $(THIS_FILE) cIt's better to leave the whole dependency tree in the same makefile by not having a make subprocess, then let make do its dependency magic correctly with full information, enabling -j to get a parallel build.
Maybe make is able to do some magic to avoid this problem since it has some some kind of process management, at least for dealing with "-j" properly in recursive Makefiles. I doubt it though.
I'm having trouble thinking of a case where it would be useful to do so.
FORCE:
a b c d: FORCE
run-a && run-b && run-c && run-d FORCE:
a: FORCE
run-a && run-b && run-c && run-d
b: FORCE
run-a && run-b && run-c && run-d
c: FORCE
run-a && run-b && run-c && run-d
d: FORCE
run-a && run-b && run-c && run-d a b c d &: FORCE
...
[1] https://www.gnu.org/software/make/manual/html_node/Multiple-...
> In QuickCheck, assertions are written about logical properties that a function should fulfill. Then QuickCheck attempts to generate a test case that falsifies such assertions. Once such a test case is found, QuickCheck tries to reduce it to a minimal failing subset by removing or simplifying input data that are unneeded to make the test fail. -- https://en.wikipedia.org/wiki/QuickCheck
People drive me crazy with Makefiles that hide almost everything, and with no "verbose" option. Sure, it looks nicer when things go right, but when it doesn't, which is the main reason why logs exist, then it is terrible. I always have to use ugly tricks to reveal what the Makefile author has hidden from me, like using the shell "-x" option, or removing all the '@' with a sed command, if would have been so much easier having a command line option.
Good thing we are mostly using cmake now, it has a working VERBOSE flag, but still, manual Makefiles still exist, and they are usually pretty terrible, and that would be a nice option to help debugging these terrible Makefiles (not unlike --shuffle).
> Prints the recipe to be executed, even when the recipe is normally silent (due to .SILENT or ‘@’). Also prints the makefile name and line number where the recipe was defined.
From the manual, which is excellent: https://www.gnu.org/software/make/manual/html_node/Options-S...
SHELL=‘/bin/bash -vx’
in your make invocation - the shell will then vomit all commands it runs to stdout.
I'd really like something like this for systemd units. On embedded systems you want to have confidence that any permitted ordering will result in a working system - as there'll be no-one there to restart it if not.
cmake -G'Unix Makefiles' -S $SRC_DIR -B $BUILD_DIR
cmake --build $BUILD_DIR -- --shuffleThe basic idea is this: Let's say you have a target being built and one of the dependencies takes a long time to compile; say, a large auto-generated file. If the time to compile this file is very dominant and outlandish, then you really want to do it as early as possible (while satisfying all dependent constraints), no matter what order the rules are in. This is so that it can overlap with other work as much as possible. If you instead pick it very late in the build process, it can significantly extend the total build time.
A concrete example is one I had at a past job. We used CMake on a reasonably-sized and actively developed C codebase. Make took about 5 minutes to do a clean build. Switching to Ninja reduced that to 2:30s, on a clean build. That was great. But then, I used Shake -- a build system that ships with a Ninja-compatible build tool, just called "shake" -- to build the same project. 1m30s total![1]
It took me a while to realize this is because shake by default randomizes build plans, both to find errors, and to increase performance in cases like this. By just shuffling the build order, you will get a "smooth" distribution of build times, whereas always deterministically sticking with 1 plan can result in a build plan with very very poor "tail latencies". This was the exact example I mentioned. The project built about 10 executables, and 1 of them was a very large auto-generated tool, and compiling it took 80% of the total wall clock time of all other jobs combined. So shake would often build this tool first or at least very early on, just by chance -- while Ninja and Make would often build it last, every single time. A very big impact on tail latency.
So the TL;DR is -- randomize your build plans, knock out the missing dependencies, stabilize and ensure determinism where possible, and be happy!
[1] Shake was only better on the "rebuild entirely from scratch" case versus Ninja. When doing incremental rebuilds with small edits, I basically couldn't find any (meaningful) difference in their performance.
Ninja build targets in a semi-arbitrary order: the memory order of the pointers to the objects representing the build steps. This was chosen in part because it was easy but also because it was a little unpredictable (in the same sense as this nice shuffling idea). In practice I might expect the pointers to get allocated in the order they're encountered while parsing though, so perhaps similar to Make.
My recollection is we experimented a bit with different prioritizations but didn't find any that reliably were better. It does seem like you could try prioritizing "longer" tasks. (There are also more complex models that take into account the graph; I have been mentally drafting a blog post about this area, there's some interesting research history...)
To do so you'd need to keep around data from previous executions of those tasks, and perhaps multiple runs (for the case where a given task can take a varying amount of time).
In my newer n2 experiment, which was designed to be a little easier to hack on, the place you could play with prioritization is right here: https://github.com/evmar/n2/blob/d64412ae74ddff4e85329f390a0...
The "available to run" tasks are in a deque there (which also means steps go in parse order) but you could easily imagine changing it to some sort of priority structure.
I realized later on that Ninja used pointers when it traverses the build graph (by actually reading your blog, I think) which is where the more stable ordering came from. IIRC, when I asked Neil (shake author) about the randomness, I believe he said he added shuffling to mainly find bugs like the OP said, but also found it turned out to also win out in some cases like this where you have a weird distribution of build times with large outliers.
> To do so you'd need to keep around data from previous executions of those tasks, and perhaps multiple runs (for the case where a given task can take a varying amount of time).
Shake does do this actually, but only for ETA predictions, it doesn't use it for build ordering. It might be an interesting approach to try, but I'm not sure if it's much better than just doing it randomly, especially since if you modify the really expensive build step, you have to fully rebuild it anyway. In the no-op case, you just avoid it. So it would only help on clean rebuilds where you really want to pack the build steps in a better way to reduce the overall time.
For CI systems it might be useful since the clean build is more common (this is what I was interested in) but, randomization is like, 80% results for 20% effort, and all.
The real lesson from it would seem to me to be your first thoughts on what steps to do first in your build may be wrong. Profile until you find your best time to build, then lock it in.
Non-determinism can be handy for discovering new things about what you're dealing with, nut once you've got it; for heaven sake, lock it in.
No, you just have poor reading comprehension and poor understanding of the problem.
> The real lesson from it would seem to me to be your first thoughts on what steps to do first in your build may be wrong.
If you list the targets "a b c d e f" in make, then you can move 'f' into the front if it is very slow. If you use something like CMake, or another generator, you will lose control over this ordering, and it isn't always clear how to recover it in a non-fragile way.
And yes, Shake has profiling tools. That's how I found out what the critical path is and why Shake was better at this path.
> Non-determinism can be handy for discovering new things about what you're dealing with, nut once you've got it; for heaven sake, lock it in.
Lol. Bad reading comprehension. Please don't bother commenting on things if you literally have no idea what you're talking about. I realize that's a big ask on this site (where shooting your mouth off and trying to sound smart is more valuable than being smart) but you'll waste less time with it. Thanks.