5 ms·

Link-Time Optimisation (LTO)

118 points by signa11 3y ago

pjmlp 3y 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.
- foobazgt 3y 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 3y ago
    I think it's just usually rolled up into optimizations with other names, like "speculative inlining".
- iruoy 3y ago
  On tuesday .NET 8 will be released which has this aswell. https://devblogs.microsoft.com/dotnet/performance-improvements-in-net-8/#tiering-and-dynamic-pgo https://devblogs.microsoft.com/dotnet/performance-improvemen...
- jryans 3y 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.
  - pjmlp 3y 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 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 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-java-cloud-native-applications/ https://developer.ibm.com/articles/jitserver-optimize-your-j... https://www.azul.com/products/intelligence-cloud/cloud-native-compiler/ https://www.azul.com/products/intelligence-cloud/cloud-nativ...
    - jryans 3y ago
      Thanks, this looks great. I'll read through these and add this info in my next update. :)
  - twic 3y 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!
    - foobazgt 3y ago
      This is incorrect. The JVM has an explicitly separate link phase [0]. The difference with AOT compilers is that linking is deferred until runtime. Rather than saying there's no link phase, you should think of it like as if your favorite AOT compiled language could support LTO on dlopen. 0) https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-5.html https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-5.ht...
vkoskiv 3y 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.
- menaerus 3y 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
  - mgaunard 3y ago
    Why not just use mold?
    - eru 3y ago
      Mold is only available on Linux.
      - mgaunard 3y ago
        If you insist on using inferior OSes like Mac OS X, there is sold.
        eru 3y ago
        Yes. But lots of people also have to use eg Windows.
        mgaunard 3y ago
        Windows has WSL.
  - 3y ago
deleted 3y ago
[deleted]
dundarious 3y 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 3y ago
  Extremely common in the games industry.
- matheusmoreira 3y 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 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.
  - dundarious 3y 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 3y ago
On MSVC: `/GL`[1], and `/LTCG`[2]. Former implies latter. [1]: https://learn.microsoft.com/en-gb/cpp/build/reference/gl-whole-program-optimization?view=msvc-170 https://learn.microsoft.com/en-gb/cpp/build/reference/gl-who... [2]: https://learn.microsoft.com/en-gb/cpp/build/reference/ltcg-link-time-code-generation?view=msvc-170 https://learn.microsoft.com/en-gb/cpp/build/reference/ltcg-l... These two options also control profile-guided optimisation.
- jryans 3y ago
  Thanks, I'll add MSVC in my next round of updates! :)
  - neerajsi 3y 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 3y 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 3y ago
Rust supports linker plugin LTO (https://doc.rust-lang.org/rustc/linker-plugin-lto.html https://doc.rust-lang.org/rustc/linker-plugin-lto.html).
- jryans 3y 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 3y 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.
- jryans 3y 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 3y ago
It would be great if someone could precisely define what is the goal we would like to optimize. In mathematical terms.
- bruce343434 3y ago
  Program runtime
  - jeffbee 3y 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.
mgaunard 3y ago
I thought thin was meant to be the opposite of fat, not that it did anything to do with parallelization.
synergy20 3y 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 3y ago
  You’ll need to also add -flto to your LDFLAGS.
  - synergy20 3y 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.
    - mgaunard 3y ago
      LTO is required to detect ODR errors and to do a bunch of other checks. It does more than optimize.
  - mgaunard 3y 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.
- chlorion 3y 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.
  - 3y ago
shaggie76 3y 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.
- mgaunard 3y ago
  The crashes sound like added value; LTO has exposed bugs in your code.
- eru 3y ago
  LLVM's thin LTO should at least not make your build times (much) longer. Have you tried that?
  - shaggie76 3y 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.
    - eru 3y ago
      Interesting, thanks! For our (Rust) project, thin LTO doesn't cost much extra in compile time and gives a few percent speedup. But it's not a terribly optimized code base, and we don't have any manual inline annotations etc.

118 points by signa11 3y 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.

foobazgt 3y 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 3y ago
  I think it's just usually rolled up into optimizations with other names, like "speculative inlining".
iruoy 3y ago
On tuesday .NET 8 will be released which has this aswell. https://devblogs.microsoft.com/dotnet/performance-improvements-in-net-8/#tiering-and-dynamic-pgo https://devblogs.microsoft.com/dotnet/performance-improvemen...
jryans 3y 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.
- pjmlp 3y 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 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 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-java-cloud-native-applications/ https://developer.ibm.com/articles/jitserver-optimize-your-j... https://www.azul.com/products/intelligence-cloud/cloud-native-compiler/ https://www.azul.com/products/intelligence-cloud/cloud-nativ...
  - jryans 3y ago
    Thanks, this looks great. I'll read through these and add this info in my next update. :)
- twic 3y 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!
  - foobazgt 3y ago
    This is incorrect. The JVM has an explicitly separate link phase [0]. The difference with AOT compilers is that linking is deferred until runtime. Rather than saying there's no link phase, you should think of it like as if your favorite AOT compiled language could support LTO on dlopen. 0) https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-5.html https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-5.ht...

vkoskiv 3y 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.

menaerus 3y 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
- mgaunard 3y ago
  Why not just use mold?
  - eru 3y ago
    Mold is only available on Linux.
    - mgaunard 3y ago
      If you insist on using inferior OSes like Mac OS X, there is sold.
      - eru 3y ago
        Yes. But lots of people also have to use eg Windows.
        mgaunard 3y ago
        Windows has WSL.
- 3y ago

deleted 3y ago

[deleted]

dundarious 3y 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 3y ago
Extremely common in the games industry.
matheusmoreira 3y 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 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.
- dundarious 3y 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 3y ago

On MSVC: `/GL`[1], and `/LTCG`[2]. Former implies latter. [1]: https://learn.microsoft.com/en-gb/cpp/build/reference/gl-whole-program-optimization?view=msvc-170 https://learn.microsoft.com/en-gb/cpp/build/reference/gl-who... [2]: https://learn.microsoft.com/en-gb/cpp/build/reference/ltcg-link-time-code-generation?view=msvc-170 https://learn.microsoft.com/en-gb/cpp/build/reference/ltcg-l... These two options also control profile-guided optimisation.

jryans 3y ago
Thanks, I'll add MSVC in my next round of updates! :)
- neerajsi 3y 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 3y 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 3y ago

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

jryans 3y 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 3y 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.

jryans 3y 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 3y ago

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

bruce343434 3y ago
Program runtime
- jeffbee 3y 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.

mgaunard 3y ago

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

synergy20 3y 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 3y ago
You’ll need to also add -flto to your LDFLAGS.
- synergy20 3y 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.
  - mgaunard 3y ago
    LTO is required to detect ODR errors and to do a bunch of other checks. It does more than optimize.
- mgaunard 3y 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.
chlorion 3y 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.
- 3y ago

shaggie76 3y 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.

mgaunard 3y ago
The crashes sound like added value; LTO has exposed bugs in your code.
eru 3y ago
LLVM's thin LTO should at least not make your build times (much) longer. Have you tried that?
- shaggie76 3y 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.
  - eru 3y ago
    Interesting, thanks! For our (Rust) project, thin LTO doesn't cost much extra in compile time and gives a few percent speedup. But it's not a terribly optimized code base, and we don't have any manual inline annotations etc.