Ninja: Object file compilation unconditionally depends on artifacts of dependencies

Title changed from Ninja: C compilation targets unnecessarily depend on libraries to Object file compilation unconditionally depends on dependent libraries

mentioned in issue #14726 (closed)

mentioned in issue #13799 (closed)

mentioned in issue #8536 (closed)

Added gen:ninja label

mentioned in issue #13592 (closed)

Changed title: Object file compilation unconditionally depends on dependent libraries → Ninja: Object file compilation unconditionally depends on dependent libraries

I changed the title back to be Ninja-specific because this problem is really only solvable with the Ninja generator. I couldn't find this issue when looking for it as a result of having no mention of Ninja.

I also tripped over this problem years ago. For what it's worth, my minimal repro at the time was to use this CMakeLists.txt

PROJECT(libDependencyTest C)
ADD_LIBRARY ( a STATIC a.c )

ADD_LIBRARY ( b STATIC b.c )
TARGET_LINK_LIBRARIES ( b a )

ADD_EXECUTABLE ( e e.c )
TARGET_LINK_LIBRARIES ( e b )

and then do:

$ touch a.c b.c
$ echo 'int main(){return 0;}' > e.c
$ cmake -G Ninja .

...and then look at the dependencies in build.ninja. On cmake 2.8.12.1 these looked like:

$ grep C_COMPILER build.ninja
build CMakeFiles/a.dir/a.o: C_COMPILER a.c
build CMakeFiles/b.dir/b.o: C_COMPILER b.c || liba.a
build CMakeFiles/e.dir/e.o: C_COMPILER e.c || liba.a libb.a

On cmake 3.7.1 the ninja generator emits the dependencies differently, but the dependencies on the .a's are still there:

build cmake_order_depends_target_e: phony || liba.a libb.a
build CMakeFiles/e.dir/e.c.o: C_COMPILER__e e.c || cmake_order_depends_target_e

build cmake_order_depends_target_b: phony || liba.a
build CMakeFiles/b.dir/b.c.o: C_COMPILER__b b.c || cmake_order_depends_target_b

build CMakeFiles/a.dir/a.c.o: C_COMPILER__a a.c

I patched our local copy of cmake (first 2.8.x, later 3.0.x) to just force it to drop a bunch of dependencies. In cmNinjaTargetGenerator ::WriteObjectBuildStatement() I just did:

  std::string rule = this->LanguageCompilerRule(language);
// [...]
if (rule != "C_COMPILER" && rule != "CXX_COMPILER")   // <----- added this line
   this->GetLocalGenerator()->AppendTargetDepends(this->Target, orderOnlyDeps);

basically I hardwired .o files to only depend on my C/C++ source files and nothing else. It's obviously an unsafe and incomplete hack around the problem. I'm looking at finally updating our local version of cmake and was researching if something like that will still be needed... I guess it will be, although the names of the rules have changed in the newer cmakes, so I'll have to adjust my logic a bit.

Anyway, hopefully there will be an official fix for this some day so I can run a stock cmake binary again.

Yeah, that's the symptoms. For clarity, this is done because it is what the Makefiles do. If you'd like to work on the proper fix, you can drop the dependency from B's objects on dependent library A if A's custom command dependencies are a subset of B's custom command dependencies (i.e., any headers/sources/etc. A needs generated are also already dependencies of B itself).

mentioned in merge request !430 (merged)

Great that this is getting fixed for Ninja! Nice job!

@brad.king you mention above that it is not possible to do similar job for Makefiles, but when playing around with CMake I noticed that it is possible there as well there with the note that one has to use both target_link_libraries() and add_dependencies() for scenarios like generated headers. It would namely be really awesome if this diminished parallelism would be sorted in more generators. I have this change for makefile generator which seems to work for a small example present still localy, but I might overlook something crucial here.

@vanderhu Huh. I'm just watching it. Not fixing. The Xcode generator eats up 150% of my spare time.

