[HN Gopher] New make --shuffle mode
___________________________________________________________________
New make --shuffle mode
Author : spyc
Score : 211 points
Date : 2023-01-17 15:16 UTC (7 hours ago)
(HTM) web link (trofi.github.io)
(TXT) w3m dump (trofi.github.io)
| gt743268 wrote:
| 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.
| msoucy wrote:
| 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...
| simlevesque wrote:
| I mean, the test may be good. But they must be so slow they're
| not really useful.
| jdlyga wrote:
| Time to add GNU make to the list of randomizers:
| www.debigare.com/randomizers/
| spyc wrote:
| The list is about Video Game Randomizers, so maybe not.
| xg15 wrote:
| 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:
|
| d: xc
|
| xc: xb; <shell commands of c>
|
| xb: a; <shell commands of b>
|
| Which seems really unsatisfying.
|
| Is there a better way?
| delusional wrote:
| I think you're correct, it's impossible to instruct make to
| order your dependencies since dependencies may be built in
| parallel.
|
| I'm having trouble thinking of a case where it would be useful
| to do so.
| teawrecks wrote:
| If they need to run in order then they have a dependency on
| each other and you have to express that.
| smallnamespace wrote:
| 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
| jgrahamc wrote:
| That's not a "single target". That's four targets and is
| equivalent to: 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
| Karellen wrote:
| Why is it that you want d to run a then b then c, if a, b and c
| are independent goals?
|
| 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.
|
| https://en.wikipedia.org/wiki/XY_problem
| xg15 wrote:
| 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.
| saurik wrote:
| 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.
| Karellen wrote:
| > 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.
| GuB-42 wrote:
| The way I do it is by calling make recursively.
| THIS_FILE := '$(lastword $(MAKEFILE_LIST))' d:
| $(MAKE) -f $(THIS_FILE) a $(MAKE) -f $(THIS_FILE) b
| $(MAKE) -f $(THIS_FILE) c
| asveikau wrote:
| 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.
| lumb63 wrote:
| 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.
| aseipp wrote:
| 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.
| evmar wrote:
| [ninja author]
|
| 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.
| aseipp wrote:
| 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.
| salawat wrote:
| So you took the wrong lesson entirely?
|
| 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.
| aseipp wrote:
| > So you took the wrong lesson entirely?
|
| 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.
| dj_gitmo wrote:
| I wish this existed a few years ago when I was regularly working
| on large Make projects. Excellent work.
| eschneider wrote:
| --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.
| spyc wrote:
| Exactly.
| t43562 wrote:
| 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.
| jgrahamc wrote:
| Thanks for mentioning Electric Make, I did a lot of work on
| that :-)
| t43562 wrote:
| I know! :-D I did a small bit of work on it but long after
| you! I now selfishly wish that it was open source so I could
| still use it. :-)
| deng wrote:
| 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).
| jgrahamc wrote:
| 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.
| natrys wrote:
| I love your book on GNU Make :D
| jgrahamc wrote:
| Thanks!
| gt743268 wrote:
| Pretty sure the make maintainers would be drawn and quartered
| if they did that. So many things - probably most of the things
| - would stop building.
|
| "Thy build shall be nondeterministic!" is quite a curse to
| spring on someone :)
| t43562 wrote:
| 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.
| pixl97 wrote:
| Invisible until it opens up a security exploit, oops that
| library doesn't have its security flags set.
| licebmi__at__ wrote:
| I would argue that builds would break are already non
| deterministic, they just appear to be deterministic on "your"
| machine.
| Arainach wrote:
| 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.
| blauditore wrote:
| 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.
| Arainach wrote:
| 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.
| TeMPOraL wrote:
| > _The default should be deterministic but slow_
|
| That all but ensures nobody will care then. Performance
| is, sadly, not a big motivator in most projects.
| ProblemFactory wrote:
| 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.
| jart wrote:
| 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.
| t43562 wrote:
| Those look interesting! I'll try them out.
|
| 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.
| jgrahamc wrote:
| 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.
| wmanley wrote:
| Very neat.
|
| 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.
| inetknght wrote:
| 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...
| iokanuon wrote:
| 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
| wyldfire wrote:
| Just pass it when you invoke it. cmake -G'Unix
| Makefiles' -S $SRC_DIR -B $BUILD_DIR cmake --build
| $BUILD_DIR -- --shuffle
| spyc wrote:
| One way would be not using "cmake --build" but invoking make
| directly yourself after calling CMake.
| GuB-42 wrote:
| 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).
| karatinversion wrote:
| Another option, that I have had to fall back to before, is to
| include a
|
| SHELL='/bin/bash -vx'
|
| in your make invocation - the shell will then vomit all
| commands it runs to stdout.
| [deleted]
| mturmon wrote:
| It would appear that you want "---debug=p" ...
|
| > 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...
| jwilk wrote:
| Avaialable only since 4.4 (or 4.3.90 if you count pre-
| releases).
___________________________________________________________________
(page generated 2023-01-17 23:00 UTC)