5 ms·

Propeller: Profile-guided, optimizing, large-scale LLVM-based relinker

56 points by uluyol 7y ago

chmaynard 7y ago
Propeller looks very interesting. Judging from the number of commits, the project has been around a long while. Does anyone know its history?
- saagarjha 7y ago
  It's a fork of LLVM; it seems to be about 800 commits ahead of LLVM master.
- ddcc7 7y ago
  It's a fairly recent project, you can see the original announcement from the team on the LLVM mailing list in September 2019: https://lists.llvm.org/pipermail/llvm-dev/2019-September/135393.html https://lists.llvm.org/pipermail/llvm-dev/2019-September/135...
saagarjha 7y ago
> It has scalability issues and to rewrite a binary with a ~300M text segment size I'm curious what kinds of tasks require a binary with a 300 MB text size…
- matt123456789 7y ago
  Isn’t the text segment actually the machine instructions?
  - saagarjha 7y ago
    Yes.
- lvh 7y ago
  Text _segment_ size. That's executable instructions; presumably it makes a bit more sense that Google would have a binary with 300MB worth of instructions laying around.
  - saagarjha 7y ago
    Yes, I get that; I am curious what goes into a binary with 300 MB of code in it.
    - Joky 7y ago
      Google has very large applications, but also they are using static linking: imagine that you statically link all the possible dependencies in a single binary for each application. 300MB is not considered a large binary at Google actually, I don't know what is public but you may look at Table 2 in this publication for instance: https://www.researchgate.net/publication/314105281_ThinLTO_Scalable_and_incremental_LTO https://www.researchgate.net/publication/314105281_ThinLTO_S... I repro here some data, there is a bit more in the paper: Clang 1.9k Files, 217MB (-g0), 3554MB (-g) Chromium 17.8k Files 706MB (-g0), 7544MB (-g) Ad Delivery 13.8k Files 1073MB (-g0), 7469MB (-g) (this is the number of object file that are participating in the link).
      - saagarjha 7y ago
        > they are using static linking Ah, that would probably be it.
      - mwcampbell 7y ago
        Is Google's rationale for using static linking at this massive scale published anywhere?
        jlokier 7y ago
        I don't know Google's rationale, but static linked libraries usually run a little faster than dynamic linked ones.
- cwzwarich 7y ago
  > I'm curious what kinds of tasks require a binary with a 300 MB text size… C++ lends itself to bloated binaries. Template instantiations are duplicated even for types where the instantiations could have identical code. Compilers have traditionally favored overly aggressive inlining over whole-program optimization. Rust didn't solve the problem; it just duplicated the C++ approach, and made it worse by effectively compiling with the equivalent of C++ exceptions enabled. The next great systems language should target binary size and CPU frontend overhead.
  - jcelerier 7y ago
    > Template instantiations are duplicated even for types where the instantiations could have identical code. compilers and linkers had identical code folding optimizations for a looooong time (20+ years for msvc, a decade or so for GNU gold (--icf option) and GCC (-fipa-icf))
    - saagarjha 7y ago
      I was going to reply with a similar comment, but I'm unable to actually get this to happen when I tried it now: https://godbolt.org/z/4VkEQc https://godbolt.org/z/4VkEQc. Perhaps the optimization needs more work?
      - jcelerier 7y ago
        No, it's just that the assembly output of godbolt happens before these optimization phases. On my machine I get no unsigned instantiation, only the signed one : $ objdump -D a.out | c++filt | grep foo 563: e8 21 01 00 00 callq 689 <bool foo<int>(int)> 56c: e8 18 01 00 00 callq 689 <bool foo<int>(int)> 0000000000000689 <bool foo<int>(int)>: and the main : 0000000000000560 <main>: 560: 53 push %rbx 561: 31 ff xor %edi,%edi 563: e8 21 01 00 00 callq 689 <bool foo<int>(int)> 568: 31 ff xor %edi,%edi 56a: 89 c3 mov %eax,%ebx 56c: e8 18 01 00 00 callq 689 <bool foo<int>(int)> 571: 0f b6 d3 movzbl %bl,%edx 574: 48 8d 3d b1 01 00 00 lea 0x1b1(%rip),%rdi # 72c <_IO_stdin_used+0x4> 57b: 0f b6 f0 movzbl %al,%esi 57e: 31 c0 xor %eax,%eax 580: e8 cb ff ff ff callq 550 <printf@plt> 585: 31 c0 xor %eax,%eax 587: 5b pop %rbx 588: c3 retq 589: 00 00 add %al,(%rax) 58b: 00 00 add %al,(%rax) 58d: 00 00 add %al,(%rax)
