Link-Time Optimisation (LTO)

by signa11 • 3 years ago

118 51 3 years ago

pjmlp2• 3 years ago

Those other language implementation strategies do not offer LTO-like features (that I know of), so I have ignored them here.

JVM implementations (and ART), alongside CLR do such optimizations.

Furthermore, nowadays PGO is part of the process as well, so the information can be carried over across runs, used as means for the JIT to quickly achieve the optimal execution point, and carry over from there instead of starting over from scratch every time.

foobazgt2• 3 years ago

Yeah, this was a very strange statement to read.

In fact, it's even more wrong than that. The ability for managed runtimes to perform LTO across dynamic code loading means you're even able to get LTO across code your compiler has never witnessed - e.g. plugins written by 3rd parties.

saagarjha• 3 years ago

I think it's just usually rolled up into optimizations with other names, like "speculative inlining".

iruoy• 3 years ago

On tuesday .NET 8 will be released which has this aswell.

https://devblogs.microsoft.com/dotnet/performance-improvemen...

jryans5• 3 years ago

Ah hmm, I guess part of the problem is I am less familiar with JVM, CLR, etc. features in this space.

Does anyone know of articles that go into a bit more on precisely the kinds of LTO they offer? I'll update the guide once I understand the situation a bit better.

pjmlp2• 3 years ago

Some examples are divirtualization across dynamic libraries, or code inlining, which is quite basic stuff for those implementations.

Here is a 2015 paper for OpenJDK,

https://cr.openjdk.org/~vlivanov/talks/2015_JIT_Overview.pdf

Modern ART has a bit of everything, Assembly written interpreter for fast startup, followed by a JIT stage with PGO capabilities, followed by an AOT compiler that AOT compiles (with LTO) when the device is idle, and uploading PGO data into the Play Store, so that incrementally the same devices collaborate to the optimal PGO data set.

https://source.android.com/docs/core/runtime/jit-compiler

IBM and Azul JVMs have similar approaches with their cloud based JIT infrastructure.

https://developer.ibm.com/articles/jitserver-optimize-your-j...

https://www.azul.com/products/intelligence-cloud/cloud-nativ...

twic2• 3 years ago

I'm not sure i would agree that the JVM and its ilk do LTO. They compile code to machine code at runtime, after loading the code it calls, and often after spending some time interpreting it. That means they can do interprocedural optimisations of the kind LTO can do (and then some). But they don't have the separate stages of compilation and linking that many ahead-of-time compiled languages do, which means they don't do linking, which surely means they can't do link-time optimisation!

vkoskiv• 3 years ago

I learned about LTO a few years ago, and it gave a significant runtime speed boost to my hobby project, but as far as I can tell, CMake still just has `CMAKE_INTERPROCEDURAL_OPTIMIZATION` as a boolean on/off flag, it doesn't seem to let you specify parallel jobs.

menaerus3• 3 years ago

it doesn't seem to let you specify parallel jobs.

You don't need to if you're using the LLVM linker (lld) - by default it will use all of your HW threads (nr of cores).

    lld --help | grep thread
      --threads=<value>       Number of threads. '1' disables multi-threading. By default all available hardware threads are used

mgaunard7• 3 years ago

Why not just use mold?

BearOso2• 3 years ago

Yes, but that CMake option also doesn't specify thin LTO, so you're only going to get 1 thread with LLVM.

dundarious2• 3 years ago

"Basic LTO" is also functionally analogous to a "unity build", i.e., smushing together each source file into a single compilation unit. There are some caveats, but it's a valuable technique.

dontlaugh• 3 years ago

Extremely common in the games industry.

matheusmoreira• 3 years ago

Does LTO allow the exact same optimization opportunities as unity builds with all static functions? I remember reading that unity builds still result in more optimized code. SQLite amalgamation comes to mind.

https://www.sqlite.org/amalgamation.html

And because all code is in a single translation unit, compilers can do better inter-procedure and inlining optimization resulting in machine code that is between 5% and 10% faster.

dundarious2• 3 years ago

In all likelihood, LTO will always be a strict subset of what you can get from a unity build, in terms of optimization, because it requires additional work to implement. It may be/become very very close, though.

I prefer to use unity builds for various reasons.

delta_p_delta_x• 3 years ago

On MSVC: `/GL`[1], and `/LTCG`[2]. Former implies latter.

[1] https://learn.microsoft.com/en-gb/cpp/build/reference/gl-who...

[2] https://learn.microsoft.com/en-gb/cpp/build/reference/ltcg-l...

These two options also control profile-guided optimisation.

jryans5• 3 years ago

