bugmake - Bugs: bug #40225, Deterministic output ordering

 
 

bug #40225: Deterministic output ordering

Submitter:  Josh Triplett <joshtriplett>
Submitted:  Wed 09 Oct 2013 10:07:11 PM UTC
   
 
Severity:  3 - Normal Item Group:  Enhancement
Status:  None Privacy:  Public
Assigned to:  None Open/Closed:  Open
Component Version:  None Operating System:  None
Fixed Release:  None Triage Status:  Major Effort
* Mandatory Fields

Add a New Comment Rich Markup
   

Sun 24 Nov 2013 04:05:42 AM UTC, comment #5: 

I don't think Frank's suggestion below will work (or maybe I misunderstood it).  It's not enough to remember the order in which target recipes were started, because in parallel builds the order of starting targets can be different.  Consider a makefile like:


foo: slow fast
slow: slower
fast: faster


In a serial make the targets are run as slower -> slow -> faster -> fast -> foo, so that's the order in which we'd always want to see the output.

But in parallel make with -j2 for example, the targets will be run as slower -> faster -> fast -> slow -> foo.

What we'd need to do is remember the order in which make would have built the targets, if running in a serial way.  In order for that to work, we'd need to keep an ordered list of the targets we visit as we walk the dependency graph, and we'd need to convince ourselves that even with parallelism enabled we will walk the graph the same way without skipping any nodes (that is, we need to be sure that we won't jump to another branch of the graph because we know that this branch is blocked by a target currently being built).

These changes would need to be made above the job layer, in remake.c which is where the dependency graph is walked.  Frank is correct that we'd need to separate the output dump function out and hoist it up a layer, so that it could be done in the proper order.

Paul D. Smith <psmith>
Group administrator
Wed 16 Oct 2013 03:58:50 PM UTC, comment #4: 

Trying to make the output order deterministic seems to be the wrong approach to me. It'd be better to separate the build log out into lots of little files corresponding to each output file. I reckon this isn't too hard with a guile script. From guile, you set up a pipe and fork. Then you add a $(info $@ ...) to the start of the commands for every build rule. The forked guile would read these from the pipe and filter them.