IIRC, makefiles use a courser dependency graph because doing anything finer inflates the number of files which needs to be written. If you look at the tests added to the branch which addresses this issue, that should be the litmus test for whether your patch fixes it for Makefiles (including the AssumedSources test since the makefiles generator probably has a similar way of implementing the associated logic: that or it just generates a broken without warning that the user is missing information). Note that GNU features are not allowed in the generated makefiles.

Note that tests show that a project which has a "wider" build graph than the machine has available parallelism (number of cores), the build performance isn't meaningfully impacted. The other part which this affects is when building with -k0, the only parts which aren't blocked are the object files which fail to build and the link steps which require them; all other object builds can complete successfully. Basically, instead of 500 or so rules left after a -k0, there might only be 10 (the failed object builds and the link rules which require them).

closed via commit adf60b28

changed title from Ninja: Object file compilation unconditionally depends on dependent libraries to Ninja: Object file compilation unconditionally depends on artifacts of dependencies

Hi... sorry coming back to this issue a month after it was closed. I have some good news and some bad news regarding this change.

First, the background: as I mentioned above I had previously used a old custom-patched cmake to remove these "false" dependencies from the generated build.ninja files. This worked, but I was eager to see this fixed in the mainline so I could run a vanilla cmake again.

When I saw this got closed, I upgraded our build environment to cmake 3.8.0 with the PR's diff applied (with the goal of moving to 3.9.0 as soon as it arrives) The initial results seemed positive; a large amount of build parallelism appeared while I was building.

However, I am now digging more deeply into some build-speed regressions, and I found that there is still one source of false-dependencies in the ninja files which are biting us. To repro, look at the CMakeLists.txt I mentioned earlier in this bug (#15555 (comment 213470)) Now running that with the just-posted cmake 3.9.0-rc1 we get this fragment in rules.ninja:

# Order-only phony target for e

build cmake_object_order_depends_target_e: phony || cmake_object_order_depends_target_a cmake_object_order_depends_target_b
build CMakeFiles/e.dir/e.c.o: C_COMPILER__e e.c || cmake_object_order_depends_target_e

# [...]

# =============================================================================
# Link build statements for EXECUTABLE target e

#############################################
# Link the executable e

build e: C_EXECUTABLE_LINKER__e CMakeFiles/e.dir/e.c.o | libb.a liba.a || liba.a libb.a

So we asked cmake to make an executable called e by compiling e.c->e.o and then linking {e.o,liba.a,libb.a}->e However, cmake_object_order_depends_target_e are the dependencies on the e.o compile even though we only need those libraries when we link e itself. Therefore we don't parallelize the compilation of e.o with the compilation of a.o and b.o.

Why does this matter for me? As described earlier, we compile over a thousand C++ files into a few dozen static libraries that get linked into our final shipped executable. However, we also have a unit test driver program that links against those same libraries but also includes a large number of testing-only C++ files. Right now these are build as object files linked directly into the testing executable. i.e. it ends up looking something like:

ADD_EXECUTABLE ( shipped-binary shipped-main.cpp )
TARGET_LINK_LIBRARIES ( shipped-binary library1 library2 library3 ... )

ADD_EXECUTABLE ( unittest-binary unittest-main.cpp test-case-1.cpp test-case-2.cpp ... )
TARGET_LINK_LIBRARIES ( my-tester library1 library2 library3 ... )

With the current fixes from PR430, this is now quite a bit better than before -- the components of library* all quickly compile in parallel, followed by a big link of *.a and shipped-binary) However none of the test-case-*.cpp files start compiling until all of the intermediate libraries are finished linking. Once they are the unit tests all compile in parallel, but there is a period of time when we're linking and most of the compile nodes go idle.

tl;dr: I think the ninja library dependencies are still landing in the wrong place, but more subtly so. The final executable link should depend on the libraries, not the compilation of source files that happen to be listed in ADD_EXECUTABLE()

Trilinos also generates a lot of unit test executables and some of the *.cpp files for these unit test executables can take a non-trivial amount of time to build. Therefore, it would be nice to get this last issue fixed.

