The Dynamic Runtime Inlining project | Hacker News Reader

The Dynamic Runtime Inlining project

github.com

83 pointsfancyfredbot35 comments

JIT compiling is very powerful. It can enable optimizations like this that cause JIT-compiled programs to run even faster than pure AOT-compiled ones.

There's obviously been a lot of research on JIT compilation for Java and JavaScript (hence why they can run very fast, especially JS, despite being very dynamic languages). But what if we apply JIT techniques to already-AOT programs? We lose performance consistency (although we can keep the lower bound of the base program), but we get even faster performance, and it makes debuggers' and hot-code-reloaders' jobs easier because we already have the ability to compile and recompile code during execution.

I read these JIT promises decades ago, yet AOT languages like C and Rust are still the pinnacle of performance.

How come?

PGO can be thought of in a sense as a form of JIT (just that you have to manually capture a profile and keep it up to date to be relevant vs happening transparently at runtime). Still, it can offer benefits [1]. So clearly something that automatically JITted without the headache of managing PGO profiles could make it MUCH easier to turn globally without needing to really do a lot of work.

[1] https://blog.chromium.org/2020/08/chrome-just-got-faster-wit...

I think part of the reason is due to the programmer: People writing in AOT languages such as C, C++ and Rust usually care more about performance and knows more about low level details that matter for performance. For example, they may try to optimize data layout to avoid cache misses, which JavaScript programmers generally won't (if they can). Also, compiling AOT can allow programmers to look at the optimization done by the compiler and determine if they need to further tweak the code to improve performance.

Complexity/Time Constraints, predicability, compiler-existance and programming language design.

Complexity:

- JIT is only faster if it often enough recognizes the right things to JIT in the right way.

- At the same time the JIT compilers share resources with the running program limiting how complex the analytics and optimizations it can do can become. This is not just a problem wrt. to hurting the main applications performance due to reducing available resources but also e.g. matters for energy usage.

- Worse there is often real time time bound on how long a JIT compiler can take no matter how much resources it uses or responsiveness will suffer to much.

- Similar if no additional tricks are used (which often add painful complexity) the optimizations have to be done every time the program is started again and again, hurting auto scaling or ephemeral programs.

- There is also the problem that workload/data specific optimizations (which gives JIT the additional edge) rely on some data/workloads always having a specific format. If this invariants change they might become slow or might even to fallback to other code (which implies the invariant also needed to be checked). One exception is if you hint to the compiler that certain invariants (e.g. function pointers) won't change (like in the OP article).

Predictability:

- the performance of AOT focused language code is often more predictable making it often easier to optimize

- in JIT languages you rely more on the compiler being able to detect the right patterns, this isn't always easy and even with AOT languages this sometimes isn't easy even through the compiler can do much more work to analyze the context

compiler-existance:

- Many AOT language can take advantage of LLVM/GCC so a lot of work has gone into optimizing them before they even started.

- And while you can use LLVM to JIT it is often not viable as it's a rather large dependency with a lot of different versions which itself is optimized for throughput and not latency and is also tuned for a use-case which is allowed to take a while and consume quite a bit of resources.

Language Design:

- Features AOT languages are often designed with their AOT nature in mind, many JIT/Interpreted languages are not. Sometimes they outright have features which can impede JIT optimizations or at least make them more complicated/harder to find/less fast.

- If you throw enough money at a badly for JIT designed language you probably still get good results, e.g. see JavaScript. But this isn't a story of success, it's a story of dynamic/politics leading to an absurd wast of human resources (dev hours) across many companies burning millions if not trillions over the years to work around language limitations.

So any hypothetical language perfectly taking advantage to JIT to become "the fastest" would probably be much closer to a classical AOT language then e.g. JavaScript (as in less dynamic more strictly structured, maybe GC but maybe not or at least more restricted to reduce GC abuse possibilities, no or very limited runtime reflection, etc.).

To top this of some of the benefits of JIT can be brought to AOT languages. For example you can compile a binary with LLVM in a way so that it collects statistics which then can be used to fine tune optimizations (better decide if a path is cold or which loops to unroll how much etc.). Drawback is setting it up in you deployment can add quite a bit of complexity. Another example are tools JIT some very few predetermined points, like de-visualizing/inlining virtual function calls or for one-time initialized global remove the "is initialized checks".

Which means at the cost of more complex deployments doing some profiling to find some problematic vcalls and similar you can get many (but not all) the optimizations JIT languages have while having most of the benefits of AOT language. Through it only makes sense if your company/product reached a certain non-small size. Or when there is more modern tooling around to make such things easier to setup.

A JIT with dynamic optimization for these traditionally-AOT-compiled languages has little headroom to improve the code, whereas for more dynamic languages, there's a lot of headroom.

