4 ms·

Over many years I've come across several discussions about fast linkers and how compile times sped up so much by replacing one linker with a faster one, but I'v

Over many years I've come across several discussions about fast linkers and how compile times sped up so much by replacing one linker with a faster one, but I've never found out what about them makes them normally so slow. Can anyone shed some light please?

ripley12 3y ago
This isn't the whole story, but linking is CPU-intensive and older linkers are mostly single-threaded. A lot of the performance gains come from doing work in parallel, which makes for a big improvement on beefy modern multicore CPUs. Rui's given some good talks about Mold if you want more info: https://www.youtube.com/watch?v=hAt3kCalE0Y https://www.youtube.com/watch?v=hAt3kCalE0Y
- glandium 3y ago
  Even single-threaded, modern linkers (lld, mold, even gold) are faster than BFD ld, which is notoriously slow, and sadly still the default you get on Linux.
JonChesterfield 3y ago
Yep. A linker in the best case would run as fast as cat. Paste the binaries together, done. Disk I/O was a problem back when we used spinning rust but less so now. What takes time is rewriting stuff as you go. Running the relocation tables to insert addresses into the code is cheap. Deadstripping sections is fairly cheap, deadstripping individual basic blocks within functions takes a lot more analysis and thus time. Deduplicating constant strings is a good idea but involves streaming them all into a hashtable of some sort. Maybe you want them to share common suffixes, more work. Deduplicating, deadstripping, rewriting debug information takes time. Debug builds can feature many gigabytes of dwarf to rewrite. Oddly enough that the linker is scriptable, as in you can give it a program that it interprets, doesn't seem to be a significant cost. Probably because the script in question is quite short and somewhat limited in functionality. Historically lld was very fast because it didn't bother doing any of the debug munging or other deduplication. Lld ran fast but the output binary was big. I'm several years out of the linker performance game now so don't know the current status. In particular I don't know where mold or lld are in terms of quality of output vs their own performance.
canucker2016 3y ago
Best source I've read is Ian Taylor's blog about his work on the gold linker: https://www.airs.com/blog/archives/38 https://www.airs.com/blog/archives/38 "Once again, the goal is speed, in this case being faster than my second linker. That linker has been significantly slowed down over the years by adding support for ELF and for shared libraries. This support was patched in rather than being designed in. Future plans for the new linker include support for incremental linking–which is another way of increasing speed." Just think of the apps that were written in early Unix days - simple single-purpose apps, probably just one source code file , just one obj and libc to link together, no shared libs et al. The linker code just grew organically as new "must-have" features were added. Correctness of features was more important than speed esp. when spinning rust was a limiting factor.
- canucker2016 3y ago
  A PDF for the lld linker has some more info on speedups over ld and gold: See https://llvm.org/devmtg/2017-10/slides/Ueyama-lld.pdf https://llvm.org/devmtg/2017-10/slides/Ueyama-lld.pdf

ripley12 3y ago

This isn't the whole story, but linking is CPU-intensive and older linkers are mostly single-threaded. A lot of the performance gains come from doing work in parallel, which makes for a big improvement on beefy modern multicore CPUs. Rui's given some good talks about Mold if you want more info: https://www.youtube.com/watch?v=hAt3kCalE0Y https://www.youtube.com/watch?v=hAt3kCalE0Y

glandium 3y ago
Even single-threaded, modern linkers (lld, mold, even gold) are faster than BFD ld, which is notoriously slow, and sadly still the default you get on Linux.

JonChesterfield 3y ago

Yep. A linker in the best case would run as fast as cat. Paste the binaries together, done. Disk I/O was a problem back when we used spinning rust but less so now. What takes time is rewriting stuff as you go. Running the relocation tables to insert addresses into the code is cheap. Deadstripping sections is fairly cheap, deadstripping individual basic blocks within functions takes a lot more analysis and thus time. Deduplicating constant strings is a good idea but involves streaming them all into a hashtable of some sort. Maybe you want them to share common suffixes, more work. Deduplicating, deadstripping, rewriting debug information takes time. Debug builds can feature many gigabytes of dwarf to rewrite. Oddly enough that the linker is scriptable, as in you can give it a program that it interprets, doesn't seem to be a significant cost. Probably because the script in question is quite short and somewhat limited in functionality. Historically lld was very fast because it didn't bother doing any of the debug munging or other deduplication. Lld ran fast but the output binary was big. I'm several years out of the linker performance game now so don't know the current status. In particular I don't know where mold or lld are in terms of quality of output vs their own performance.

canucker2016 3y ago

Best source I've read is Ian Taylor's blog about his work on the gold linker: https://www.airs.com/blog/archives/38 https://www.airs.com/blog/archives/38 "Once again, the goal is speed, in this case being faster than my second linker. That linker has been significantly slowed down over the years by adding support for ELF and for shared libraries. This support was patched in rather than being designed in. Future plans for the new linker include support for incremental linking–which is another way of increasing speed." Just think of the apps that were written in early Unix days - simple single-purpose apps, probably just one source code file , just one obj and libc to link together, no shared libs et al. The linker code just grew organically as new "must-have" features were added. Correctness of features was more important than speed esp. when spinning rust was a limiting factor.

canucker2016 3y ago
A PDF for the lld linker has some more info on speedups over ld and gold: See https://llvm.org/devmtg/2017-10/slides/Ueyama-lld.pdf https://llvm.org/devmtg/2017-10/slides/Ueyama-lld.pdf