@mitchblank in your example all three sources can compile concurrently.

cmake_object_order_depends_target_e are the dependencies on the e.o compile even though we only need those libraries when we link e itself.

cmake_object_order_depends_target_e does not depend on e.o as of CMake 3.9. It represents the potential dependencies needed to compile e.o itself, such as custom commands in target e or its dependencies.

Here are the relevant parts of the build graph:

build cmake_object_order_depends_target_a: phony
build CMakeFiles/a.dir/a.c.o: C_COMPILER__a a.c || cmake_object_order_depends_target_a
build cmake_object_order_depends_target_b: phony || cmake_object_order_depends_target_a
build CMakeFiles/b.dir/b.c.o: C_COMPILER__b b.c || cmake_object_order_depends_target_b
build cmake_object_order_depends_target_e: phony || cmake_object_order_depends_target_a cmake_object_order_depends_target_b
build CMakeFiles/e.dir/e.c.o: C_COMPILER__e e.c || cmake_object_order_depends_target_e
build e: C_EXECUTABLE_LINKER__e CMakeFiles/e.dir/e.c.o | libb.a liba.a || liba.a libb.a

Note that cmake_object_order_depends_target_{a,b,e} amount to nothing (their role changed from CMake 3.8 to 3.9). The build graph simplifies to:

build CMakeFiles/a.dir/a.c.o: C_COMPILER__a a.c
build CMakeFiles/b.dir/b.c.o: C_COMPILER__b b.c
build CMakeFiles/e.dir/e.c.o: C_COMPILER__e e.c
build e: C_EXECUTABLE_LINKER__e CMakeFiles/e.dir/e.c.o | libb.a liba.a || liba.a libb.a

All the sources will compile concurrently. Then the archive/link steps occur in order.

I verified that the Ninja files generated by CMake 'master' will allow the build of object files for sources directly used in execs without triggering the build of upstream libs or their objects, at least for a few examples that I looked at.

Sorry for disappearing for so long again... I haven't had much time to play with our build system.

I can verify that I was misunderstanding my test case, and that a.o, b.o, and e.o are being compiled in parallel.

However, it was still mysterious why I'm seeing non-optimal parallelism in practice. Digging more into it, it seems to be an issue being caused by some strange dependencies ending up on a ADD_CUSTOM_COMMAND target which is generating one source file. I'll have to investigate more when I have some time, but here is a modified version of my example:

PROJECT(libDependencyTest C)
ADD_LIBRARY ( a STATIC a.c )

ADD_LIBRARY ( b STATIC b.c )
TARGET_LINK_LIBRARIES ( b a )

ADD_CUSTOM_COMMAND (
	OUTPUT ${CMAKE_BINARY_DIR}/linked-e.c
	COMMAND ln -f ${CMAKE_BINARY_DIR}/e.c ${CMAKE_BINARY_DIR}/linked-e.c
	MAIN_DEPENDENCY ${CMAKE_BINARY_DIR}/e.c
	COMMENT "hardlinking e.c"
)

ADD_EXECUTABLE ( e linked-e.c )
TARGET_LINK_LIBRARIES ( e b )

After running through cmake-3.9.0 I get this in build.ninja

build linked-e.c: CUSTOM_COMMAND e.c || liba.a libb.a

and if I add another f.c file to e like:

ADD_EXECUTABLE ( e linked-e.c f.c )

...and it seems that f.c and b.c won't be compiled in parallel (which I've verified experimentally), following this dependency chain:

build CMakeFiles/e.dir/f.o: C_COMPILER__e f.c || cmake_object_order_depends_target_e
build cmake_object_order_depends_target_e: phony || cmake_object_order_depends_target_a cmake_object_order_depends_target_b linked-e.c
build linked-e.c: CUSTOM_COMMAND e.c || liba.a libb.a

so the generated .c file can't (for some reason that's obscure to me) be built until all of the libraries are built... and it also won't build any other object files until that generated source file is built (again, not sure why that would be)

