4 ms·

Linkers are mind-bogglingly slow. I don't understand why they are so slow. lld is still slow, it is just less slow than the other linkers. This is not to disp

by jblow 10y ago

Linkers are mind-bogglingly slow. I don't understand why they are so slow. lld is still slow, it is just less slow than the other linkers. This is not to disparage anyone working on linkers or say they are not smart. I think they just don't tend to be performance-oriented programmers, and culturally there has become some kind of ingrained acceptance of how much time it is okay for a linker to take.

comex 10y ago
Linking is also very easy to do incrementally, but for some reason incremental linking is not popular in the Unix world. GNU ld and Apple ld64 can't do it. GNU gold can do it, but only if you pass a special linker flag, which typical build systems don't. LLD can't do it, despite being the spiffy new thing. So you end up with big projects where most of the time taken by incremental debug builds is spent linking - relinking the same object files to each other over and over and over. Awful. I don't use Windows, but I hear Visual Studio does the right thing and links debug builds incrementally by default. Wish the rest of the world would catch on.
- Joky 10y ago
  ld64 links clang (a multi-millions line project) in roughly 2s on my laptop. Do we need incremental linking? MSVC incremental link is really not a model I would take as an example: the final binary is not the same as the one you get from a clean build, which is not a world I would want to live in.
  - comex 10y ago
    First of all, that doesn't include linking debug info (dsymutil), does it? That's usually bigger than the executable itself. You can get away without linking it, but that just means the debugger has to read a ton of object files at startup. dsymutil isn't part of the linker, but AFAIK there's no reason it couldn't/shouldn't be. Anyway, an incremental link should take a small fraction of a second and be O(1) all the way up to something like chromium. Well, there's the need to stat the input files to check for changes, but that's something the build system also has to do, so ideally there should be some sort of coordination. It's true that the output of an incremental link will generally be nondeterministic, unless you add a slow postprocessing step. After all, the whole point is to take advantage of the fact that most of the desired content is already in the output binary. Ideally you never have to touch that content, even just to do a disk copy; you should be able to just patch in the new bytes in some free space in the binary, and mark the old region as free. But of course the ordering of symbols in the binary then depends on what was there before. I don't know why that's particularly problematic; incremental builds are mainly useful during development, not for making releases, which is where reproducible builds are desirable.
    - Joky 10y ago
      > I don't know why that's particularly problematic; incremental builds are mainly useful during development, not for making releases, which is where reproducible builds are desirable. I don't know for you, but not having to chase bugs that would only show up in an incremental build (or symmetrically: having bugs hidden by the incremental build that would show up in a clean build) is making "reproducible builds desirable" in my day-to-day development... I would design any incremental system to provide this guarantee from the beginning.
      - comex 10y ago
        I would expect it to be extremely rare for the order of symbols within a binary to hide or expose bugs in the application. It's not like compiler optimizations where semi-random inlining decisions can allow for further optimizations, with a cascading effect on whether undefined behavior gets noticed or what kind of code gets generated, etc. Linkers are much simpler and lower level than that, in the absence of LTO. Anyway, many people already develop without optimizations and release with them, which is far more likely to result in heisenbugs even if it's technically a deterministic process. For that matter, I'm only proposing to use incremental linking in debug builds, so most of the time you'd only end up with nondeterminism if you were already going to get an output binary substantially different from a release-mode one. The only exception is if you have optimizations enabled in debug builds.
- jblow 10y ago
  Windows has incremental linking and it's still too slow. But it's faster than non-incremental linking, yeah.
