5 ms·

It's curious that linking speed can be improved by so much when gold was itself written for speed only 7 years ago. I wonder, what's the trick?

by evmar 11y ago

mschuster91 11y ago
Probably because the GNU utils are written with support for each and every architecture and format in this world in mind. lld however supports only x86_64, according to the blogpost. It's got to be fast if the cruft is cut. What are the most dominant archs in actual usage today anyways? I'd guess x86(_64), armv6/v7/64, MIPS for cheap/crap routers and some SPARC... and ELF as the dominant binary format on *nix and PE/COFF on win32/64/arm.
- chx 11y ago
  Are you sure MIPS is only used in crap routers? For example https://www.ubnt.com/edgemax/edgerouter-lite/ https://www.ubnt.com/edgemax/edgerouter-lite/ this is MIPS as documented for example https://wiki.gentoo.org/wiki/MIPS/ERLite-3 https://wiki.gentoo.org/wiki/MIPS/ERLite-3 here. Also, one of the first 802.11ac Wave 2 routers from Xirrus, that's also MIPS, isn't it? http://www.wireless-mag.com/News/34108/xirrus-selects-cavium-octeon-iii-processors-for-80211ac-wave-2-wi-fi-.aspx http://www.wireless-mag.com/News/34108/xirrus-selects-cavium...
  - kenz0r 11y ago
    MIPS (Cavium and Broadcom) and PowerPC (Freescale QorIQ) are big players in the Networking market currently, but the next generation of processors from those companies mentioned above will be ARMv8
    - justincormack 11y ago
      Cavium is still producing MIPS64 as well as ARM64, although whether they will continue to do so is unclear.
  - gsnedders 11y ago
    MIPS is still a big player in the TV market, and similar devices (DVD, BluRay players etc.).
- ithkuil 11y ago
  While the gold linker is now part of the GNU binutils distribution, it's speed advantaged stem exactly from what you mentioned. The origin question is how lld can improve on that even further. Is there any document such as http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/34417.pdf http://static.googleusercontent.com/media/research.google.co... for gold ? "Unlike the GNU linker, gold doesn't use the BFD library to process object files. While this limits supported formats to ELF only, it's also claimed to result in a cleaner and faster implementation without an additional abstraction layer. Complete removal of BFD was cited as a reason to create a new linker from scratch rather than incrementally improve the GNU linker.[5]" -- https://en.wikipedia.org/wiki/Gold_(linker) https://en.wikipedia.org/wiki/Gold_(linker) "Gold is known to work on x86 and x86-64, PowerPC (partially) and ARM." -- https://fedoraproject.org/wiki/GoldLinking https://fedoraproject.org/wiki/GoldLinking
- imglorp 11y ago
  We're seeing a resurgence in multiple architectures as the world hurtles away from desktops. While it's good to have GNU alternatives that do some things better, portability is more important than ever. This means we need to keep adding toolchains for new arches as they come up. For example, you missed Snapdragon and A4, which together are probably around a billion devices. I don't want to detract from LLVM, but the community needs to keep the GNU one prospering if we want to avoid proprietary tool hell.
  - mschuster91 11y ago
    > For example, you missed Snapdragon and A4, which together are probably around a billion devices. Snapdragon and Apples Ax CPUs are all ARM, though.
    - imglorp 11y ago
      TIL, thx.
  - Sanddancer 11y ago
    Aye, and the rest of the LLVM toolchain is supporting a huge number of architectures, some of which, like GPUs, that the GNU toolset doesn't support. Like any project, LLD is supporting the most popular architecture first, with roadmapped items for further architectures once that is finished. Keep in mind that binutils didn't support all the architectures it did with v1, it took porting work as well. Furthermore, I'd disagree that the GNU binutils are the only toolset that are keeping us from proprietary hell. The LLVM development model, with fairly frequent releases and updates gives a huge push for toolchain users to contribute their patches. Sony, for example, had been grumpily looking at all the new features in LLVM being added as they were developing the toolchain for the PS4 because they couldn't add their contributions into the LLVM toolchain, and couldn't import the LLVM updates to avoid DNF syndrome. I'd even go as far as to say that LLVM is our best hope of keeping the GNU project honest. A competing, Free, toolchain means that the GNU project cannot feign ignorance of the new features that llvm is bringing to the development table. The abilities that llvm offer are slowly trickling into gcc, even if certain parties are fearful of what effects those changes might bring. The right mix of cooperation and competition can and does bring wonderful things.
- legulere 11y ago
  It's not only CPU architectures, but also operating systems. For instance the `-akeyword`(HP/UX compat), `-z`, `-Y` (Solaris compat), `-assert` (SunOS compat) `-Qy` (System V Release 4 compat) options in GNU `ld` (http://ftp.gnu.org/old-gnu/Manuals/ld-2.9.1/html_mono/ld.html http://ftp.gnu.org/old-gnu/Manuals/ld-2.9.1/html_mono/ld.htm...) Then there's also compatibility with MRI linkers in GNU ld
