Future Directions for Optimizing Compilers
arxiv.org
arxiv.org
While it's true that many sites with high volume are written in high level languages, it's still true that these will require more CPU and memory than something which is highly optimized written in a lower level language. The trade-off is that it takes less developer time to write code in the high level language and the savings there are enough to invest in more computing power.
However, if you can optimize code for high level languages even further, you're still reducing the hardware requirements and ultimately saving costs. If you can build a stable Ruby VM that runs with 10% fewer resources and is compatible with existing applications, I think you'll find people willing to throw money your way.
Not if your application is being used by many users; optimising exclusively for development time is only for rarely-used/one-off things or if you don't value your user's time --- some of whom may be themselves developers. The more users you have, the more it matters.
We've somehow gotten ourselves into a situation where relatively few developers are making countless more users waste time and hardware resources for their own selfish benefit, and I think that's a very bad thing.
Take Java for example.
When it came into scene we had Oberon and its variants, Ada, Modula-3 and Eiffel.
All supported JIT/AOT compilation, value types, and with exception of Oberon, generics.
Most of the last changes at the JVM level, and the upcoming ones on Java's roadmap are basically catching up with what was already possible in the mid-90's.
So how much money could Sun, Oracle and IBM have saved if those features were there from the beginning?
We will never know, but we will know how much the bill is going to be, given that it is 10+ year process currently.
All because the current hardware changes make it impossible for Java to continue to ignore those features, if it is to stay relevant against other languages.
Same applies to other languages in different ways.
Part of the answer is that Java still advance the state of the art for most people: It got safety and garbage collection accepted by the mainstream.
Oberon etc were not in reach for the average Joe, the tooling was too expensive and the cheap, resource constrained PCs couldn't run it. The language required sophistication from the programmers. Nobody was available to answer questions, the ecosystem wasn't there.
Java, o.t.o.h. had something for everybody. It was safer than C, important if you wanted a stable web server. It was faster than perl or shell scripting, so you also had a cheap web server. The browser got nicer graphics from applets. Enterprise architecture got a way forward from CORBA to JEE without having to admit something was wrong. Hardware vendors got a way to stay relevant in the face of Windows. Tooling vendors and consulting companies got a reason to sell. Managers got cogweel replaceable programmers. Schools got a reasonable and vendor-neutral language. Even if none of promises was completely fulfilled, it was close enough long enough.
So basically the language design resources for Oberon were in the end more wasted than those on Java. 'Worse is better' once again.
I'm sorry, but that's just nonsense. You can argue lack of documentation and user community, but Oberon is about as resource economic as it gets, and was originally designed for mid-80s hardware.
* It wasnt very visible in the ICT media. Sun did a full steam ahead Java Campaign
* Open source at the time was not seen as trustworthy. I did run Linux at the time. SO did you, probably. Corporations would not touch it with a 10 feet pole. I presume oberon was seen in the same light.
If Java was sold for the same price as lets say Delphi, most devs and university students would never have cared.
Same goes for the hardware resource. Changing to a bigger server cost less than than my time. That way again my time can save more time on useful stuff.
There's billions of hours wasted in business and government in long and meaningless tasks. Optimize that first please before micro optimizing your software.
For example you could get your product or services up and running in Ruby Rails with least amount of time, but I doubt it will ever be as efficient as Stack Exchange in resources. [1] and likely will cost a lot more reaching that scale.
Instruction-level (peephole) optimizations are omnipresent. You're not going to beat a compiler in register allocation (at least, not by enough to actually be worth the time writing in assembly), and optimizing for microarchitecture is generally within reach of the compiler, when the compiler is made aware of these details. Superoptimization means that automatic tools can write better patterns than you can for loop-free code, and maybe even small loops (although most compilers don't incorporate superoptimization for compile-time reasons).
The next level of optimization is loop nest. Compilers already do loop idiom recognition (if you write a memcpy as a loop, LLVM will recognize it as a memcpy and convert it to faster memcpy idioms). But recognition is of course limited to known kernels; we don't have good general-purpose tools. Automatic optimization for parallelization, vectorization, cache hierarchy (block loops out so everything sits in L1 cache, for example) are all well-known, but they tend to turn out to be extremely problematic to work in practice because languages suck, and many of the core kernels can be wrapped up in autotuned libraries (e.g., FFTW, ATLAS).
Whole-function optimization, interprocedural, and whole-program optimization are much less mature. Whole-function is used for many microoptimizations (dead code and various kinds of partial redundancy elimination), but it's not really feasible for higher-level algorithm analysis. Interprocedural optimization is largely limited to figuring out if inlining functions would help reduce code size or dead function analysis, and whole-program is used to improve the quality of these kinds of analyses.
The frontier of compiler research (and in terms of shifting research prototypes to product compilers) is in moving our techniques to larger and larger program slices. Program synthesis can already automatically generate specialized data structures from the queries you will make on them, for example. As the original paper points out, making these techniques easier and more readily available is likely going to the main program here for the next two decades or so.
Not true, because the lower-level languages introduce far more bugs which wastes user time even more because they can't get their work done.
Lower level languages these days are only used where performance and resource use must be controlled for. With Rust, that too will soon be a thing of the past.
edit: Now I understand you're probably replying to a comment (https://news.ycombinator.com/item?id=17950490), and probably accidentally made your response a top-level comment.
The current focus is on improving the underlying VM, cperl, a fork of perl5, to enable most traditional optimizations, such as types, compile-time classes, inlining, loop unrolling, lazy parsing, type tracing, ... The optimized compiler or jit would then be about 4x faster, while still keeping the memory resources down. Recent efforts with static perfect hashes for const unicode data brought down memory by factor 10.
But money is not flowing, on the contrary, it was taken away, so we will see. The dynamic language communities are very hostile to compile-time optimizations. only recently type hints got adopted. but there's so much more to do.
We now have machines that are fast enough for many/most activities, as evidenced by production code that's written in Ruby, Python, JS, etc. For these we don't really need optimizations.
On the other hand, performance critical routines tend to require human attention, and for these the approach of having the optimizations fully automated is generally less than helpful.
As Knuth put it, in 1974 nonetheless:
"For some reason we all (especially me) had a mental block about optimization, namely that we always regarded it a behind-the-scenes activity, to be done in the machine language, which the programmer isn’t supposed to know. This veil was first lifted from my eyes in the Fall of 1973. when I ran across a remark by Hoare [42] that, ideally, a language should be designed so that an optimizing compiler can describe its optimizations in the source language. Of course! Why hadn’t I ever thought of it?
Once we have a suitable language, we will be able to have what seems to be emerging as the programming system of the future: an interactive program-manipulation system ..." -- http://www.cs.sjsu.edu/~mak/CS185C/KnuthStructuredProgrammin...
So let's have systems/languages that allow us to express performance constraints and performance-oriented transformations, and let the compiler/language assist us in doing this.
* As you pointed out, we are moving to higher-level constructs and languages (this is directly addressed by a Pugh's talk as well); and
* "[...] in any case getting high-performance executables out of high-level languages seems to fundamentally require aggressive compiler optimization".
In the other words, the widespread use of higher-level languages does not prove that the (automatic) optimization is not needed, but rather that the needs for higher-level languages are very high despite of the cost. And indeed, all languages you've mentioned have highly optimized interpreters or JIT compilers, albeit crafted by humans.
I also feel that the paper importantly discusses the speed and correctness of code optimization along with the resulting optimized code (Thesis 1), and it is not just for the fully-automatic optimizer as you detest. The correctness of such program transformations will eventually require many tools mentioned in the paper.
I missed the reference to Bernstein (and Pugh), thanks! Though they seem to think he was kidding. I don't think so. A little tongue-in-cheek, maybe, but not kidding, because what Bernstein and Pugh discuss are very real.
Most code is cold, most optimizations here are a waste of compiler resources, better to compile to a simple/compact bytecode to keep code-densities high and memory clean. (See also Google's recent experience with re-implementing their JS engines).
Some code is hot, here most compilers are not good enough, though we will take what they can give us, not necessarily because you need assembler (as Bernstein says), but because higher level optimizations that do 100x - 1000x are needed when coming from high-level code.
Often, the "cold" code is setup code, whereas the hot code is in loops that get run once set up, see the Scripted Components pattern. Of course, once you follow that pattern, you run into the Two Languages problem that Julia is trying to solve.
> getting high-performance executables out of high-level languages seems to fundamentally require aggressive compiler optimization".
If you (a) treat the compiler (or runtime) as a black box and (b) don't permit multiple levels (as per Knuth) than I agree, sort of. Except that you don't actually reliably get high performance that way. You may sometimes get high peak performance, if you're lucky.
Now they seem to argue that their approach would do away with the variability of that approach, by consistently/reliably burning through layers of abstraction.
"finding optimizations using aggressive search algorithms and SMT solvers that are, unlike humans, not easy to fool with superficial changes of representation."
I wish them cough sufficiently smart compiler cough luck, particularly when the goal is also to make/keep compile times reasonable. I also have a hard time with the phrase "unlike humans, not easy to fool", because what's easy to fool here is the compiler, and the "superficial changes of representation", as the changes needed are often not superficial.
To me, an alternative solution to the the Scripted Components / Two Languages problem with progressive refinement and the ability to specify constraints seems like the right path. So instead of, for example, writing high level (OO?) code and hoping that the compiler/runtime will do the escape analysis and put things in registers instead of allocating them on the heap, you write the same code and then (a) specify that you don't want heap allocations in a particular region (b) have the compiler tell you whether that was possible and (c) assist you in putting in annotations/transformations that accomplish this goal and remain visible in the code, possibly separate from the other other code.
Only if you think that things like power savings and being able to run more on the same hardware are not important.
So machines are fast enough that a lot of people are happy making that trade-off, and it's hard to argue that they're all wrong.
And of course they are also fast enough on single user machines (PCs, phones, tablets) that typical frameworks and 'best practices' often waste orders of magnitude of performance and developers don't even know or care to find out, and if they find out don't care enough to fix it.
Pretty much everyone agrees that climate change is bad but if you base your ... say, meat consumption or car usage on what others do you are going to wait a long time
Now we do have a few language constructs to help us here, although sometimes it's not enough. We have inline, restrict, register as well, although that one is not really used a lot in practice in my experience (at least not for its original purpose). We have compiler extensions for computed GOTOs, alignment constraints etc...
In this context what would "an interactive program-manipulation system" look like? Personally I think we could use more standardized constraints in languages like C to be able to annotate code in a way that could be useful to optimizer, such as tagging "cold" code, having control of the prefetcher and being able to write SIMD code without using intrinsics (a very complex problem admittedly). Standardizing computed gotos would be nice as well.
Beyond that, in my experience a big problem with modern architectures is that it's very much non-trivial to figure out what's the fastest way to implement an algorithm. You have to consider which CPU model you're using, the cache architecture, RAM speed ... Second-guessing the compiler is pretty hard if you don't have a lot of experience optimizing for a particular architecture.
I imagine he was thinking about human-directed program transformations that are almost language and machine-independent, implicitly high-level, whole-program stuff, rather than aimed at writing "idiomatic" fast machine code. So I guess not the kind of optimization you have in mind.
What sounds more applicable for your use case would be profile-directed optimization, maybe based on mutating an initial fragment of assembler in ways that preserve its semantics but might improve performance. Like https://en.wikipedia.org/wiki/Superoptimization. But unless you wanted to create an instruction set that included reflection as a feature, this would most conveniently be written in another language.
Edit: I should clarify, obviously self-modifying code written in assembler is in some sense reflective, but it's hard work.
This is one of the properties that makes an idea a worthy research direction.
Indeed, we need better abstractions, like cache-oblivious data structures.
This one is somewhere in the middle, to be honest (no offense meant to your friend). I realize what people writing research papers have to deal with (really!), but the words "scales to 837 instructions" and "practical" should never appear in the same abstract.
PBQP and friends can handle larger functions in better time bounds (and give near-optimal or optimal results for the problem they solve).
This is one reason PBQP is actually part of LLVM mainline.
Unison (the framework your friend uses), will never be part of LLVM (or GCC, or ...) unfortunately.
Register Allocation and Instruction Scheduling in Unison
http://llvm.org/devmtg/2017-03//assets/slides/register_alloc...
Front end vs back end.
For instance, it's peephole optimizations are also a chunk of hand-written C++ code (https://github.com/facebookincubator/BOLT/blob/2ed436a6d3b17...), and thus could benefit just as much from the more declarative (and possibly SMT-driven) ideas in this paper.
Finally, there's all sorts of optimizations that are only possible because of high-level information from the source language. For instance, removing unnecessary loads & stores requires knowing pointers don't alias, which is very difficult to deduce given unannotated integers (most of this is driven by language rules, such as the (controversial) TBAA in C). Additionally, even the BOLT paper itself mentions things that can be understood (and optimized for) from a higher-level language, but are much harder to deduce from a raw binary (Section 8):
> Indirect tail calls are more challenging for static binary rewriters because it is difficult to guess if the target is another function or another basic block of the same function, which could affect the CFG
And, the paper touches on your curiosity in the conclusion:
> Nevertheless, a post-link optimizer has fewer optimizations than a compiler. We show that the strengths of both strategies combine instead of purely overlapping
(Oh, one more post-finally thing, there's probably an argument to be had that BOLT fits into the (backend) superoptimizer category of the paper.)
I think there is an error on page 9, though: ”Second, −a+−b can be rewritten as −(a − b)”. I think that should be either a left-hand side of ”-a--b” or a right-hand side of ”-(a + b)”.
Two things:
1) If you are writing a compiler and NOT using Prolog you are almost certainly working way too hard.
2) I think I can see an alternate reality where compiler-like software exists but high-level programming languages as such do not.
If you are trying to write a compiler for anything but a toy language in Prolog, you are going to be at it for far too long without getting anything done.
"Logic Programming and Compiler Writing" David H. D. Warren (this is the kickoff.)
"Parsing and Compiling Using Prolog" Jacques Cohen and Timothy J. Hickey
"Provably Correct Code Generation: A Case Study" Qian Wang, Gopal Gupta
"From Programs to Object Code and back again using Logic Programming: Compilation and Decompilation" Jonathan Peter Bowen
"Automatic Derivation of Code Generators from Machine Descriptions" R. G. G. Cattell