- chisophugis 10y ago
  Every incremental linking technique I'm aware of involves overwriting the output file and does not guarantee that identical input files and command line lead to identical (bit-exact) output files. Incremental linking is not so easy under that constraint, since the output depends on the previous output file (which may not even be there). (and considering the previous output file to be an "input file" follows the letter of the requirement but not the spirit; the idea is that the program invocation is a "pure function" of the inputs, which enables caching and eliminates a source of unpredictable behavior) We have had to reject certain parallelization strategies in LLD as well because even though the result would always be a semantically identical executable, it would not be bit-identical. See e.g. the discussions surrounding parallel string merging: https://reviews.llvm.org/D27146 https://reviews.llvm.org/D27146 <-- fastest technique, but non-deterministic output https://reviews.llvm.org/D27152 https://reviews.llvm.org/D27152 <-- slower but deterministic technique https://reviews.llvm.org/D27155 https://reviews.llvm.org/D27155 <-- really cool technique that relies on a linearly probed hash table (and sorting just runs of full buckets instead of the entire array) to guarantee deterministic output despite concurrent hash table insertion.
  - comex 10y ago
    As I said in a different reply, I think nondeterminism is an acceptable sacrifice for development builds, which is where incremental linking would be most useful. That said, it's definitely possible to get some speedup from incrementality while keeping the output deterministic; you'd have to move symbols around, which of course requires relocating everything that points to them, but (with the help of a cache file that stores where the relocations ended up in the output binary) this could probably be performed significantly more quickly than re-reading all the .o files and doing name lookups. But admittedly this would significantly reduce the benefit.
    - chisophugis 10y ago
      I agree. It's definitely possible. It's just that the actual benefit is far from reducing link time to "O(changes in the input)" and it would introduce significant complexity into the linker (and keeping LLD simple and easy to follow is a high priority). It's definitely an open research area. > That said, it's definitely possible to get some speedup from incrementality while keeping the output deterministic; you'd have to move symbols around, which of course requires relocating everything that points to them, but (with the help of a cache file that stores where the relocations ended up in the output binary) this could probably be performed significantly more quickly than re-reading all the .o files and doing name lookups. But admittedly this would significantly reduce the benefit. Yeah. It's not clear if that would be better in practice than a conservative padding scheme + a patching-based approach. "move symbols around, which of course requires relocating everything that points to them" sounds a lot like what the linker already spends most of its time doing (in its fastest mode). In its fastest mode, LLD actually spends most of its time memcpy'ing into the output file and applying relocations. This happens after symbol resolution and does not touch the input .o files except to read the data being copied into the output file. The information needed for applying the relocations is read with a bare minimum of pointer chasing (only 2 serially dependent cache misses last I looked) and does not do any hash table lookup into the symbol table nor does it look at any symbol name string.
rui314 10y ago
Linkers have to copy large amount of data from object files to an output file, and that is inevitably slow. But LLD is not that bad if you pass -O0 (which disables string merging, which is computationally expensive). For example, LLD takes 6.7 seconds to link clang with debug info on my machine. $ time ld.lld <omit> -O0 -o bin/clang-4.0 real 0m6.689s Copying the output file to other file takes 2.6 seconds. $ time cp bin/clang-4.0 foo real 0m2.657s So, LLD is only 2.5x slower than cp in this case. That's not too bad, as apparently the linker has many more things to do than the cp command.
- jblow 10y ago
  Is your test mostly waiting on a mechanical hard drive? If so, then "2.5x slower than cp" could mean "a very large amount slower than cp" once you remove that overhead. Whereas I have not done your specific test, I know that for the file sizes of executables I deal with in everyday work (around 10MB), the amount of time I wait for linking is woefully disproportionate.
  - rui314 10y ago
    It is on an SSD.
    - e12e 10y ago
      It'd be interesting to see the numbers of a ramdisk cp/link as well. With ssd being so much faster than mechanical disks, people sometimes forget that ram is faster still.
  - aseipp 10y ago
    For a comparison, an optimized release build of Clang 5.0 trunk (from a few days ago, built with Clang 5.0 trunk from like a week ago) with assertions enabled is 87mb -- with the LLVM libraries linked in, but dynamically linked to system libraries, on my Fedora 25 machine. A debug build of clang is normally hundreds of megabytes (~600mb IIRC, and normal linkers go bonkers dealing with it), so if LLD is actually only 2.5x slower than 'cp' at -O0, that's quite good I think. The next question is how much memory LLD uses vs the competition in this test...