hthh 11y ago
I think this is the COFF document which they say "is directly applicable". https://github.com/llvm-mirror/lld/blob/master/COFF/README.md https://github.com/llvm-mirror/lld/blob/master/COFF/README.m... I'm guessing the speed difference comes from this linker using a different approach to symbol resolution which requires visiting files fewer times, but I'm not sure.
DannyBee 11y ago
" lld is not at feature parity with gold yet, so it is too early to make a conclusion, but we are working hard to maintain or improve lld’s speed while adding more features." LLD does not yet support string section merging, which iant mentions is the slowest part of gold. So "so far so good", but "jury is still out"
- rwmj 11y ago
  So wait, modifying gold to fix (or even remove) the slow string section merging wasn't a possibility? It sounds a lot less work than writing a completely new linker.
  - msbarnett 11y ago
    gold is GPL v3. Even if that route was less work, it wouldn't be compatible with the LLVM project's goal to produce a permissive-licensed suite of tools (UIUC, broadly similar to BSD). This matters to important LLVM backers like Apple, who employ a lot of the core devs.
    - DannyBee 11y ago
      "LLVM project's goal to produce a permissive-licensed suite of tools" This is really far down the goal list ;-) "This matters to important LLVM backers like Apple, who employ a lot of the core devs." As mentioned numerous times, the vast majority of core devs are non-Apple at this point. More to the point here, the person who wrote the blog post, and is responsible for the vast majority of LLD as it exists today, ruiu, works at Google (happily, ELF is being pushed along by others as well) I'm responsible for the entire C++ platform there, and I can happily state that i don't give a single whit about whether LLD is permissively licensed or not.
  - DannyBee 11y ago
    gold is deliberately ELF only, LLD supports PE, ELF, Mach-O.
rui314 11y ago
As I wrote in the blog post, we didn't take a closer look at the performance difference, and I know that "measure, don't guess" is maxim. But if I risk it, I believe there are some differences that could make a difference in performance as described in the following chapter. (This is for COFF but applicable to ELF.) https://github.com/llvm-mirror/lld/blob/master/COFF/README.md#performance https://github.com/llvm-mirror/lld/blob/master/COFF/README.m... We can't reach a conclusion until we add a linker script support to lld, though.

It's curious that linking speed can be improved by so much when gold was itself written for speed only 7 years ago. I wonder, what's the trick?

by evmar 11y ago

It's curious that linking speed can be improved by so much when gold was itself written for speed only 7 years ago. I wonder, what's the trick?

mschuster91 11y ago

Probably because the GNU utils are written with support for each and every architecture and format in this world in mind. lld however supports only x86_64, according to the blogpost. It's got to be fast if the cruft is cut. What are the most dominant archs in actual usage today anyways? I'd guess x86(_64), armv6/v7/64, MIPS for cheap/crap routers and some SPARC... and ELF as the dominant binary format on *nix and PE/COFF on win32/64/arm.

chx 11y ago
Are you sure MIPS is only used in crap routers? For example https://www.ubnt.com/edgemax/edgerouter-lite/ https://www.ubnt.com/edgemax/edgerouter-lite/ this is MIPS as documented for example https://wiki.gentoo.org/wiki/MIPS/ERLite-3 https://wiki.gentoo.org/wiki/MIPS/ERLite-3 here. Also, one of the first 802.11ac Wave 2 routers from Xirrus, that's also MIPS, isn't it? http://www.wireless-mag.com/News/34108/xirrus-selects-cavium-octeon-iii-processors-for-80211ac-wave-2-wi-fi-.aspx http://www.wireless-mag.com/News/34108/xirrus-selects-cavium...
- kenz0r 11y ago
  MIPS (Cavium and Broadcom) and PowerPC (Freescale QorIQ) are big players in the Networking market currently, but the next generation of processors from those companies mentioned above will be ARMv8
  - justincormack 11y ago
    Cavium is still producing MIPS64 as well as ARM64, although whether they will continue to do so is unclear.
- gsnedders 11y ago
  MIPS is still a big player in the TV market, and similar devices (DVD, BluRay players etc.).
