10 ms·
The Dynamic Runtime Inlining project
- fancyfredbot 4y agoOkay so this is more of a POC than a real implementation, but what a great idea!
- titzer 4y agoYes, I expect VMs will be adopting this idea -28 years from now. :)
- sebastianconcpt 4y agoI was thinking this was like JIT but for C?
- fancyfredbot 4y agoIt is exactly like that. The parent comment is being sarcastic, making the point that the JVM did runtime inlining a long time ago.
- stormbrew 4y agoJIT 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.
- chrisseaton 4y agoThere are already several JITs for C.
- fancyfredbot 4y agoTo 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++.
- monocasa 4y agoArguably 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.
- 3836293648 4y agoHaven't they already been doing this for like 20 years? EDIT: Can't tell the difference between ~ and - apparently
- klyrs 4y ago> 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.
- jabbara 4y agoIs this like how some C libraries have differently optimised hot path functions for different processors, selected at runtime? But a more generic solution.
- ncmncm 4y agoThis 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.
- mgraczyk 4y agoYou 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.
- ncmncm 4y agoI 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.
- mgraczyk 4y agoEven 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.
- titzer 4y agoYou 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.
- armchairhacker 4y agoJIT 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.
- k__ 4y agoI read these JIT promises decades ago, yet AOT languages like C and Rust are still the pinnacle of performance. How come?
- vlovich123 4y agoPGO 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-with-profile.html https://blog.chromium.org/2020/08/chrome-just-got-faster-wit...
- pca006132 4y agoI 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.
- dathinab 4y ago
- sour-taste 4y agoWhat does this offer that profile guided optimization doesn't?
- vlovich123 4y agoEase 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.
- cryptonector 4y agoThis is dynamic at run-time.
- moonchild 4y agoIsn't this just dynamo (1999)? - https://www.hpl.hp.com/techreports/1999/HPL-1999-78.pdf https://www.hpl.hp.com/techreports/1999/HPL-1999-78.pdf
- rwmj 4y agoYes, 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.
- moonchild 4y agoTCG 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.
- twoodfin 4y agoThis 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.
- rurban 4y agoThis 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.
- cryptonector 4y agoI wonder if this will make the optimizer/UB issues worse for C.