--shuffle shouldn't break anything with a correctly written makefile, but it's a nice debug tool for flaky makes. If --shuffle breaks things, there's a dependency problem. Nice.
This is great. Short of having Electric Make and Electric Insight it's the best thing you can get in open source and I think shuffling should really be the default to stop people from making horrendous parallel unsafe makefiles in the first place - so that the rest of us never have to fix them.
What does Electric Make do? Have you considered Landlock Make? https://github.com/jart/landlock-make It's a GNU Make fork that uses pledge() and unveil() which is based on the Landlock security module which was introduced into the Linux Kernel two years ago. https://justine.lol/make/ Using this tool, it becomes impossible to specify build rules that fail to declare dependencies, because userspace sandboxing prevents it. This sandboxing goes 2x faster than Bazel. There's also an mkdeps.com program for C/C++ projects that can generate dependencies for 1m+ LOC projects in ~100ms.
Runs the make job in parallel on remote machines but maintains state about file accesses in order to detect order problems and dynamically reruns the build healing the problem in real time. Then writes out the correct build order so that subsequent builds can be arbitrarily parallel.
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.
If you want to argue this could break legacy products, that's a valid reason why they shouldn't do this.
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.
I disagree: The default should be deterministic but slow, and one should have to go out of their way to e.g. parallelize stuff, at least just enough to understand the risk of it becoming non-deterministic if done wrong.
Determinism is an implementation that limits your future development. Is a faster sort available? You can't use it. Could you do some of your internal implementation in parallel? You can't do that either, since some customer is relying on exactly how things work today.
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.
Developers will care if they are spending their time waiting for a build.
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.
These problems come out anyhow when people run the build on a different machine with more or less cores or other issues then the people who are just users of the build have a problem.
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.
I remember checking out electric make years ago for a project. It was from electric cloud and I believe it was somehow related to the creator of tcl. It would hook into the filesystem to understand everything that was being built. If there was a hidden dependency it would record it and could restart steps to build in the correct order.
It was pretty smart - I suspect you could write a really crappy makefile and coast.
While we're at it: Thanks for writing your book on GNU Make, it was a godsend years ago when I had to convert a big recursive Make build to be non-recursive (and that new shuffle feature would definitely have been a big help).
That's kind. That book came about because I wrote the Electric Make implementation of GNU Make and learnt a lot about it and then I worked with our customers on massive Makefiles and saw a lot of things.
Oh, I like it; there do need to be more ways to tackle the whack-a-mole situation that can arise with -j. Glad there's a seed option to make it deterministic.
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.
Meanwhile my coworkers refuse to run googletest tests in random orders, because their tests all rely on being run in the "right" order and affect global data...
I don't know a lot of makefiles, but based on what was written in the article, I was just trying to design a makefile which enforces goal ordering using the "correct" way, i.e dependencies. Such a makefile should naturally be unaffected by --shuffle and by parallel execution.
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:
If a, b, and c are independent and d depends on them all, you could declare:
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.
In theory yes. But a lot of people seem to think they need this and (wrongly) assume they can archieve it by simply writing the goals in order. Otherwise OP wouldn't be able to break so many builds with the --shuffle option.
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.
> But a lot of people seem to think they need this and (wrongly) assume they can archieve it by simply writing the goals in order.
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
If that's what they wanted, it's not that hard. Or they could just write a shell script to do a then b then c, instead of using make.
There is no such thing as "the" top-level goal, so that use case doesn't work: if someone does a parallel build of multiple "top-level" goals the package goal will still need to do something reasonable. To make this work you need multiple package goals, maybe using a pattern goal, and then the package--which sounds like the thing he user was actually trying to get--is going to be an ultimate goal, not whatever you previously thought was the "top-level" one.
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 hides the work of the subprocess from the parent. So if a, b, or c depend on other objects, make would need to stat them to discover they are built, maybe make -j could lead to them being built in parallel creating a race condition.
It'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.
Yes, I see what you mean. In practice, I have only used this trick for "clean and build" rules, which mean that d will never depend on the dependencies of a, b, and c, and I take care not to invoke several conflicting rules as the same time on the command line.
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.
Other sibling comments express that you can push the dependency graph into the targets, but if you really do need a-d to be built in order then it seems more straightforward to just execute them all as a single target:
FORCE:
a b c d: FORCE
run-a && run-b && run-c && run-d
This is sort of a "generative" (aka property-based) approach to testing makefiles. So, I'd like to see a variation that can find a minimal failing subset of the makefile rules, as in QuickCheck:
> 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
Hijacking the thread, but a command line option I would really like to have in make is a way to force command echoing, including those prefixed by '@'. It would be the opposite of '-s'. If such a feature already exists, please tell me.
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.
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.
Any way to set a seed, to reproduce failures trivially? This has been really useful with pytest-randomly. Update: Should've read further, it supports --shuffle=SEED. Nice!
Cool! How do I get CMake with `Unix Makefiles` generator to use `--shuffle` flag? Then I can use this same feature to find dependency issues in my CMakeLists.txt files...
It's an option you can use when invoking `make` - so no need to specify extra cmake options, just during `make` invocation after `cmake` is already done
Great feature. And shuffle isn't just useful for finding build issues, it can actually improve performance in some really annoying edge cases!
The 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).
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.
Thanks for the input, I haven't tried n2 yet. I don't have access to that code anymore but synthesizing an example to have the same outcome wouldn't be hard.
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.
