4 ms·
In their comparisons they explain that the existing Hot Cold Split creates new functions for the cold parts which brings overheads due to calling conventions an
by account42 6y ago
In their comparisons they explain that the existing Hot Cold Split creates new functions for the cold parts which brings overheads due to calling conventions and exception handling. Their new method avoids that by using simple jumps.
I wish compilers were able to optimize functions boundaries for visible but not inlined better so they could optimize those function call overheads away automatically. There is no reason for a compiler to limit itself to the system ABI for completely internal functions.
Besides leaving values in the registers they are already in instead of moving them to where the ABI says they should be, this could enable passing C++ objects such as std::unique_ptr in registers where the current ABI forbids this. Or to eliminate nop destructors for objects that are always moved from in the called functions.
In general, I think compilers should see function boundaries in the source code as a mere hint when it comes to code generation just like they already do with the register keyword.
Is there any existing compiler work to optimize function calls where the implementation and all uses are visible in the translation unit?
- saagarjha 6y agoFunctions by default have external linkage, and as such can be called by anyone. So of course this could only apply to functions that are static or internal in some way. Once you have that down, you have to deal with the fact that the things you would want to optimize may differ at each call site (one may like to keep rdx free, one may be able to give up rdi) so I am unsure it would be worth the effort to not follow the ABI.
- account42 6y ago> So of course this could only apply to functions that are static or internal in some way. Or with LTO / -fwhole-program: functions that have hidden visibility. Which is all of them for Windows executables and the default for DLLs (and -fvisibility=hidden is a sane default for other systems too). > Once you have that down, you have to deal with the fact that the things you would want to optimize may differ at each call site (one may like to keep rdx free, one may be able to give up rdi) so I am unsure it would be worth the effort to not follow the ABI. Sure, that makes things harder. But in many cases will only be one call site. In others you can still figure out which optimizations you can apply to all of them - for example passing std::unique_ptr and similar objects by register should always be doable as long as you control all call sites. Further, the compiler has the option to clone functions in order to apply optimizations specific to a group of call sites if it decides that an optimization is worth the increased code size. And some optimizations will be purely on the caller side - for example not spilling caller-saved registers if you know they won't be clobbered by the callee.
- webreac 6y agoIMHO, it will be a nightmare for debuggers.
- mnem 6y agoGenerally trying to debug optimised code is a nightmare anyway. Most debugging is performed on non-optimised builds, which wouldn’t be affected by the proposed optimisation.
- thu2111 6y agoThere's actually a compiler that does all these things and allows debugging of optimised code whilst seeing the unoptimised form - Sulong. Sulong is an LLVM JIT-compiling engine that runs on GraalVM. So it uses the same infrastructure of the JVM, but without JVM bytecode getting into the picture. Instead the JVM runs LLVM bitcode directly. But it does so in the standard way which gives many benefits: • Splitting of hot/cold paths, as in this work. • Cross-function optimisation and inlining regardless of visibility, as requested above. • Ability to debug an optimised program, because the JVM can 'deoptimize' the parts being inspected or debugged. • Run the Linux version of the bitcode cross-platform. • In "Managed Sulong" (which is an enhanced payware version), all allocations are garbage collected and bounds checked. Yes even for C/C++ programs, just needing a recompile. It's just about possible to do this within the rules of well defined C/C++, as long as the program doesn't try to do non-portable or non-defined things like pass stack pointers between threads. Managed Sulong can also sandbox LLVM code modules, and redirect IO back into the JVM for mapping via the pluggable socket/filesystem layers. • Cross-language interop, including recent experimental support for e.g. casting Java or Ruby or Python objects to C++ objects and calling methods on them. • All the same compiler optimisations as LLVM does still apply. It's a pretty amazing and under-appreciated project. On the other hand the code being run inherits the limits of the JVM, e.g. you shouldn't try and fork the process (of course, lots of runtimes don't like being forked and on Windows you can't do it at all).
- brian_herman 6y agoYeah, sulong looks pretty cool! https://llvm.org/devmtg/2019-04/slides/TechTalk-Schatz-Sulong_an_experience_report.pdf https://llvm.org/devmtg/2019-04/slides/TechTalk-Schatz-Sulon...
- chriswarbo 6y ago> There is no reason for a compiler to limit itself to the system ABI for completely internal functions. As far as I understand it, this limitation is also the only thing preventing tail-call elimination in C/C++. Tail-recursive functions are essentially the same as 'while' loops (execute some instructions then conditionally go back to the start); they just have different scope and calling conventions. In particular, 'while' loops are always inline and can't be referenced from other functions, but tail-recursive functions can. Hence compilers can apply more aggressive optimisations to 'while' loops, e.g. re-using the same stack frame and iterating with a conditional jump. However, as you say, functions-as-subroutines don't necessarily need to coincide with functions-as-interface. Tail-recursive functions which are only used internally can also be optimised to re-use the same stack frame and iterate with a conditional jump. If such functions are also exposed in the interface, it's pretty trivial to expose a dummy entry point which invokes the optimised version (if we want to); although cross-unit tail calls wouldn't be eliminated in that case. Of course, this is more useful than just writing 'while' loops in a different style (although I personally prefer recursion https://news.ycombinator.com/item?id=11150346 https://news.ycombinator.com/item?id=11150346 ), since tail calls don't have to be recursive: we can split our code up into modular, composable, self-contained functions without having to worry about stack usage (or code bloat caused by inlining into multiple locations).
- deleted 6y ago[deleted]
- tom_mellior 6y ago> As far as I understand it, this limitation is also the only thing preventing tail-call elimination in C/C++. Nothing "prevents" tail-call elimination in C. Compilers do it all the time. > Tail-recursive functions which are only used internally can also be optimised to re-use the same stack frame and iterate with a conditional jump. If such functions are also exposed in the interface, it's pretty trivial to expose a dummy entry point which invokes the optimised version (if we want to) Can you illustrate with a concrete example what you mean? If the function doesn't need a stack frame, there will be no stack frame either way. If the function needs a stack frame, that stack frame must be allocated in the function's start block either way, and tail recursive calls will of course not jump to that start block but to its successor. I don't see how being "exposed in the interface" (in C speak, static vs. non-static) would make a difference here.
- Apanatshka 6y agoI've seen a poster presentation at the student research competition of a PL conference where the student created a tool to do this after the fact on binaries. It looked quite promising, but I think preliminary results were single digit percentage speedup for most benchmarks. I'll have to see if I can find it again.
- kevincox 6y agoSingle digits is a huge improvement. This is single digits across billions of programs with no change on their part. In the email Google claimed single digit improvements and I'm sure they are thrilled. 1% CPU savings across Google is many, many millions of dollars a year. If you contribute a 1% CPU savings change to GCC or LLVM you would have a very hard time being carbon-positive over your lifespan.