Wild 0.10

Why another linker?
Mold is already very fast, however it doesn't do incremental linking and the author has stated that they don't intend to. Wild doesn't do incremental linking yet, but that is the end-goal. By writing Wild in Rust, it's hoped that the complexity of incremental linking will be achievable.

Incremental linking

Idea: Incremental linking is a technique to patch a previous linker's output file so that only functions or data that are updated from the previous build are written to it. It is expected to significantly reduce the amount of data copied from input files to an output file and thus speed up linking. GNU BFD and gold linkers support it.

Reason for rejection: I turned it down because it (1) is complicated, (2) doesn't seem to speed it up that much and (3) has several practical issues. Let me explain each of them.

First, incremental linking for real C/C++ programs is not as easy as one might think. Let me take malloc as an example. malloc is usually defined by libc, but you can implement it in your program, and if that's the case, the symbol malloc will be resolved to your function instead of the one in libc. If you include a library that defines malloc (such as libjemalloc or libtbbmallc) before libc, their malloc will override libc's malloc.

Assume that you are using a nonstandard malloc. What if you remove your malloc from your code, or remove -ljemalloc from your Makefile? The linker has to include a malloc from libc, which may include more object files to satisfy its dependencies. Such code change can affect the entire program rather than just replacing one function. The same is true for adding malloc to your program. Making a local change doesn't necessarily result in a local change in the binary level. It can easily have cascading effects.

Some ELF fancy features make incremental linking even harder to implement. Take the weak symbol as an example. If you define atoi as a weak symbol in your program, and if you are not using atoi at all in your program, that symbol will be resolved to address 0. But if you start using some libc function that indirectly calls atoi, then atoi will be included in your program, and your weak symbol will be resolved to that function. I don't know how to efficiently fix up a binary for this case.

This is a hard problem, so existing linkers don't try too hard to solve it. For example, IIRC, gold falls back to full link if any function is removed from a previous build. If you want to not annoy users in the fallback case, you need to make full link fast anyway.

Second, incremental linking itself has an overhead. It has to detect updated files, patch an existing output file and write additional data to an output file for future incremental linking. GNU gold, for instance, takes almost 30 seconds on my machine to do a null incremental link (i.e. no object files are updated from a previous build) for chrome. It's just too slow.

Third, there are other practical issues in incremental linking. It's not reproducible, so your binary isn't going to be the same as other binaries even if you are compiling the same source tree using the same compiler toolchain. Or, it is complex and there might be a bug in it. If something doesn't work correctly, "remove --incremental from your Makefile and try again" could be a piece of advice, but that isn't ideal.

So, all in all, incremental linking is tricky. I wanted to make full link as fast as possible, so that we don't have to think about how to work around the slowness of full link.