What Challenges and Trade-Offs Do Optimising Compilers Face?
tratt.net
tratt.net
WebKit used LLVM as its optimizing JIT compiler for a couple years, and it was fine. We only switched away from LLVM when we wrote a compiler that generated code that was as good as LLVM (for our narrow use case) but in less compile time; we would probably switch back to LLVM (or any other heavy AOT-style compiler) if it gave us more throughput than our current compiler. In general, we're happy to pay compile time to get peak throughput.
The reason why we have this attitude is that we have more than one JIT. WebKit has three JIT tiers for JS and two for WebAssembly. The top tier does crazy expensive optimizations (the most expensive of which is a must-points-to analysis for removing object allocations; in second place is the Yorktown-style regalloc) and has long compile times, but it's OK because by the time we run it, we've already done a pretty good job of optimizing the code with the JIT tier just below the top one. The second-to-top JIT tier in WebKit, called the DFG JIT, runs very quickly.
Overall this is a great post! I just think that there is even more potential for perf with JITs than what the post implies.
Specially if the JIT can reuse PGO from previous execution runs like MGO on .NET 4.5+ or Android 7.
https://blogs.msdn.microsoft.com/dotnet/2012/03/20/improving...
> In general, we're happy to pay compile time to get peak throughput.
Shouldn't a program which runs a UI (which WebKit basically is) optimize for lowest latency instead?
Do you want to achieve low latency with low latency, or do you want low latency and it's so important that you don't mind high latency to get it :)
What I mean is yes people want lowest latency. But you can either compile quickly, to get to a reasonably low latency when using the app and to get to that point itself with low latency, or you can compile with optimisations, and get lower latency when the compilation is done but have to wait with high latency to get to that point.
Both approaches are 'optimising for latency' so you'd need to be more specific.
The practical compromise is tiers of compilation, each taking higher latency to apply but producing lower latency when they're done.
Note that this is only the third (top) tier JIT (or fourth if you include the interpreter). By that point, you're really optimising for throughput and not compile time.
Compiler directives are given as numerical levels of speed, safety, compilation speed, code size, and debuggability. There are other more specialized directives beyond those.
If you're building a web app and the backend has 2 or 3 really hot code paths, you can do something like:
(defun hot-path (request)
(declare (optimize (speed 3) (safety 0) (debug 0)))
...)
I'll usually abstract away the DECLARE with more semantically meaningful terms: OPTIMIZE-DANGEROUSLY-FAST, OPTIMIZE-FOR-SCRUTINY, etc.
In general, in Lisp, I would say it's even considered bad hygiene to flip the global optimization switch; as djb and the article say, most of your large programs don't need it. You also often sacrifice debuggability in the entirety of your program if you ask the compiler to do what it can to make it fast.
Loop unrolling directives went through that process in just a few years, from giving a nice speedup, to compilers being able to mostly match the directive, to the directive causing slowdowns, to compilers ignoring that directive.
The article mentioned superoptimization. Google's Souper uses an SMT solver (like Z3) to make LLVM peephole optimizations.
https://github.com/google/souper
Alternatively, Alive allows users to specify rewrite rules for peephole optimizations. The rules are verified with Z3 and then compiled into an LLVM pass. If the rewrite can't be verified, then Alive won't allow it.
https://github.com/nunoplopes/alive
And then there's STOKE, which uses stochastic search to investigate possible program transformations of x86 to find non-obvious code sequences. STOKE also verifies the resulting transformation with Z3.
I know this isn't the position being put forward or defended by the author but I feel it's worth addressing nonetheless.
The flaw in this logic is that whether a problem is worth solving or not depends not only on the benefits of doing so, but also the costs. In this case, a compiler which optimises for size can, for almost zero cost, provide a modest benefit. This is absolutely worth doing.
I was already looking to doing something similar after seeing VeLLVM project and KLEE. Idea was to make an optimizing compiler generate each intermediate step in C code so KLEE can equivalence check it. Once low-level enough, do that in KLEE and/or VeLLVM. Naturally, this is so time-consuming that one would do it for code that doesn't change much or is just really critical. The component handling the commits in your link would be a candidate.
Rust was designed to be optimized; this means unoptimized Rust code can easily be 2x-100x slower than optimized code. Given that speed is one of Rust's goals, yeah, you could implement a Rust compiler with no optimization, and that's fine. But it won't be usable to a significant chunk of users who rely on the speed.
Another way this can affect language design: Rust supports enums, which are a sum type. The memory layout of the enum is undefined at the language level. This is specifically so that compilers can do optimizations to make layout more compact than a naive implementation. In some sense, this is leaking optimization concerns out into language design.
Designing the language around optimizability is a good thing, e.g. C++'s "as if" rule (in [intro.execution] in standards after C++11 (or near there)). Some of these options, which may or may not be used for optimization, can also be very useful for code quality/correctness: e.g. Language enforced purity (of functions) (in D) can be very useful for optimization (It's inferred in most compilers, but it can at least save a trip) and being able to trust (even a D function pointer) to be pure.
That the compiler isn't fundamentally part of the language or integrated into the language itself?
I don't think that has to hold for all possible language designs...
I could give it a few hints about what order might work, and it could show me what the intermediate representations are so that I can keep them in mind while writing code. There are patterns in C/C++ that trip up compilers, like unintentional aliasing or out params, and I could try to avoid them to help the optimizer. On the other hand, if the optimizer doesn't are, I will use them for my own convenience.
I suppose Clang has a pretty well-defined interface between passes, in the LLVM IR, so you can do this to some degree now. But it is a little obscure and probably version-dependent.
I thought that all it really did, at least on gcc, was record which branches were taken and optimise the code to reflect the common path. Do compilers really make use of the profile timings to decide to spend more time optimising 'hot' parts of the code with more involved/expensive transformations?
Clang does not AFAIK.
MSVC in PGO/LTO mode will do all sorts of exciting things. For example, in hot code it will detect that a virtual function call is always or nearly always happening with the same vtable pointer and emit a guard on the vtable pointer followed by an inlining of that one particular implementation (with a fallback to a normal virtual call if the guard fails). I'm pretty sure it doesn't do this for all virtual function calls in the program. Even if it only does it for ones where it has "enough data", that would bias towards the hot ones.
These days, with CPU vendors putting in massive effort for <10% performance improvements, getting a 2x speedups in applications that compile to hundreds of MB's, is more "free" performance than you are likely to gain over the next decade from the hardware vendors.
Lastly, the kinds of code paths most suited to these gains are also the hardest to benchmark. Which is why I fall into the camp that believes picking a fairly performant language is more valuable than a small bump in developer productivity for a little syntactic sugar for anything more complex than throw away code.
Well syscall entry/exit would be a contender, but those are already in hand-written assembly anyway, so that doesn't count.
Then I'd go for the read()/write() syscalls; I bet (not verified) that they're called really often in comparison to the other ones, with all the file/socket/IPC I/O that's going on.
I'm in the same camp about language choice though; there's lots of place for slower and easier languages, like Python in the role of gluing together high-performance C code, but there are still also lots of scenarios where an across-the-board performant language seems a good fit. Compilers spring to mind, but they are even an extreme example.
If an optimizing compiler can reduce code size by 50%, that's extremely useful, and as opposed to throughput optimization for which perhaps only a few small methods matter, for code size the whole program matters, so humans can't compete with compilers there.
And throughput is actually easier (see: Latency Lags Bandwidth). So we're often/usually getting help with the less important problem that's easier to solve, while at the same time making the more important and harder problems more difficult.
YMMV.
Somehow this blog and the debate with djb reminds me of this point. What kind of person is are the compiler optimizations intended to benefit?
I.e. you compile your program with profiling, then run e.g. a test suite, and compile your release binary with input from that profiling so the compiler knows what to optimize.
Has any C compiler closed the loop on that by shipping the full compiler with the program to do runtime optimization? With on-the-fly symbol replacement you'd effectively have a C JIT compiler.
- The truffleruby "cext" project demonstrated something like this. They interpret and then JIT C on the JVM, and do cross-language inlining and other optimizations.
http://chrisseaton.com/rubytruffle/cext/
The same group is working on compiling LLVM IR on the JVM. Presumably the JVM's tiered runtime optimizations would apply to both of these.
https://github.com/graalvm/sulong
- There are also interactive C(++) "JITs" from CERN and the Julia project. However, as far as I know, they are both method JITs and don't do any trace-based re-JIT/OSR.
https://root.cern.ch/cling and https://github.com/Keno/Cxx.jl
Past that, LLVM is already like this, it's just a matter of shipping bitcode, and outputting the currently optimized bitcode at shutdown.
It is actually done in practice, but admittedly, only by those who care tremendously about performance.
(IE you don't find it done in common linux distros).
Particularly in a datacenter world, where you have hypervisors and things under the covers anyway, it's not a huge deal to have a JIT running.
The harder part is actually, if you are a cloud provider, getting anyone to bring bitcode with them :)
Even if you promise them X% performance gain to start, where X is usually 10-30%, they don't usually care enough to modify their workflow.
http://archive.arstechnica.com/reviews/1q00/dynamo/dynamo-1....
I have used processors that have saturating arithmetic and I even used that feature, but even there compiler defaulted to the more common rollover behavior.
I once suggested, back when there were machines that weren't byte-oriented or twos complement, that wraparound arithmetic should be requested with
unsigned int x;
x = (x + 1) % 0xffff;
I assumed it was free. If it's not, then it isn't even fully open as a language. Can anyone refute it with a link to free standard?
(It's been a while, but I found these rationale documents fascinating reading.)
C11 is here. [0]
However, the working draft immediately before is open. In this case, C1X is here [1].
[0] https://www.iso.org/standard/57853.html
[1] http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf
Which has created a history of languages that usually follow the standard quite strictly.
(Though, I do personally despise the non-free aspect, I can sort of understand it, considering history and the effort to standardise).
I am starting to think that the complaints about optimizing compilers are due to C family undefined behavior leading to C programmers having a love hate relationship with their compiler writers. In contrast Java programmers trust their JIT compilers to not screw up. But then UB is something that can cause issues even if there was no optimizing compiler at all.
So to conclude I am extremely grateful that there are optimizing compiler writers out there.
Now what is that 15% worth? Take the new AMD Epyc to go from 2Ghz to 2.2Ghz is worth 800USD (3200->4000). That means running JVM -server gives a value at that level of about 1/3 of the server CPU cost over running the same JVM -client. Of course that is at the top level and would be less in the middle.
This reads as if the author had suddenly remembered he's British halfway through the sentence. Quite jarring.
(Not to mention that 'practise' is a verb.)