by jblow 10y ago

comex 10y ago

Linking is also very easy to do incrementally, but for some reason incremental linking is not popular in the Unix world. GNU ld and Apple ld64 can't do it. GNU gold can do it, but only if you pass a special linker flag, which typical build systems don't. LLD can't do it, despite being the spiffy new thing. So you end up with big projects where most of the time taken by incremental debug builds is spent linking - relinking the same object files to each other over and over and over. Awful. I don't use Windows, but I hear Visual Studio does the right thing and links debug builds incrementally by default. Wish the rest of the world would catch on.

Joky 10y ago
ld64 links clang (a multi-millions line project) in roughly 2s on my laptop. Do we need incremental linking? MSVC incremental link is really not a model I would take as an example: the final binary is not the same as the one you get from a clean build, which is not a world I would want to live in.
- comex 10y ago
  First of all, that doesn't include linking debug info (dsymutil), does it? That's usually bigger than the executable itself. You can get away without linking it, but that just means the debugger has to read a ton of object files at startup. dsymutil isn't part of the linker, but AFAIK there's no reason it couldn't/shouldn't be. Anyway, an incremental link should take a small fraction of a second and be O(1) all the way up to something like chromium. Well, there's the need to stat the input files to check for changes, but that's something the build system also has to do, so ideally there should be some sort of coordination. It's true that the output of an incremental link will generally be nondeterministic, unless you add a slow postprocessing step. After all, the whole point is to take advantage of the fact that most of the desired content is already in the output binary. Ideally you never have to touch that content, even just to do a disk copy; you should be able to just patch in the new bytes in some free space in the binary, and mark the old region as free. But of course the ordering of symbols in the binary then depends on what was there before. I don't know why that's particularly problematic; incremental builds are mainly useful during development, not for making releases, which is where reproducible builds are desirable.
  - Joky 10y ago
    > I don't know why that's particularly problematic; incremental builds are mainly useful during development, not for making releases, which is where reproducible builds are desirable. I don't know for you, but not having to chase bugs that would only show up in an incremental build (or symmetrically: having bugs hidden by the incremental build that would show up in a clean build) is making "reproducible builds desirable" in my day-to-day development... I would design any incremental system to provide this guarantee from the beginning.
    - comex 10y ago
      I would expect it to be extremely rare for the order of symbols within a binary to hide or expose bugs in the application. It's not like compiler optimizations where semi-random inlining decisions can allow for further optimizations, with a cascading effect on whether undefined behavior gets noticed or what kind of code gets generated, etc. Linkers are much simpler and lower level than that, in the absence of LTO. Anyway, many people already develop without optimizations and release with them, which is far more likely to result in heisenbugs even if it's technically a deterministic process. For that matter, I'm only proposing to use incremental linking in debug builds, so most of the time you'd only end up with nondeterminism if you were already going to get an output binary substantially different from a release-mode one. The only exception is if you have optimizations enabled in debug builds.