- jupp0r 7y ago
  That’s a relatively normal binary size for a ~1 million LOC C++ server from my experience. (statically linked).
fulafel 7y ago
Can anyone summarize differences with previous work like https://cseweb.ucsd.edu/classes/sp00/cse231/dynamopldi.pdf https://cseweb.ucsd.edu/classes/sp00/cse231/dynamopldi.pdf ?
- saagarjha 7y ago
  This is profile-guided optimization: you run your program, collect data on what code runs, and use it to optimize the layout of your program. Dynamo runs optimizations at runtime.
- Joky 7y ago
  The closest previous work would rather be Facebook BOLT I believe: https://github.com/facebookincubator/BOLT https://github.com/facebookincubator/BOLT
  - fulafel 7y ago
    Right, I misremembered what Dynamo does - from the Bolt paper references I see that I was actually thinking of Spike (https://www.usenix.org/legacy/publications/library/proceedings/usenix-nt97/full_papers/cohn/cohn.pdf https://www.usenix.org/legacy/publications/library/proceedin...). Interesting stuff!
dang 7y ago
Related current thread: https://news.ycombinator.com/item?id=22654229 https://news.ycombinator.com/item?id=22654229
fulafel 7y ago
Now if we could only do the same profile guided layout optimizations with data...

56 points by uluyol 7y ago

Propeller looks very interesting. Judging from the number of commits, the project has been around a long while. Does anyone know its history?

saagarjha 7y ago
It's a fork of LLVM; it seems to be about 800 commits ahead of LLVM master.
ddcc7 7y ago
It's a fairly recent project, you can see the original announcement from the team on the LLVM mailing list in September 2019: https://lists.llvm.org/pipermail/llvm-dev/2019-September/135393.html https://lists.llvm.org/pipermail/llvm-dev/2019-September/135...

saagarjha 7y ago

> It has scalability issues and to rewrite a binary with a ~300M text segment size I'm curious what kinds of tasks require a binary with a 300 MB text size…

matt123456789 7y ago
Isn’t the text segment actually the machine instructions?
- saagarjha 7y ago
  Yes.
lvh 7y ago
Text _segment_ size. That's executable instructions; presumably it makes a bit more sense that Google would have a binary with 300MB worth of instructions laying around.
- saagarjha 7y ago
  Yes, I get that; I am curious what goes into a binary with 300 MB of code in it.
  - Joky 7y ago
    Google has very large applications, but also they are using static linking: imagine that you statically link all the possible dependencies in a single binary for each application. 300MB is not considered a large binary at Google actually, I don't know what is public but you may look at Table 2 in this publication for instance: https://www.researchgate.net/publication/314105281_ThinLTO_Scalable_and_incremental_LTO https://www.researchgate.net/publication/314105281_ThinLTO_S... I repro here some data, there is a bit more in the paper: Clang 1.9k Files, 217MB (-g0), 3554MB (-g) Chromium 17.8k Files 706MB (-g0), 7544MB (-g) Ad Delivery 13.8k Files 1073MB (-g0), 7469MB (-g) (this is the number of object file that are participating in the link).
    - saagarjha 7y ago
      > they are using static linking Ah, that would probably be it.
    - mwcampbell 7y ago
      Is Google's rationale for using static linking at this massive scale published anywhere?
      - jlokier 7y ago
        I don't know Google's rationale, but static linked libraries usually run a little faster than dynamic linked ones.
cwzwarich 7y ago
> I'm curious what kinds of tasks require a binary with a 300 MB text size… C++ lends itself to bloated binaries. Template instantiations are duplicated even for types where the instantiations could have identical code. Compilers have traditionally favored overly aggressive inlining over whole-program optimization. Rust didn't solve the problem; it just duplicated the C++ approach, and made it worse by effectively compiling with the equivalent of C++ exceptions enabled. The next great systems language should target binary size and CPU frontend overhead.
- jcelerier 7y ago
  > Template instantiations are duplicated even for types where the instantiations could have identical code. compilers and linkers had identical code folding optimizations for a looooong time (20+ years for msvc, a decade or so for GNU gold (--icf option) and GCC (-fipa-icf))
  - saagarjha 7y ago
    I was going to reply with a similar comment, but I'm unable to actually get this to happen when I tried it now: https://godbolt.org/z/4VkEQc https://godbolt.org/z/4VkEQc. Perhaps the optimization needs more work?
    - jcelerier 7y ago
      No, it's just that the assembly output of godbolt happens before these optimization phases. On my machine I get no unsigned instantiation, only the signed one : $ objdump -D a.out | c++filt | grep foo 563: e8 21 01 00 00 callq 689 <bool foo<int>(int)> 56c: e8 18 01 00 00 callq 689 <bool foo<int>(int)> 0000000000000689 <bool foo<int>(int)>: and the main : 0000000000000560 <main>: 560: 53 push %rbx 561: 31 ff xor %edi,%edi 563: e8 21 01 00 00 callq 689 <bool foo<int>(int)> 568: 31 ff xor %edi,%edi 56a: 89 c3 mov %eax,%ebx 56c: e8 18 01 00 00 callq 689 <bool foo<int>(int)> 571: 0f b6 d3 movzbl %bl,%edx 574: 48 8d 3d b1 01 00 00 lea 0x1b1(%rip),%rdi # 72c <_IO_stdin_used+0x4> 57b: 0f b6 f0 movzbl %al,%esi 57e: 31 c0 xor %eax,%eax 580: e8 cb ff ff ff callq 550 <printf@plt> 585: 31 c0 xor %eax,%eax 587: 5b pop %rbx 588: c3 retq 589: 00 00 add %al,(%rax) 58b: 00 00 add %al,(%rax) 58d: 00 00 add %al,(%rax)
jupp0r 7y ago
That’s a relatively normal binary size for a ~1 million LOC C++ server from my experience. (statically linked).

fulafel 7y ago

Can anyone summarize differences with previous work like https://cseweb.ucsd.edu/classes/sp00/cse231/dynamopldi.pdf https://cseweb.ucsd.edu/classes/sp00/cse231/dynamopldi.pdf ?

saagarjha 7y ago
This is profile-guided optimization: you run your program, collect data on what code runs, and use it to optimize the layout of your program. Dynamo runs optimizations at runtime.
Joky 7y ago
The closest previous work would rather be Facebook BOLT I believe: https://github.com/facebookincubator/BOLT https://github.com/facebookincubator/BOLT
- fulafel 7y ago
  Right, I misremembered what Dynamo does - from the Bolt paper references I see that I was actually thinking of Spike (https://www.usenix.org/legacy/publications/library/proceedings/usenix-nt97/full_papers/cohn/cohn.pdf https://www.usenix.org/legacy/publications/library/proceedin...). Interesting stuff!

dang 7y ago

Related current thread: https://news.ycombinator.com/item?id=22654229 https://news.ycombinator.com/item?id=22654229

fulafel 7y ago

Now if we could only do the same profile guided layout optimizations with data...