Propeller: Profile-guided, optimizing, large-scale LLVM-based relinker | Hacker News Reader

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

github.com

56 pointsuluyol27 comments

> 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…

Isn’t the text segment actually the machine instructions?

Yes.

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.

Yes, I get that; I am curious what goes into a binary with 300 MB of code in it.

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_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).

> they are using static linking

Ah, that would probably be it.

Is Google's rationale for using static linking at this massive scale published anywhere?

I don't know Google's rationale, but static linked libraries usually run a little faster than dynamic linked ones.

> 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.

> 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))

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. Perhaps the optimization needs more work?

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)

> 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))

If you look at the resulting binaries, they don't work as well as you might think.

Not sure why you get downvoted. I've seen presentations by Ubisoft for example where they replaced templated vectors because of the code bloat which added up too much in their large code base.

(That’s only by default, you can panic=abort and not get that overhead too.)

Rust still has some room to improve over C++ here. Because it knows up-front which operations generic code can use on its type parameters, it can do things like "polymorphization": https://github.com/rust-lang/rust/pull/69749

This means the compiler will automatically detect how much duplication is actually needed ahead of time, eliminating the need for after-the-fact identical code folding. (This should also drastically reduce compile times for some programs!)

And it could go even further than that. For example, some code could be duplicated based only on the size+alignment of its parameters (C#-style generics without a JIT). The analysis could be finer-grained than per-function, sharing parts of a function across instantiations (kind of like outlining).

With the detection happening this early in the pipeline, the compiler could even tell the user about it and guide them toward techniques that reduce the amount of duplication. (A different language could go further, of course.)

That’s a relatively normal binary size for a ~1 million LOC C++ server from my experience. (statically linked).

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

It's a fork of LLVM; it seems to be about 800 commits ahead of LLVM master.

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/135...

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

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

Can anyone summarize differences with previous work like

https://cseweb.ucsd.edu/classes/sp00/cse231/dynamopldi.pdf ?

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.

The closest previous work would rather be Facebook BOLT I believe: https://github.com/facebookincubator/BOLT

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/proceedin...).

Interesting stuff!

Reply on news.ycombinator.com