This is basically it's a custom command. Since CMake doesn't have any idea what it is doing, it hooks up dependencies maximally in case it implicitly depends upon, say, a header generated as a dependency of a. It also depends on a's output directly since it might read that file (every other generator guarantees that it will exist at that point).

Work would need to be done to indicate that add_custom_command is fully specified and that OUTPUT, BYPRODUCTS and DEPENDS are complete which would allow for Ninja to do further optimization based on it.

Ah ok.. I assumed that the dependencies I listed for add_custom_command would be considered definitive, but I guess that's not the case. I guess for the time being I'll go back to the strategy of locally patching the cmake source code to remove these dependencies from the generated build.ninja file.

The annoying thing is the only reason I a using add_custom_command at all is to work around a different problem I ran into with the ninja backend. One task our cmake scripts does is come up with a list of unit-test functions that need to be compiled in (which differs depending on exact configuration) which then get written out as a table in a C++ file that we link against. Since this file is not on disk at the time that cmake runs we need to mark it with the GENERATED property to prevent cmake from complaining about it missing.

This works fine with the "UNIX Makefiles" and various MS Visual Studio generators. However the "Ninja" generator effectively assumes that everything marked with GENERATED should be included as part of the clean target, even if it wasn't a build target!

A simple example:

PROJECT ( genFileBug C )
FILE ( WRITE gen.c "int main() { return 0; }\n" )
SET_SOURCE_FILES_PROPERTIES ( gen.c PROPERTIES GENERATED 1 )
ADD_EXECUTABLE ( gen gen.c )

If you then run...

$ rm -rf gen.c CMakeCache.txt CMakeFiles && cmake -G "Unix Makefiles" && make  && make clean  && make
$ rm -rf gen.c CMakeCache.txt CMakeFiles && cmake -G Ninja            && ninja && ninja clean && ninja

...the first command will work fine. However, the second ninja build will fail because ninja clean deletes the gen.c file even though it wasn't the thing that built it. This seems to be because cmake still spits out a "build" line for this file into build.ninja

#############################################
# Assume dependencies for generated source file.

build gen.c: CUSTOM_COMMAND cmake_object_order_depends_target_gen
  restat = 1

...so ninja -t clean assumes that gen.c should be part of the cleansing.

Anyway, the workaround I used for this is to check if ${CMAKE_GENERATOR} is Ninja and if so write the file generated by the cmake scripts to a different filename. Then I have a trivial add_custom_command that just makes a hardlink at build-time. That way ninja clean can delete it with no harm done -- the next ninja run will just recreate it.

So maybe I'll try to locally patch cmGlobalNinjaGenerator::WriteAssumedSourceDependencies() to be a no-op to make this ninja clean problem go away without needing the hardlink hack in the first place... not sure if that would have any ill effects or not.

It'd be better if you could convert the file(WRITE) into something done at build time rather than configure time. That should solve the issue you're seeing with all generators. The issue you're hitting is #16367 though.

~~Actually, if you unconditionally do file(WRITE), you can just add that path to CMAKE_CONFIGURE_DEPENDS.~~ Oops, you need CMAKE_CONFIGURE_OUTPUTS, which also doesn't exist yet.

It'd be better if you could convert the file(WRITE) into something done at build time rather than configure time.

But "done at build time" how? If it's built via add_custom_command() aren't I back to square one wrt the dependency graph being non-optimal?

Hmm, probably. It would fix the "clean deletes files it doesn't actually know how to remake" problem though (which sounds more core to me).

Yes, which is why I'm using add_custom_command() to make that hardlink in the first place! You're basically describing my exact solution right now.

To recap:

The information I need to generate the table of test cases is all known at cmake-time, so it's creating a file with this information (It doesn't really matter if creating it via file(write) or as a side effecct of an exec_program() call -- I just used file(write) in my trivial example for brevity).
Because of this ninja -t clean issue I am then "building" the source file via add_custom_command() just like you recommend. In my case I actually have a C++ file already in its final form, so my "build" step is just creating a hardlink. However, it satisfies the criteria that now clean only deletes things it "knows how to remake"
...however this use of add_custom_command() is messing up my dependency graph (apparently because it doesn't believe that I'm telling it the whole truth about DEPENDS/etc), causing my parallel builds to be much slower than they should be.