Runtime profiling has a cost, and the benefit has to outweigh that cost. Collecting receiver type profiles in order to speculatively inline has a big payoff in, e.g. Java or JavaScript, but probably not C++ or Rust, where programs have less polymorphism because programmers routinely avoid polymorphism in hot parts of the code.

Okay so this is more of a POC than a real implementation, but what a great idea!

Yes, I expect VMs will be adopting this idea -28 years from now. :)

I was thinking this was like JIT but for C?

It is exactly like that. The parent comment is being sarcastic, making the point that the JVM did runtime inlining a long time ago.

JIT goes back a lot farther than the jvm. I think the first recognizably modern implementations were for Self and Smalltalk. The people responsible for those were largely involved in bringing the idea to the jvm afaik.

There are already several JITs for C.

To be fair this kind of an AOT/JIT hybrid is the kind of thing Android might adopt about -6 years from now ;-)

And, to my mind at least, there is something interesting/innovative about seeing these ideas applied to C++.

Arguably goes at least back to HP Dynamo. Binary to binary JIT, but practically has very similar semantics to a C to native code JIT outside of the frontend.

Haven't they already been doing this for like 20 years?

EDIT: Can't tell the difference between ~ and - apparently

> The basic concept is to get the normal compiler front end like clang to emit its LLVM Intermediate Representation (IR) as a bitcode file, then run a custom LLVM pass over this to inject DRTI code at the appropriate places.

DRTI is pronounced "dirty." This sounds impressive as heck but also I'd never be an early adopter.

This seems to miss the primary purpose of inlining, which is to enable further optimizations on the combined call site/inlined code.

Inlining is the ultimate optimization, but only as a foundation for others: Modern CPUs have rendered function calls (even predictable virtual ones) nearly free.

Isn't this just dynamo (1999)? - https://www.hpl.hp.com/techreports/1999/HPL-1999-78.pdf

Yes, the first thing I thought of too. Also I wonder if we could modify qemu TCG to do some sort of dynamic analysis + recompilation for virtual machines.

TCG is not that great, so I hear--might not make the best starting point. But VMs do seem like a promising avenue. One obvious problem is register allocation: if guest has more registers than host, and you can predict branch X is hotter than branch Y, then spill Y's registers to keep X's in (host) registers.

This is almost useless for dynamic runtimes, as they need to inline their own calls in their own calling convention, not calls in the C calling convention in llvm bitcode format.

For the C calling convention -O3 is good enough. With this you need to explicitly mark them, similar to [[always_inline]], just in a separate text file. This hardcodes r14, so it would be only useful for x86_64.

Also inlining just enables further optimizations, previously missed. something like qbe is much more interesting.

Is this like how some C libraries have differently optimised hot path functions for different processors, selected at runtime? But a more generic solution.

This seems sort of pointless -- you could just compile versions of the function for all the types that might be there -- except maybe the code is to be specialized on a type that came from a shared library that was not visible to the linker at the time the program was built.

You can't do that in general. For example you can't statically devirtualize a call to a virtual function on a non-final class because it could be inherited from in a different dynamically loaded library. This pattern is pretty common with C++ SDKs.

I guess virtual functions are common in some places.

This thing seems to generate code to check if the type matches what was inlined, and do the ordinary virtual call if it doesn't match. Virtual-call branches are well predicted nowadays, but the opportunity to integrate the code before and after the call might be worth something, probably by deleting code that computes something thrown away in that case.

Even if virtual call branches are well predicted, they still have high overhead.

Yeah GCC and clang will do what you described in some cases, they will insert a check and try to make a non-virtual call when possible. But also as you mentioned, they real advantage is from the downstream optimizations that unlocks, which they cannot do.

You can do a pretty good job if you have the whole program. That's the point of class hierarch analysis (CHA) or rapid type analysis (RTA), which unfortunately doesn't seem to get used all that much these days. Virgil is an unapologetic whole-program compiler and goes even further with specializing to an initialized heap.

JVMs typically use dynamic class hierarchy analysis that doesn't require runtime profiling, but can require deoptimization on class loading.

I'm specifically talking about cases where you don't have the whole program, like SDKs

Even just restricting the scope to a jar works surprisingly well. It's even better if the language has a module system that can further reduce the amount of exposed APIs.

You can, but you have to guard your inlined path with a type check and fallback to the non virtual path (JITs do similar things, except that the JIT of course can dynamically decide which function to inline, while at best AOT can use PGO).

Yes GCC and Clang already do this in many cases, but it's not quite the same as what the posted compiler can do.

I wonder if this will make the optimizer/UB issues worse for C.

What does this offer that profile guided optimization doesn't?

Ease of use of not having to figure out what a representative workload looks like / collecting samples from production. The downside is that you have to spend CPU cycles JITting in production.

I could see this getting more play than PGO if it becomes really easy to turn on.

This is dynamic at run-time.

Reply on news.ycombinator.com