Thanks, I'll add MSVC in my next round of updates! :)

neerajsi• 3 years ago

Hi Ryan, nice to see you're doing well (I remember you from High School).

MSVC's LTCG (LTO) pipeline has been heavily in use at Microsoft for decades now. PGO and LTCG go together. LTCG is the default way most of our binaries are built.

A lot of work has been done to make MSVC LTCG fast and scalable. In particular, the compiler backend is multithreaded on a per-function basis, and there is also support for incremental LTCG that reuses previously compiled machine code and summary information.

vient• 3 years ago

Small correction: -ffat-lto-objects was meant to be added to Clang 17 but after it was finally done there was not enough time to properly test before release. It is implemented though and works in trunk so should be available in Clang 18.

kobzol• 3 years ago

Rust supports linker plugin LTO (https://doc.rust-lang.org/rustc/linker-plugin-lto.html).

jryans5• 3 years ago

Ah yeah, that one I was aware of, but wasn't sure how interested readers would be... I'll queue it for my next round of updates! :)

DannyBee• 3 years ago

This is not quite right.

LTO was available in llvm forever, and well predates GCC, clang is just a particular frontend.

RMS finally allowed the GCC IR to be saved to disk in part as a response to llvm doing it and becoming popular

(I worked on both GCC and llvm forever)

It also misses the function summary vs non summary modes, which is fairly important.

jryans5• 3 years ago

LTO was available in llvm forever, and well predates GCC, clang is just a particular frontend.

For the initial version of this guide, I chose to focus on features as they are exposed in specific tools, as it's easier to pin down a "first available" date that way. Basic LTO for Clang is listed as first available in Clang 2.6, which is also the first LLVM release to officially include Clang.

It also misses the function summary vs non summary modes, which is fairly important.

Are you talking about the module summaries LLVM uses in its parallel / thin LTO mode, or something else?

zschoche• 3 years ago

It would be great if someone could precisely define what is the goal we would like to optimize. In mathematical terms.

bruce343434• 3 years ago

Program runtime

jeffbee• 3 years ago

Not necessarily. You specify the objective, just as you do with compile-time optimization. You can LTO with binary size objective, -Os or -Oz, or for speed, -O/2/3 whatever.

mgaunard7• 3 years ago

I thought thin was meant to be the opposite of fat, not that it did anything to do with parallelization.

synergy202• 3 years ago

I need add LTO flags to my workflow, so for newest gcc and clang, which flags I should use nowadays in daily coding? what about newest g++ and clang++?

My current understanding is: just add -flto to CFLAGS and CXXFLAGS, it does wonders and there is no downsides(other than longer build time). correct me if I am wrong please

InfamousRece• 3 years ago

You’ll need to also add -flto to your LDFLAGS.

synergy202• 3 years ago

Thanks. confirmed with chatgpt, and, if you're doing debug build, you probably do not want to use -flto, otherwise it's great for release build.

mgaunard7• 3 years ago

I don't think that's required. The linker driver will use LTO automatically if the object files it's given contain LTO IR.

If anything you might want to explicitly do -fno-lto to not use LTO when you have fat objects.

chlorion2• 3 years ago

Enabling LTO can cause things to fail to build or fail to run in some cases.

My understanding is that LTO itself is not breaking anything. In these cases the software that it was running on was broken in some subtle way that didn't show up before.

Linux distros like Gentoo that can try to compile lots of stuff with LTO find a lot of bugs related to this.

Kranar2• 3 years ago

Fail to build yes, but I don't know that it can cause failure to run. LTO can identify existing issues as you point out which will cause a failure to build, but if it does build then it would not introduce any new issues that weren't already there nor would any of those issues prevent an application from running.

shaggie762• 3 years ago

Every few years I try LTO on our game engine (about 1M LOC C++) and either the resulting binary crashes or isn't measurably faster.

Invariably, though, the executable is at least a few MB larger (a bad trade on systems like the Nintendo Switch where memory is scarce) and the incremental build time is intolerable.

I've always wondered why it's never brought the promised free performance; I can only assume our frequent profiling and judicious definition of hot functions inline has gotten us almost everything LTO would bring anyway.

eru4• 3 years ago

LLVM's thin LTO should at least not make your build times (much) longer. Have you tried that?

shaggie762• 3 years ago

Yes, IIRC it took a few minutes to turn around an incremental build (instead of maybe 10 seconds) and 2MB bigger text segment for no measurable performance gains.

mgaunard7• 3 years ago

The crashes sound like added value; LTO has exposed bugs in your code.

Link-Time Optimisation (LTO)

Related Stories