jblow 10y ago
Windows has incremental linking and it's still too slow. But it's faster than non-incremental linking, yeah.
chisophugis 10y ago
Every incremental linking technique I'm aware of involves overwriting the output file and does not guarantee that identical input files and command line lead to identical (bit-exact) output files. Incremental linking is not so easy under that constraint, since the output depends on the previous output file (which may not even be there). (and considering the previous output file to be an "input file" follows the letter of the requirement but not the spirit; the idea is that the program invocation is a "pure function" of the inputs, which enables caching and eliminates a source of unpredictable behavior) We have had to reject certain parallelization strategies in LLD as well because even though the result would always be a semantically identical executable, it would not be bit-identical. See e.g. the discussions surrounding parallel string merging: https://reviews.llvm.org/D27146 https://reviews.llvm.org/D27146 <-- fastest technique, but non-deterministic output https://reviews.llvm.org/D27152 https://reviews.llvm.org/D27152 <-- slower but deterministic technique https://reviews.llvm.org/D27155 https://reviews.llvm.org/D27155 <-- really cool technique that relies on a linearly probed hash table (and sorting just runs of full buckets instead of the entire array) to guarantee deterministic output despite concurrent hash table insertion.
- comex 10y ago
  As I said in a different reply, I think nondeterminism is an acceptable sacrifice for development builds, which is where incremental linking would be most useful. That said, it's definitely possible to get some speedup from incrementality while keeping the output deterministic; you'd have to move symbols around, which of course requires relocating everything that points to them, but (with the help of a cache file that stores where the relocations ended up in the output binary) this could probably be performed significantly more quickly than re-reading all the .o files and doing name lookups. But admittedly this would significantly reduce the benefit.
  - chisophugis 10y ago
    I agree. It's definitely possible. It's just that the actual benefit is far from reducing link time to "O(changes in the input)" and it would introduce significant complexity into the linker (and keeping LLD simple and easy to follow is a high priority). It's definitely an open research area. > That said, it's definitely possible to get some speedup from incrementality while keeping the output deterministic; you'd have to move symbols around, which of course requires relocating everything that points to them, but (with the help of a cache file that stores where the relocations ended up in the output binary) this could probably be performed significantly more quickly than re-reading all the .o files and doing name lookups. But admittedly this would significantly reduce the benefit. Yeah. It's not clear if that would be better in practice than a conservative padding scheme + a patching-based approach. "move symbols around, which of course requires relocating everything that points to them" sounds a lot like what the linker already spends most of its time doing (in its fastest mode). In its fastest mode, LLD actually spends most of its time memcpy'ing into the output file and applying relocations. This happens after symbol resolution and does not touch the input .o files except to read the data being copied into the output file. The information needed for applying the relocations is read with a bare minimum of pointer chasing (only 2 serially dependent cache misses last I looked) and does not do any hash table lookup into the symbol table nor does it look at any symbol name string.

rui314 10y ago

Linkers have to copy large amount of data from object files to an output file, and that is inevitably slow. But LLD is not that bad if you pass -O0 (which disables string merging, which is computationally expensive). For example, LLD takes 6.7 seconds to link clang with debug info on my machine. $ time ld.lld <omit> -O0 -o bin/clang-4.0 real 0m6.689s Copying the output file to other file takes 2.6 seconds. $ time cp bin/clang-4.0 foo real 0m2.657s So, LLD is only 2.5x slower than cp in this case. That's not too bad, as apparently the linker has many more things to do than the cp command.

jblow 10y ago
Is your test mostly waiting on a mechanical hard drive? If so, then "2.5x slower than cp" could mean "a very large amount slower than cp" once you remove that overhead. Whereas I have not done your specific test, I know that for the file sizes of executables I deal with in everyday work (around 10MB), the amount of time I wait for linking is woefully disproportionate.
- rui314 10y ago
  It is on an SSD.
  - e12e 10y ago
    It'd be interesting to see the numbers of a ramdisk cp/link as well. With ssd being so much faster than mechanical disks, people sometimes forget that ram is faster still.
- aseipp 10y ago
  For a comparison, an optimized release build of Clang 5.0 trunk (from a few days ago, built with Clang 5.0 trunk from like a week ago) with assertions enabled is 87mb -- with the LLVM libraries linked in, but dynamically linked to system libraries, on my Fedora 25 machine. A debug build of clang is normally hundreds of megabytes (~600mb IIRC, and normal linkers go bonkers dealing with it), so if LLD is actually only 2.5x slower than 'cp' at -O0, that's quite good I think. The next question is how much memory LLD uses vs the competition in this test...