As a test, I wrote a guile script (which I've attached to the bug) which does the pipe/fork however it execs tee to save a copy of the build output in a file. I'm new to Guile so sorry if it is somewhat crude but I think it does prove the concept.

Does anyone know how I can avoid the guile messages about auto-compiling the script given that I can't impose environment variables on users of the Makefile? I've tried adding a path to the compiled file to %load-compiled-path before calling (load "...") in the Makefile.. I've also tried a putenv.

(file #29386)

Oliver Kiddle <opk>
Thu 10 Oct 2013 04:51:51 PM UTC, comment #3: 

Just a nit: on MS-Windows, $wildcard always returns file names in sorted order, because that's how the underlying filesystem behaves.

Eli Zaretskii <eliz>
Group Member
Thu 10 Oct 2013 05:23:15 AM UTC, comment #2: 

A non-parallel build is actually fully deterministic for a given makefile.  Make (I believe this is specified by POSIX) will always try to build the first prerequisite first, then the second, etc.  Of course there are ways to get non-determinism: for example IIRC the $(wildcard ...) function returns files in "directory order", unsorted, which is non-deterministic.

I'm not saying Frank's idea would not work but I think it might be slightly hairier than described here.

Regarding vmsjobs.c: that's OK because vmsjobs.c is actually not compiled separately.  It's #included into jobs.c, so it has access to all jobs.c's static functions etc.  This is not orthodox, but I really needed to split out the VMS support as it was hard to follow job.c (it still is, but it was worse before).

Paul D. Smith <psmith>
Group administrator
Thu 10 Oct 2013 04:09:21 AM UTC, comment #1: 

First, I wonder how deterministic the order in a non-parallel build actually is. I guess, formally it's not, but for practical purposes it is, i.e. given the same make version and the same makefiles, it's unlikely to change.

When I had a need like yours (rarely), what I did was either:

- Preferredly: Build with "-s" and fix warnings early, so my build logs are quite small (ideally empty), even on large builds, so I'll see new messages with my bare eyes. :)

- Diff sorted logs. This way, I can at least see new or eliminated messages, but without context. (Here, output-sync will not help at all, though you still may want it for other reasons.)

Apart from these workarounds, I do think a proper solution could be implemented in make itself. Since output-sync keeps the output from each job in a temp file, it's already half way there.

I think such a new feature only makes sense with "recursive" output-sync. The purpose of line/target sync is to get messages earlier, which would conflict with (or be negated by) ordering. So effectively you want a new sync mode, let's call it "ordered" which implies "recursive", so we'd have a sequence of 5 modes (none, line, target, recursive, ordered) with successively stronger synchronization at the cost of more deferred messages. This will simplify the implementation since we'll only have to deal with one sync mode, and we won't have to care about make's own messages which have to be treated specially with line/target, but not recursive sync.

With output-sync, make dumps those temp files to the real stdout/stderr when it reaps the children (job.c:935: reap_children() -> output_dump()), so one idea would be to reap the children in the order they were started (by waiting for a specific process rather than any one). But this has a big drawback because it may drastically reduce parallelism (a long-running job would prevent waiting for other children and starting new ones, even if job server slots are free), so I don't think this will work well.

Instead, I think we'll have to separate reaping and syncing, i.e. reap_children() won't call output_dump() in "ordered" mode, and when make terminates (succesfully or not), it will clean up all children and dump their output (free_child() -> output_close() -> output_dump()).

The active children are kept in a list (global variable "children" and "next" pointer) until reaped. We cannot just move the children to a new list in reap_children() because we'd lose the order at that point. But if we simply keep the reaped children in the original list after reaping, this might also lead to problems: All code which traverses this list (e.g. job.c:819) needs to check for active children (not sure if child->file->command_state will do or a new flag would be needed), and for huge builds with maybe thousands of total jobs, this will basically add an O(n) factor there (not sure though if that's really significant, compared to actually running the child jobs).

A way to avoid these problems might be to put the children in a dual list, i.e. "children" and "next" continue to contain the active children, and a second list (say, global variable "children_to_sync" and a new "next_to_sync" pointer in struct child) contains all children (at least in "ordered" mode). new_job() would then link the new entry in both lists, reap_children() -> free_child() would only remove it from the former and the final syncing at the end would traverse the latter, whereas other code that traverses the children list would need no changes.

All of this assumes that the order that the children are started is deterministic -- at least as deterministic as in the non-parallel case (see above), which I haven't verified.

I might be missing something, but this could be a way to implement this feature with moderate effort. I'm afraid I don't have the time to write it myself (and the feature is not that important to me), and I don't know if Paul does, but if you, Josh, would like to try it, I could offer some advice when needed and review your changes, since I'm quite familiar with the output-sync internals. But first, I'd like to know what Paul thinks about adding even more complexity to output-sync ...

PS: While checking the above, I noticed vmsjobs.c calls free_child() which is static in job.c. Of course, I can't test it, since I don't have VMS, but it might be a bug.

Frank Heckenbach <frank>
Wed 09 Oct 2013 10:07:11 PM UTC, original submission:  

The new make -O option untangles the output of parallel builds; however, the actual output still occurs in a nondeterministic order.  I'd love to see an option to emit output in a deterministic order, ideally in the same order that a non-parallel make would.  This would make it possible to diff two build logs (for instance, to detect new or eliminated warning messages) without having to serialize the build and sacrifice build performance.

Josh Triplett <joshtriplett>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #29386:  buildlog.scm added by opk (670B - text/x-scheme - example of capturing output from guile)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by opk (Updated the item)
  • -email is unavailable- added by eliz (Posted a comment)
  • -email is unavailable- added by psmith (Posted a comment)
  • -email is unavailable- added by frank (Posted a comment)
  • -email is unavailable- added by joshtriplett (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2013-11-24 psmith Triage StatusNone Major Effort
    2013-10-16 opk Attached File- Added buildlog.scm, #29386

    Back to the top

    Powered by Savane 3.13-cf05.
    Corresponding source code