Heuristic: Run jobs with large inputs before jobs with small inputs

[jlebar]

In the LLVM build, we have some files which take much longer to compile than others. The filename of one of these -- a 30,000-line C++ file (don't ask) -- is pretty late alphabetically, and it often ends up spinning long after most other targets have finished building.

It would be cool if ninja could, as a heuristic, look at the combined sizes of a rule's inputs and run rules with larger inputs first.

[wilhelmtell]

I'm not sure compile time is uniquely a function of file size.. I can imagine a small file that's a tough nut to crack for the compiler, and a large file that is trivial..

[jlebar]

I'm not sure compile time is uniquely a function of file size..

It's not. Nonetheless, compilation time is certainly positively correlated with file size. Thus the benefit of this heuristic.

[jimon]

Also maybe ninja can do some sort of PGO (profile guided optimization) 👍 like collect time information how long in took to compile each file and use this information to prioritize files in next build.

[kasper93]

Nonetheless, compilation time is certainly positively correlated with file size.

I don't think any heuristic based on source files will make sense. For instance we have less than thousand line C++ file which compile almost a minute (don't ask). Ultimately it depends how hard is the file for preprocessor and how many templates it will instantiate during compilation.

Of course one can assume that 30k-line file will compile longer than 1k one, but that's not decision that ninja should make in my opinion.

like collect time information how long in took to compile each file...

This is already done in .ninja_log You can use this script https://github.com/nico/ninjatracing to parse it and load up in chrome to see how build process went.

...and use this information to prioritize files in next build.

so since we already have the build time info ninja could indeed use that info in next builds. Could actually help.

EDIT:

Ok, I have actually taken a look at compilation times. The file which compiles the longest is https://github.com/llvm-mirror/clang/blob/master/lib/ASTMatchers/Dynamic/Registry.cpp and it has only 600 lines. So file size metric doesn't work at all for this particular file.

Also I don't see any bottlenecks in the process. But might help that I build with 13 threads.

[jlebar]

Hi, in case it's not clear, I actually work on LLVM and clang. I spent the past few weeks optimizing the speed of the clang/llvm backend, and in fact it was during this process that I ran into this problem. You're correct that a clean rebuild of clang packs well. But if you touch certain headers, you can easily end up waiting for one of these very long compiles, such as x86 isel lowering (which also happens to appear late in the alphabet, exacerbating the problem).

The analysis above is not statistically meaningful because it looks at just one file. Here's a scatterplot of cpp file size (x-axis) versus compile time (y-axis) on my machine of doing a clean build of clang.

If there were no correlation between file size and compilation time, we would expect this to look like random noise. But as you can see, there is a decent correlation between file size and compilation time.

Anyway, think using past compilation times to inform the ordering is a great idea.

[kasper93]

Of course there is corelation. But I don't think it is conclusive enough to be universal for every project. I don't have data available tho, so I might be wrong here.

See also #60 #376 #232

[jlebar]

But I don't think it is conclusive enough to be universal for every project.

Maybe I'm not being clear with my suggestion.

The suggestion is, if you are going to make an arbitrary choice between building A and B, then maybe use some heuristic to figure out which target is going to take longer to build. The heuristic of "look at how long they took to build last time" is great, way better than my suggestion of looking at file sizes. But in the absence of historical build times, I'd expect file sizes still to be useful.

Again, if a better heuristic (such as one of the ones you mentioned) applies, you should use that. But since I am only suggesting that this heuristic be applied as a last resort, I don't think the fact that it's not "universal" makes a difference. We were going to make an arbitrary choice, and now we make a slightly less-arbitrary choice.

Anyway looking at historical build times is so much better, I don't really care if you look at the file sizes. :)

[colincross]

Ninja has a heuristic for making arbitrary choices between building A and B: it builds whichever was first in the manifest. Could you put your heuristic in your build.ninja generator instead?

[mathstuf]

@colincross That is fine for the initial ordering, but subsequent orderings can use the timing to be more accurate than generators could ever hope to be. Personally, I'm not too worried about initial build time, but generators could optimize that way.

[Salamandar]

I think using the file size may not be enough for "profiling". For instance, a reeeally small cpp file with a lot of includes could be really long to process. And non-compilation processes (parsing, copy, file generations…) are not related to file size.
Still, that's a good approach for some build units.
A second approach could be to save in cache the time needed to build some file. Rebuilds could be optimized by analyzing this cache.

[mathstuf]

Ninja does save the times for jobs, so it has that information. The first build may not be optimal, but that's already the case since the ninja deps log is not populated either.

[advancedwebdeveloper]

@jlebar,
I have something similar with https://go.googlesource.com/gollvm/ : I got few thousands of compiled source files before specific ones enforce compiler's crash, featuring an "out of memory" error.
Currently two files are causing such a failure:
https://github.com/llvm/llvm-project/blob/7d3aace3f52f6b3f87aac432aa41ae1cdeb348eb/llvm/lib/Target/AMDGPU/AMDGPULowerIntrinsics.cpp
https://github.com/llvm/llvm-project/blob/7d3aace3f52f6b3f87aac432aa41ae1cdeb348eb/llvm/lib/Target/AArch64/AArch64PreLegalizerCombiner.cpp
While I have some doubts on the fact that Golang's compiler front-end has anything to do with OpenCL or OpenGL (there is nothing related existing event on the backend, currently) - but ARM64 support exists, for general CPU programming.
I would have to disable some parts of LLVM project, in CMake's config, in any case.
However the first file is 697 of 2934 files (past compilation processes preserved compiled .o files) and the second one (within a clean build) appears to be 817 of 3214 files.
It would be best to compile other files first, so I would predictively stuck on those that would consume the most of my RAM. So I would be interested to get those last - and see which have issues, since I can't know that before I would try. Or could I?

Ivan

[jlebar]

@advancedwebdeveloper indeed, there's sort of an assumption in Ninja that you have enough RAM to compile everything in parallel with the -jN setting you chose. At its root, this problem isn't caused by the order Ninja chose so much as by the fact that Ninja (and every other build tool I'm aware of) only gives you a very coarse way to limit parallelism -- namely, the -j flag.

[phord]

Anyway looking at historical build times is so much better, I don't really care if you look at the file sizes. :)

I came here looking for this feature, but I found this open issue instead. I hope it's clear that this "prioritize based on historical build-times" feature request is the sensible one to follow here. Can we change to title to attract more attention and avoid dups?

Has anyone experimented with this yet?

I'm not trying to continue the argument about whether input size is a more useful heuristic than random guessing in the absence of historical records. It clearly is! I only want to press for using the log of previous builds intelligently and I don't want to create another issue to request it since this one already exists.

[jlebar]

Does this PR count as a fix for this issue? #2019

I think so!!