It sounds like there isn't a way to fix this build speed problem without some local patching of cmake here to case the build.ninja file to be emitted slightly differently... either by fixing the underlying clean bug, or by trimming the add_custom_command() target's dependencies.

Well, instead of the hardlink hack, if you have an add_custom_command which wrote the file in the first place, that'd fix the clean problem. So instead of file(WRITE) → hardlink, replace the hardlink with a step that does the same thing as your file(WRITE). You'll still have the excess dependencies, but your build will be generator-agnostic even after a clean.

I guess we're just talking past each other at this point. The excess dependencies are the problem I'm most trying to fix.

The original form of the bug that there were tons of excess dependencies in the ninja files, limiting parallelism. I commented that I had made a locally-hacked-up copy of cmake to avoid it. Since unpatched cmake 3.9 still shows non-ideal parallelism (better than before, but not as good as with my earlier hacky "fix") I thought that it meant that this issue was partially fixed, but it now seems that it's an unrelated limitation in add_custom_command()'s willingness to trust the dependencies I tell it.

So ultimately the situation for me is that I still need to locally hack up cmake to get the build parallelism I want. This is something I was hoping to be able to avoid after this bug was fixed, but oh well...

OK, we are understanding each other, but personally, I consider the clean problem more urgent (from a CMake-correctness viewpoint), but if you have other tradeoffs, that's fine too.

The extra deps on an add_custom_command is something worth a separate issue if you'd like to summarize the discussion here about it (this one didn't mention add_custom_command, but I can see how it'd be confusing to outsiders how that part didn't get fixed at the same time; they're just different codepaths and behaviors, some of them imposed by the behaviors of other generators and add_custom_command).

mentioned in issue #17097 (closed)

OK filed the add_custom_command dependencies as #17097 (closed) Hopefully I've described that sufficiently clearly.

but personally, I consider the clean problem more urgent (from a CMake-correctness viewpoint)

I would as well, except that I have already have a working solution for that problem (the hardlink thing)

I think the thing you're not understanding is that I can't simply move all of the logic into the add_custom_command() The point of this generated file is to capture information determined during the cmake run (which is dependent on all sorts of cmake-time options). Basically we have a custom cmake macro that both calls add_test() to create a new ctest-driven unit test case and also adds an entry to this C++ table that gets built into our test-driver binary. This way, our developers only have to add a single cmake command to set up a new test.. and it still does the right thing if it's inside a cmake if() statement, or called via foreach() or whatever else.

Now what I could do is change this code so it looks like:

cmake-time: My macros output a text file describing the tests (in some format)
build-time: An add_custom_command()-target takes that as input and outputs a C++ file

But compare that with what I'm doing today:

cmake-time: My macros output a text file describing the tests, which happens to be in the form of a C++ source file
build-time: The add_custom_command()-target now just has to hardlink (or copy) that file in place

There is no real difference as far as cmake is concerned, it just happens to be outputting the needed information in a format that doesn't require any additional transformation at build time. If I were going to build it from scratch today I might do it differently, but I don't feel like changing what works today. As long as the ninja clean issue requires an add_custom_command() it makes no difference if it's running some giant python script or just /bin/ln, it's going to have the same drawbacks dependency-wise.

mentioned in issue #17528

mentioned in issue #20361

mentioned in issue #20407

mentioned in issue #22263 (closed)

mentioned in issue #24411 (closed)

mentioned in merge request !8420 (merged)

mentioned in issue #24959 (closed)

mentioned in issue #24998 (closed)

mentioned in merge request !8989 (merged)

mentioned in issue #25425 (closed)

mentioned in issue #25796 (closed)

mentioned in issue #24629

Ninja: Object file compilation unconditionally depends on artifacts of dependencies

Child items ...

Activity