explicit control of the build order

[qhuo]

It seems to me that all ready to build Edges are contained in a std::set<Edge*> (Plan::ready_). That is, they are sorted by the pointer value comparison. In mostly cases, the order comes out in line with the order build commands are read and parsed from ninja files. And this is ok for us as we generate projects in order of their dependency orders.

However, sometimes, it may happen that a cpp file from a lower level project is not schedules to compile until much later into the build process, and therefore blocking up all the linking actions, making the total build time unnecessarily long. This typically happens with a clean build, when at the start of ninja, thousands of cpp files are ready to be compiled.

I propose we add some explicit control of the build order for ready targets. Let's say every Edge object should have a member of buildorder, then Plan::ready_ can be changed to set with a compare function, which compare the buildoder member of edges.

There are a few options to determine the build order value for the edges. By default, ninja can assign a sequential number for every Edge object created. We may also introduce a build_order variable to build commands, therefore giveing the generator full control of the order.

A further benefit when above is acomplished, we can indroduce a ninja option that generates randomised build order for all edges. This would be useful to find subtle dependency problems in generated ninja files.

[evmar]

It's a good idea. See also the discussion on #60

I wrote a test patch that adds a priority queue, letting you sort by an arbitrary number. One easy number to compute is "how deep in the dependency graph is this node" -- that is, what is the number of steps that will run serially after it finishes. That is just looking at stack.size() in Plan::AddSubTarget. We can even do smarter things like use the build log to estimate the total time of dependent work. (But parallelization and build graphs that aren't simple trees can make these numbers a bit harder...)

[qhuo]

Your idea looks good. Will you merge that to the mainline soon?

[PetrWolf]

After a little experiment, it turns out that this is especially important for more recent version of Windows (starting with 2K8 and Vista), where Low Fragmentation Heap is on by default.

There, the sequence of pointers returned from "new Edge" is not guaranteed to be always increasing.

A simple fix would be to use a custom comparator in Plan::ready_ based on the order in which the edges were created (rather than assuming that the pointer nominal values reflect that) and generate the .ninja files with that in mind.

But it seems you have a much smarter solution available - based on the actual position in the graph. That would be perfect indeed. Did your patch work as expected or did you encounter other problems? Are you planning to come back to that soon? If you publish that change, I'll be happy to give that a try.