Really cool article. Posts like this always make me wonder what the state of the programming would be if browsers hadn't sucked up almost all of the world's compiler optimizers.
Look at what Mike Pall did with LuaJIT2 - I assume if the world wasn't so focused on the web, we would see more of it in other languages. But really, things aren't that bad. Microsoft has enough good people working on RyuJIT, PyPy has some of the best people advancing metatracing JITs, and Mike Pall is a god among men.
But considering that optimized scalar code performance has moved, what, maybe 40% over the last two decades, I'm going to say "not much". Compilers are sexy, but they're very much a solved problem. If we were all forced to get by with the optimized performance we saw from GCC 2.7.2, I think we'd all survive. Most of us wouldn't even notice the change.
I'd disagree. Classical compiler work is very mature, yes - and new progress in things like register allocation and backend IR-based optimization stuff is well trod ground.
But in the context of JIT compilers for dynamically typed languages, in particular the space involving runtime inferred hidden type models, there is a TON of work left on the table.
It hasn't been paid much attention to in academia, IMHO largley because of a historical perspective on optimizing dynamic languages as "not classy" work among language theorists. I hope that perspective changes over time.
> Compilers are sexy, but they're very much a solved problem.
Not for all of the other widely-used languages that still have incredibly simple interpreters. Think how much energy could have been saved if Ruby, Python, and PHP were all as fast as your average JS engine.
Ruby has massive adoption, as do Python and Perl and PHP. Environments with objectively better performance like the JVM and .NET have not, in fact, done all that well comparatively in this environment (which is to say they've done fine too and achieved "massive" adoption, just not that much better than their slower competitors).
In fact, looking at the market as it stands right now I'd say that performance concerns are almost entirely uncorrelated with programming environment adoption.
Considering the massive speed improvements we have been seeing in Javascript, but also languages like Ruby, I'd say compilers is a solved problem for staticly compiled languages, but perhaps not as much for interpreted highly expressive languages.
Sort of. Lisp had a good combo of expressiveness and speed in the 80s, but it reached that point on the efficiency frontier by different techniques, like heavier use of macros. The newer techniques like trace compilation can make life even better, but the language design decisions in Ruby/Python/etc. that made that sort of thing necessary if you want speed, they didn't really pay for themselves from the perspective of smug Lisp weenies like me who were happy enough with our language and just wanted pragmatics like libraries.
ajross is right. People choose the languages they like regardless of performance.
JS perf is important to users though. Faster execution means fewer watts spent rendering and interacting with your favorite web page.
(Fun fact: B3's backend contains a machine description language that gets compiled to C++ code by a ruby script, opcode_generator.rb. We use Ruby a lot.)
And Go proves munificent's point: it doesn't have many compiler optimizations either. (This may change with the WIP SSA backend, but the point remains that Go gained huge popularity in spite of having a non-optimizing compiler.)
Yeah, more interesting is having them rediscovering Turbo Pascal compile speeds.
EDIT: I wonder why the positive effect to re-discovering that not all compilers need to be like C and C++ compile speeds and that it was once upon a time mainstream, is worthy of downvotes.
Can't critique this one: Go was an attempt to re-create the Oberon experience in modern setting with some additions from other languages. Rather than accidental re-discovery, getting Oberon (not Pascal) speed out of the compiler was an explicit design goal. One of few examples of modern IT really learning from the past.
Unfortunately, they didn't learn about the stuff between Oberon and 2007 that would've been nice to have in a modern, app language. ;)
For the curious (I am sure pjmlp is well aware of this) D and Go compile speeds are pretty neck and neck. DMD was faster, then Go caught on, not sure which one is faster now, depends on the nod. If I may add, D is a lot less impoverished than Go, although its coroutines story is not that strong.
Are you claiming Go runs at the speed of Ruby/Python/PHP etc? Because from what I read, migration to Go from above mentioned language led to lot of hardware / memory saving.
I'd think Java can certainly be considered having highly optimized compiler / runtime. But it has almost same performance as Go and much higher memory usage compared to Go.
> Are you claiming Go runs at the speed of Ruby/Python/PHP etc?
No. I'm claiming it doesn't perform anywhere near the level of optimization of GCC and LLVM.
> I'd think Java can certainly be considered having highly optimized compiler / runtime. But it has almost same performance as Go and much higher memory usage compared to Go.
I disagree with what seems to be your implication that compiler optimizations don't matter (and almost everyone else who works on compilers would also disagree), but I don't really want to turn this thread into a critique of the benchmarks game, so let's just leave it at that.
Please don't jump to the conclusion that huge differences in the default memory allocation of tiny 100 line programs means there will be similar huge differences between ordinary large programs.
Notice that even for those tiny 100 line programs, the difference can be more like 2x when memory actually needs to allocated for the task.
"Compiler optimization" in this thread is referring to speeding up compilation time†, not runtime of generated code. Go produces fast code, but the go compiler does not generate that code particularly quickly.
† Which can be seen as a runtime cost for interpreter+JIT languages, but that's a different issue. We're talking time-to-steady-state when the interpreter is fed a file (which is something Javascript engine devs worry about a lot), not benchmark-speed-at-steady-state.
Compilers are sexy, but they're very much a solved problem.
This may be true for sequential languages, but is very much false for the compilation of concurrency and parallelism. It's basically not known how to do this well. Part of the problem is that CPU architectures with parallel features have not yet stabilised.
For sequential languages the problem has shifted: how can I get a performant compiler easily. The most interesting answer to this question is PyPy's meta-tracing, and that's work is from 2009, and far from played out.
> optimized scalar code performance has moved, what, maybe 40% over the last two decades
I'm not convinced. Raw single-thread number crunching performance is somewhere around _two to three fold_, clock-for-clock, on Intel x86, over that of 10-15 years ago. What methodology do you use to attribute only a fraction of those gains to language optimizers? And even if you are correct, why is it meaningful? Who is going to have invested energy in optimising the shit out of mundane codegen when hardware performance will have just come and stolen your thunder a few months later?
The problem we have now is that CPUs are gaining ever more complex behaviour, peculiarities, and sensitivities. I'd say compiler engineering is far from a "solved problem", even for statically-typed languages.
> The problem we have now is that CPUs are gaining ever more complex behaviour, peculiarities, and sensitivities.
With mainstream CPUs, exactly the opposite is happening. CPUs are getting more complex under the hood, but less sensitive to code quality. For example, a lot of the scheduling hazards in the P6 microarchitecture have been eliminated in subsequent iterations. Branch delay slots are a thing of the distant past, so are pipeline bubbles for taken branches, indirect branch prediction is extremely capable, even the penalty on unaligned accesses is minimal.
Well, sure, but SIMD more than compensates for all of that, given how hard autovectorization is. In fact, I think with things like AVX and NEON becoming ubiquitous, you can get more benefit out of writing in assembly (or intrinsics) than any time I can think of in the past 10 years.
> Compilers are sexy, but they're very much a solved problem
No they're not, and won't be for long (ever?). However it does not matter because they are "good enough".
Compilers are driven by heuristics which provide "reasonable" results in most cases for common architectures. But they still leave a lot on the table. Compiler writers have to trade compile-time with execution-time.
Now we're not talking about an order of magnitude, but rather ~20%-30% in some workloads. When it matters (I guess for people like Google/Facebook/Amazon/... it translates in electricity bill and a number of racks to add to the datacenter) people may have to get down to the assembly level for a very small (and hot) part of the program.
That seems a bit chicken-and-the-egg-y though: if the web didn't become a global phenomenon then there would be far less interest in improving the browsers, far less business need for programmers, and far fewer people working on whatever they'd be working on if they weren't working on browsers.
They're solving a non-issue. The rest of the world is perfectly fine with the statically typed, well designed languages that are easy to compile. And only the web world is so obssessed with smart compilers compensating (impressively, but still far from being sufficient) for multiple deficiencies in the language design.
> The rest of the world is perfectly fine with the statically typed, well designed languages that are easy to compile.
Python, Ruby, PHP, and Perl aren't "the rest of the world"? As far as compilers are concerned, all of those languages have more troublesome semantics than JavaScript does.
> And only the web world is so obssessed with smart compilers compensating (impressively, but still far from being sufficient) for multiple deficiencies in the language design.
You have no idea how much compilers have to compensate for the deficiencies in C and C++'s design.
Nobody really cares about their performance. They're just fine with their simple interpreters. Web is different, there is no choice, no fallback to C.
And no, thank you kind sir, but I've got a very good idea of what compilers are doing wrt. C deficiencies, I was writing OpenCL compilers for 6 years at least. Besides aliasing stupidity and byte-addressing there is nothing really bad to compensate for.
> Web is different, there is no choice, no fallback to C.
asm.js and Web Assembly.
> Besides aliasing stupidity and byte-addressing there is nothing really bad to compensate for.
Aliasing issues, C++ heavy reliance on virtual methods, too many levels of indirection in the STL, overuse of signed integers due to "int" being easier to type interfering with loop analysis, const being useless for optimization, slow parsing of header files...
For example in JS, once you prove that "o.f = v" is not going to hit a setter (or you put a speculative check to that effect), then you know that this effect does not interfere with "v = o.g" (provided you check that it's not a getter). JS VMs are really good at speculating about getters and setters. The result is that alias analysis, and its clients like common subexpression elimination, are super effective. It's only a matter of time before we're creating function summaries that list all of the abstract heaps that a procedure can clobber so even a function call has bounded interference.
This is totally different from C. There, making sure that accesses to o->f and o->g don't interfere is like pulling teeth. And the user can force you to assume that they always interfere by using -fno-strict-aliasing, which is hugely popular.
The fallback-to-C paths on the web aren't that great, though. At least not yet. Once you fall back to C, you're sandboxed into a linear heap with limited access to the DOM and JS heap. But we'll fix that eventually. :-)
Web Assembly is not even there yet, asm.js up until recent was more a toy and a standalone runtime, I have not seen it being routinely used for a fallback, nothing like, say, python with C modules.
As for virtual methods, it is a problem of a bad C++, devirtualisation may help, but nobody cares in general. We have a cool curiously recurring template pattern instead.
But for the integers you're right. And signedness is still the most annoying source of bugs in the infamous LLVM instcombine.
Headers are a frontend issue, nothing to do with the optimisations.
> Web Assembly is not even there yet, asm.js up until recent was more a toy and a standalone runtime, I have not seen it being routinely used for a fallback, nothing like, say, python with C modules.
That's because (a) page performance is frequently gated on things other than JavaScript, so people don't go through a lot of trouble to write C++; (b) many modules that would be written in C in Python are provided by the browser itself; (c) JS itself is usually fast enough, since the gap between JS and C++ is much less than the gap between Python and C++.
> As for virtual methods, it is a problem of a bad C++, devirtualisation may help, but nobody cares in general.
Huh? Tons of people care about devirtualization! Much of the reason Firefox builds go to the trouble of PGO (and it is a huge amount of trouble) is to get devirtualization.
> As for virtual methods, it is a problem of a bad C++
So I could say the same thing about JavaScript: if it's slow, you're writing "bad JS". But you would rightly reject that as invalid: if the code people write in practice is slow, then the problem is with the language encouraging people to write slow code. The point is that the same thing applies to C++.
Re: int, isn't it the reverse? I.e. don't compilers find loops using ints easier to optimise because they can assume the counter does not wrap?
Also, what do you mean by level of indirection in the STL? Pointer chasing or, I suspect, layers of layers of tiny functions that need to be inlined for reasonable performance?
> statically typed, well designed languages that are easy to compile
Which ones are these? All of the statically-typed and well-designed languages I can think of are, at the least, hard to compile well, if not hard to compile in the first place. (Haskell and Rust both come to mind; there are few Haskell compilers other than GHC, and no Rust compilers other than rustc.) The languages that are easier to compile are either not statically-typed in a useful way, or not well-designed, or both.
I've never heard anyone say Ada was easy to compile. Also, I heard its uptake was slowed by how hard it was to get the early compilers working. So, where did you see an easy one? Seriously, because Ada still needs a CompCert (or at least FLINT) style certified compiler. An easy Ada compiler would be a nice start on that.
I always thought that Ada was easy to compile in the backend (i.e. the moral equivalent of what B3 does) but challenging on the frontend because of how large the language is. Could be wrong though.
The frontend is usually the hard part IMO. In WebKit, we have 100,000 lines of code for our "frontend" (i.e. the DFG compiler) and 50,000 lines of code for our "backend" (i.e. B3). That split is really interesting.
It's what I thought, too. The split may come from the fact that the front-end is more complex, richer in information, harder to analyze, and harder to transform. The more you can do with it the more code it takes to represent. That's my hypothesis.
Far as Ada, I figured it would be difficult due to the large number of language features and complexities of analyzing a program for safety w/ all its rules. And any interactions that might emerge in that between features and rules. Could be easier than I think but my default belief is that it's not easy.
You can't compile Rust without types and inside functions, most types come from inference and coercions, so "type checking" is really "type resolution".
> Rust (and Haskell) is not easy to _type-check_ though.
Is that really the case? It seems to me that a Prolog-like resolution system, coupled with a constraint solver, would get most of the job done with little effort.
There are certainly many rules to keep track of, but in some cases the newer rules are strict generalisations of the older rules. For example, Haskell's original type classes are just a special-case of modern multi-parameter, flexible instances/contexts, etc. type classes. Likewise, we can implement constraint kinds, type class instance resolution and type equalities using one constraint solver.
Hindley-Milner is already quite Prolog-like. But you're right, CLP(fd) rocks for typing.
My usual approach to implementing a type system is to derive a flat list of Prolog equations out of the AST and leave it to Prolog for solving. If you ask what to do with error messages, I've got a comprehensive answer, but it is not for a mobile phone typing.
I don't understand this perspective. Is the point that JavaScript just works such that you don't have to worry about it compiling at runtime?
To me this is the difference between knowing that your program will probably work after it compiles, vs not knowing until after its deployed.
What I think people really enjoy in dynamic languages like JavaScript is the instant feedback, just reloading the browser. This can be accomplished with decent IDEs for most statically typed languages.
I don't believe anyone's arguing that the overhead of static checking is not worthwhile, merely that it involves serious work on the part of the compiler developers that should not be dismissed.
While they have sucked up a lot, it is far from certain all would have been employed optimizing compilers if that hadn't happened. Demand tend to create the supply.
Also, many of the improvements done for JS will certainly trickle down to Python, Ruby, PHP eventually.