Meta Sees ~5% Performance Gains to Optimizing the Linux Kernel with Bolt | Hacker News Reader

Meta Sees ~5% Performance Gains to Optimizing the Linux Kernel with Bolt

phoronix.com

50 pointsnewman31425 comments

Interestingly Google went ahead and made their own version of Bolt after it was already open source.

It's called Propeller and it had some purported advantages afaik.

Anyone know if such large scale experiments have been conducted with this for the sake for comparison?

More info about Google's Propeller, from https://lists.llvm.org/pipermail/llvm-dev/2019-September/135...:

    While BOLT does an excellent job of squeezing extra performance from highly optimized binaries with optimizations such as code layout, it has these major

issues:

     * It does not take advantage of distributed build systems.
     * It has scalability issues and to rewrite a binary with a ~300M text segment size:
     * Memory foot-print is 70G.
     * It takes more than 10 minutes to rewrite the binary.

    Similar to Full LTO, BOLT’s design is monolithic as it disassembles the original binary, optimizes and rewrites the final binary in one process.  This limits the scalability of BOLT and the memory and time overhead shoots up quickly for large binaries.

Disclaimer: I'm an active developer of BOLT.

It takes BOLT less than 10 second to optimize the Linux kernel once the profile is collected. There's no need for a distributed build system to take advantage of that. Overall, we have improved both processing time and memory consumption over the years.

Isnt what BOLT does done _once_ before distribution?

Here is an article on the Meta engineering blog about BOLT

https://engineering.fb.com/2018/06/19/data-infrastructure/ac...

The gains are dependent on how much time the workload spends in the kernel. The Propeller team showed 2% performance improvement over PGO+LTO in this LLVM discussion post: https://discourse.llvm.org/t/optimizing-the-linux-kernel-wit...

More details about Propeller are available in a recently published paper: https://research.google/pubs/propeller-a-profile-guided-reli...

Is this specific to big programs running on data centers or could it be applied to programs people run locally on their computers or phones?

I'd love to know if the kernel improvements could be improved in this way too for PC / Android users.

I seem to remember that glandium had done something like this on the Firefox binary to optimize the startup, with impressive speedup. Can't find the details, though.

If some of the optimization gain is from bad alignment of potentially fused operations that can't because they straddle a 64 byte cache boundary, it feels like this is something the compiler should be aware of and mitigating.

Aren't profile guided optimizers capable of doing similar optimizations?

The gains mentioned are on top of compiler's PGO+LTO.

No. The key observation of BOLT is that by collecting profiling on an optimized binary and then mapping the profiling onto a compiler's decompilation of that optimized binary, you get better profiling fidelity.

My intuition for why BOLT works is that:

- If you try to profile an unoptimized (or even insufficiently optimized) binary, you don't get accurate profiling because the timings are different.

- If you try to profile an optimized binary and then rerun the compiler from source using that profiling data, then you'll have a bad time mapping the profiler's observations back to what the source looked like. This is because the compiler pipeline will have done many transforms - totally changing control flow layout in some cases - that make some of the profiling meaningless when you try to inject it before those optimizations happened.

But BOLT injects the profiling data into the code exactly as it was at time of profiling, i.e. the binary itself.

It's totally insane, wacky, and super fucking cool - these folks should be hella proud of themselves.

I know very little about compilers or bolt.

But what you just described sounds awesome!(and crazy)

In theory you can get a pretty good idea of where instructions came from in the source code though the optimizer does, shall we say, obfuscate/spread that a little bit (which is why debugging through optimized code or looking at core dumps from optimized code can be tricky- but you can still mostly do it, there's just some lack of precision in the mapping back).

Maybe the bigger problem is at what point do the profiles feed back. Since a compiler may generate many object files which are then linked to form the final binary you'd sort of maybe want to do this in the linker vs. earlier on.

I guess specifically with the kernel there's an extra layer of complexity. It looks like they use `perf` to record the profile which is cool. And then they apply the results to the binary which is also cool.

> In theory you can get a pretty good idea of where instructions came from in the source code though the optimizer does, shall we say, obfuscate/spread that a little bit (which is why debugging through optimized code or looking at core dumps from optimized code can be tricky- but you can still mostly do it, there's just some lack of precision in the mapping back).

I think the whole point of BOLT is that in practice, you can't get a good idea of where instructions came from.

And it's not even about instructions as much as control flow. LLVM, GCC, and other good compilers (like the ones I wrote for JSC) can and absolutely will fuck up the control flow graph for fun and profit. So if the point of the FDO is to create better code layout, then feeding the profiling samples into before when the compiler did its fuckery will put you up shit creek without a paddle: the basic blocks and branches that the profiler will be telling you about don't exist, and won't, until the compiler does its thing.

You could try to run the compiler forward until it recreates the control flow structure that the profiler is talking about, but that seems hella sketchy since at that point you're leaning on the compiler's determinism in a way that would make me (and probably others) uncomfortable. It would rule out running BOLT on binaries optimized with PGO and it would create super nasty requirements for build system maintainers.

If it increases performance by 5% then 5% of execution time was spent missing branches and instruction cache misses... Which sounds utterly implausible. Conventional wisdom has it that instruction caching is not a problem because whatever the size of the binary it is dwarfed by the size of the data. And hot loops are generally no more than a few KBs at most anyway. I'm skeptical.

>5% of execution time was spent missing branches and instruction cache misses... Which sounds utterly implausible.

You could be right, but this reminds of the "efficient markets" joke. Wherein two economists refuse to believe the $100 the see on the ground is real because "someone would have picked it up" :-)

The performance loss due to cache misses in data-center applications far exceeds 5%. Combined data and instruction cache misses are contributing to more than half of stalled cycles.

The following publication by Google from 2015 goes into details: https://static.googleusercontent.com/media/research.google.c...

"Our results demonstrate a significant and growing problem with instruction-cache bottlenecks. Front-end core stalls account for 15-30% of all pipeline slots, with many workloads showing 5-10% of cycles completely starved on instructions (Section 6)."

You're conflating data misses with instruction misses. Besides, the article is about hundred-megabytes-binaries (forgot to strip debug data?), which the Linux kernel isn't.

The quote above talks exclusively of instruction cache misses. In case you are really interested, the two kinds are related as L2 and L3 caches are shared my instructions and data.

In terms of the execution profile, the kernel is very close to a typical WSC application. I.e. very flat without hotspots. The size of L1 I$ is 32KB, hence your application doesn't have to have 100s of megabytes of code to benefit from layout optimizations.

5% doesn't sound like what you would get addressing the lowest hanging fruit.. Which makes sense because the Linux kernel's primary bloat is mostly in the form of drivers that never load on any specific system. So sure, a pretty good result for not a very relevant optimization but I'd be disappointed if I built this tool specifically for the kernel instead of applied it because I had it..

You can measure it yourself, this is not a philosophical thing you have to be skeptical about.

It's not that 5% of the time was spent in icache misses, it’s more about cascading benefits of hitting the cache or predicting a branch correctly. You get more instruction level parallelism, less stalls, and in general more straightline execution without hitting memory.

This looks like iffy blogspam of https://github.com/llvm/llvm-project/blob/main/bolt/docs/Opt...

The claim in it is 'up to 5% improvement' so the title seems overstated as well.

Iffy blogspam? Phoronix? To me it reads like a well written summary.

Well, that's a matter of taste but plucking out something out of an article, sticking it in the headline and getting it wrong, is not a good summary and, to my eyes, blogspammy behaviour. But it the taste part doesn't matter much because HN's guidelines ask people to submit original sources so the original article would have been a better fit.

Reply on news.ycombinator.com