ithkuil 11y ago
While the gold linker is now part of the GNU binutils distribution, it's speed advantaged stem exactly from what you mentioned. The origin question is how lld can improve on that even further. Is there any document such as http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/34417.pdf http://static.googleusercontent.com/media/research.google.co... for gold ? "Unlike the GNU linker, gold doesn't use the BFD library to process object files. While this limits supported formats to ELF only, it's also claimed to result in a cleaner and faster implementation without an additional abstraction layer. Complete removal of BFD was cited as a reason to create a new linker from scratch rather than incrementally improve the GNU linker.[5]" -- https://en.wikipedia.org/wiki/Gold_(linker) https://en.wikipedia.org/wiki/Gold_(linker) "Gold is known to work on x86 and x86-64, PowerPC (partially) and ARM." -- https://fedoraproject.org/wiki/GoldLinking https://fedoraproject.org/wiki/GoldLinking
imglorp 11y ago
We're seeing a resurgence in multiple architectures as the world hurtles away from desktops. While it's good to have GNU alternatives that do some things better, portability is more important than ever. This means we need to keep adding toolchains for new arches as they come up. For example, you missed Snapdragon and A4, which together are probably around a billion devices. I don't want to detract from LLVM, but the community needs to keep the GNU one prospering if we want to avoid proprietary tool hell.
- mschuster91 11y ago
  > For example, you missed Snapdragon and A4, which together are probably around a billion devices. Snapdragon and Apples Ax CPUs are all ARM, though.
  - imglorp 11y ago
    TIL, thx.
- Sanddancer 11y ago
  Aye, and the rest of the LLVM toolchain is supporting a huge number of architectures, some of which, like GPUs, that the GNU toolset doesn't support. Like any project, LLD is supporting the most popular architecture first, with roadmapped items for further architectures once that is finished. Keep in mind that binutils didn't support all the architectures it did with v1, it took porting work as well. Furthermore, I'd disagree that the GNU binutils are the only toolset that are keeping us from proprietary hell. The LLVM development model, with fairly frequent releases and updates gives a huge push for toolchain users to contribute their patches. Sony, for example, had been grumpily looking at all the new features in LLVM being added as they were developing the toolchain for the PS4 because they couldn't add their contributions into the LLVM toolchain, and couldn't import the LLVM updates to avoid DNF syndrome. I'd even go as far as to say that LLVM is our best hope of keeping the GNU project honest. A competing, Free, toolchain means that the GNU project cannot feign ignorance of the new features that llvm is bringing to the development table. The abilities that llvm offer are slowly trickling into gcc, even if certain parties are fearful of what effects those changes might bring. The right mix of cooperation and competition can and does bring wonderful things.
legulere 11y ago
It's not only CPU architectures, but also operating systems. For instance the `-akeyword`(HP/UX compat), `-z`, `-Y` (Solaris compat), `-assert` (SunOS compat) `-Qy` (System V Release 4 compat) options in GNU `ld` (http://ftp.gnu.org/old-gnu/Manuals/ld-2.9.1/html_mono/ld.html http://ftp.gnu.org/old-gnu/Manuals/ld-2.9.1/html_mono/ld.htm...) Then there's also compatibility with MRI linkers in GNU ld

hthh 11y ago

I think this is the COFF document which they say "is directly applicable". https://github.com/llvm-mirror/lld/blob/master/COFF/README.md https://github.com/llvm-mirror/lld/blob/master/COFF/README.m... I'm guessing the speed difference comes from this linker using a different approach to symbol resolution which requires visiting files fewer times, but I'm not sure.

DannyBee 11y ago

" lld is not at feature parity with gold yet, so it is too early to make a conclusion, but we are working hard to maintain or improve lld’s speed while adding more features." LLD does not yet support string section merging, which iant mentions is the slowest part of gold. So "so far so good", but "jury is still out"

rwmj 11y ago
So wait, modifying gold to fix (or even remove) the slow string section merging wasn't a possibility? It sounds a lot less work than writing a completely new linker.
- msbarnett 11y ago
  gold is GPL v3. Even if that route was less work, it wouldn't be compatible with the LLVM project's goal to produce a permissive-licensed suite of tools (UIUC, broadly similar to BSD). This matters to important LLVM backers like Apple, who employ a lot of the core devs.
  - DannyBee 11y ago
    "LLVM project's goal to produce a permissive-licensed suite of tools" This is really far down the goal list ;-) "This matters to important LLVM backers like Apple, who employ a lot of the core devs." As mentioned numerous times, the vast majority of core devs are non-Apple at this point. More to the point here, the person who wrote the blog post, and is responsible for the vast majority of LLD as it exists today, ruiu, works at Google (happily, ELF is being pushed along by others as well) I'm responsible for the entire C++ platform there, and I can happily state that i don't give a single whit about whether LLD is permissively licensed or not.
- DannyBee 11y ago
  gold is deliberately ELF only, LLD supports PE, ELF, Mach-O.

rui314 11y ago

As I wrote in the blog post, we didn't take a closer look at the performance difference, and I know that "measure, don't guess" is maxim. But if I risk it, I believe there are some differences that could make a difference in performance as described in the following chapter. (This is for COFF but applicable to ELF.) https://github.com/llvm-mirror/lld/blob/master/COFF/README.md#performance https://github.com/llvm-mirror/lld/blob/master/COFF/README.m... We can't reach a conclusion until we add a linker script support to lld, though.