A common question that comes up is “why not just convert to the IR of {llvm,gcc,...} and go from there?” I think there are 3 major reasons:
- Compiler speed. I intend our SSA IR, and the optimizer passes implemented on top of that IR, to be fast by design. We’ll aim for linear-time algorithms wherever possible. The backends of other possible compilers weren’t really designed with fast compile speed in mind.
- Runtime information. The runtime needs accurate maps of stack frames for both GC and stack copying, something that is not available from standard backends today.
- An additional dependence. Do we want a {llvm,gcc,...} backend as a prerequisite for building Go? (Note that this would only be an issue for those developing Go, not those writing Go programs.)
I’m happy to be convinced otherwise - maybe we should throw our effort into getting frame maps out of {llvm,gcc,...} and figuring out how to configure the backend (e.g. which optimizations to turn on) to make it compile quickly.
Note, for the record, none of these are correct except for the last one:
1. LLVM's SSA based compiler currently uses more linear time algorithms than Go's SSA backend (IE phi placement, etc), and in more places. So yeah.
While parts of LLVM definitely could be sped up (particularly the backend), it was originally designed with fast compile speed in mind, just like go! Given how many years it's taken so far, you easily could have gotten the same thing out of LLVM. Would it have been more work? Probably, but not much. Are the other reasons not to do it? Yes. But the idea that their compiler is somehow the only one designed with fast compile time in mind is, honestly, pretty arrogant
2. Stack maps have been supported for quite a while, and statepoint support now exists and is used by real people in real places.
But i'll also just point out he's never actually asked, or talked to the LLVM folks about it (search the mailing list, see if you can find any mail about it).
Note: I honestly don't care whether they write their own compiler or not.
I suspect it's better for them to do it because of the community they want to build, because of how much control they want over their toolchain, etc.
But i'm not a fan of saying "someone else's infrastructure sucks, so we are doing it", when
1. That's not the real reason as far as i can tell
2. People are using, in production, the very things they claim don't exist (and they've been told this, it turns out)
3. Answers about linear time algorithms are honestly just BS.
Agreed. Though another argument in favor was not cited: the SSA backend is in Go, so that means that anyone who knows Go can also hack on the SSA backend. With LLVM, they would have to know Go's internals and C++.
Of course, there is also gccgo and llgo, so once the SSA backend is in stable Go, useful comparisons can be made.
Using llvm might introduce a dependency, but it also gives all the LLVM advantages/disadvantages across platforms for "free" (some work, fewer reinvented wheels) and more toolchain utilities.
i think that this is a gimmick rather than a reason.
languages that have their own tools built with themselves are cool... but it has zero practical value imo. the number of C/C++ programmers interested in Go and capable of contributing meaningfully far outweighs the number of programmers who do not know C/C++ and are interested in Go
No, stack maps provide information about each stack frame (typically using the return instruction pointer left in that frame) to allow for the garbage collector to determine what is a pointer or not in that frame.
No it's not. Segmented stacks are a way of allocating smaller stack segments that are linked together with pointers and kept in the heap and is a means of implementing coroutines. Safestack is more complicated and it segregates the stack into 2 parts to prevent stack buffer overflow attacks.
It is untrue, given the same amount of work put into both (IE if they had spent their time doing llvm instead of their own ssa backend).
Remember the SSA backend of Go was slower than the normal go compiler for the vast majority of it's life as well.
In any case, people like to build shiny new things they think they can do better at, instead of fixing things that are, in actuality, probably better for what they want but need a little work.
The truth is that there is no magic in building good compilers, so it's not like anyone comes along, waves a wand, and produces a compiler that is X times faster or better than anyone else's.
I can think of a lot of good reasons to write their compiler in go, and not use LLVM. Technical reasons are ... not any of them :)
> Remember the SSA backend of Go was slower than the normal go compiler for the vast majority of it's life as well.
Go 1.7 in August will be first release with SSA backend. So I do not understand what is that vast majority of life besides development phase of 1 year or so.
> In any case, people like to build shiny new things they think they can do better at, instead of fixing things that are, in actuality, probably better for what they want but need a little work.
I agree with that. It could just be a comment on our society.
> I can think of a lot of good reasons to write their compiler in go, and not use LLVM. Technical reasons are ... not any of them :)
I think goroutine and segmented stacks support was mentioned as technical reason.
The reasons why Rust is slower to compile are basically (a) typechecking takes longer; (b) LLVM does way way more optimization than Go's backend does. (b) applies even at -O0 because it has to go through LLVM IR to SelectionDAG to MachineInstrs, while Go 6g/8g pre-SSA can just go from AST to MachineInstrs. (We can't use FastISel at the moment because FastISel has no support for unwinding, among other minor reasons.)
If Go adds all the optimizations that LLVM does, then I have no reason to believe that it won't end up just as slow as LLVM.
There's active work to fix both (a) and (b): for (a) there are ideas for an O(1) unifier in typechecking, and for (b) we're working on MIR (which is now able to self-host) to do higher-level optimizations on a language-specific IR to avoid punting them to LLVM, where it may take more work to figure out. (For instance, we can do inlining on polymorphic functions, reducing the time complexity from O(number of instantiations) to O(1).) But the biggest wins will come from incremental compilation, which there's been a ton of progress on lately and might just fix the compilation time issues once and for all in practice.
So my non-expert, just-a-normal-programmer feeling is something still doesn't add up -- I feel like you could compile C++ with optimizations off, and it would still lose at compile time, and really lose at runtime, to Go.
So somehow Go is compiling quickly and running fastishly.
So "it doesn't do optimization is why it compiles fast" is confusing.
Is the story that Go, as a simpler language, is able to compile to decently fast code w/ fewer compiler optimizations?
I'm thinking along the lines of C++ zero-runtime-overhead template stuff is very-large-overhead w/o optimizations.
I've only played a tiny bit with Rust, and it was a long time ago, but my experience is there was no "fast compile time, decent runtime" configuration available. Naturally, that's a really good configuration to have accessible if possible!
Yes, C++ is dependent on optimizations. It's not that C++ is a complex language and that Go is a simple language, though--in fact, due to GC metadata Go is on the whole probably more complex than C++ once you get to the LLVM IR level. C++ (like Rust) is runtimeless and has no data structures built-in, so every time you use a hash table (for example) the implementation of the hash table is compiled alongside your code. In Go, hash table operations compile to opaque runtime calls (I believe), to a runtime that is always optimized. This is faster for compile time, but it's slower for runtime, frequently much slower because containers benefit heavily from IPO. (For instance, SROA and inlining are a powerful combination, allowing for the length of a short-lived array to be promoted to an SSA register and thereby allowing vectorization, etc.)
Go's compiler is not competitive with a mature backend like GCC or LLVM. It's "fastish" for the niche it's in, but there's no substitute for the nonstop 10+ years of optimization work that has gone into the flagship open source compilers. I don't see LICM in Go's source at all, for instance, and that's a really basic one.
> I've only played a tiny bit with Rust, and it was a long time ago, but my experience is there was no "fast compile time, decent runtime" configuration available. Naturally, that's a really good configuration to have accessible if possible!
There is -O1, but it has basically the same compile time as -O2, so it's not used in practice.
I guess complex is an ambiguous word. Let's just agree that template-heavy "modern" C++ needs more optimizations turned on to get decent performance. So more optimizations => longer compiler times. (Not to even mention all of the parsing the headers multiple times, plus generating multiple versions of the code for all of the various type specializations!)
From the other replies, I feel like there's more to it than just optimizations though -- but as just a compiler-user, not a compiler-writer, I'm out of my depth and just reading tea leaves. :)
Reading those tea leaves, I'll be sadly surprised if the Go compiler ends up slow and happily surprised if a C++ compiler ever ends up as fast.
(I don't know enough about Rust to make any predictions. ;)
(PS. No disagreement that C++ has a higher performance ceiling than Go; of course hand-rolled asm still goes higher than that (ever tried running x264 w/o the assembly bits? it's painfully slow).)
Is the story that Go, as a simpler language, is able to compile to decently fast code w/ fewer compiler optimizations?
Sort of. But it's also that you're making bad comparisons. C++ has an include based compilation model and heavy reliance on template specialisation that means it'll never be fast.
What you should instead be comparing it to is Java, which is also a simple language, only slightly more complex than Go. However, that comparison is rarely made, because it'd show that compiling fast is not so special a trick ... Java also compiles extremely fast at every level, that's why it's possible to use a JIT compiler with it at all.
Given that "compiles fast" is Go's number one claim to fame, the reluctance to compare to the most popular compiled language is the elephant in the room.
What did it take to fo that in Java? When I tried Java on a Pent3, it took a few seconds to compile. The BASIC and Wirth languages could do tens of thousands of lines a second on same machine. Then they consistently ran faster than Java.
The only elephant in the room is the bloated, insecure platform sitting on many servers. Competition showed one could do much more with less CPU, memory, or money invested in tooling itself.
Dude is brillaint and did great work. Yet, the Oberons and Pascals compiled so fast my finger was barely off the key when they were done. Even the C/C++ editors werent that fast for Java. Allowed rapid iteration while maintaining mental flow. When done, you turn all the options on with that or a slower compiler to get fastest, production version. This has been true going back to the old, Ceres workstations where commenters here that used them reported instant compiles on CPU's with tens of MHz.
Barely any. Which leads us to differentiate between iterative and release requirements. Language like Go will kill on the former with Wirth-style compilees. A LLVM extension might have been better for latter. That was my recommendation a while back. Even still, the language is simple enough it should compile faster. Should != will of course.
On a Pentium 3? Don't you think such a comparison might be out of date? Java has changed a lot since those days.
Yes, Pascal/Delphi also compiles very fast, it's true, but they also forbid circular dependencies and impose other restrictions that caused a lot of developer pain.
Let's say we port it from P3 to multi-core, 2GHz x86. We want to know if prior performance was relevant as a predictor. As in, will difference choices made on old platform apply to new? Here's a few examples to illustrate:
1. Interpreted vs compiled language.
2. Simple, Oberon-like type checks vs Rust or Ada.
3. Several pages of BNF in grammar vs 1 or 2.
4. Designed for abstract, heap machine or just above real, stack machine?
5. Number of steps needed between source and efficient exdcution.
6. Number of times you perform those steps (eg AOT vs JIT).
7. Cache-awareness of design.
These are a few key differences between Java and Wirth-style languages then. They made compiles rapid on P3. Updating to multicore or 64-bit would be trivial given each update at ETH was a few undergrads work for 6mo-2yr. So, do lessons learned that those attributes Wirth-style greatly aid performance of compilers and runtime still apply today?
I think so given what Go accomplished in its time and resources. Other languages too with design decisions that proved out over time. It took truly epic work and investment to get Java to its current situation.
I havent heard people say Pascal caused them lots of pain aside from functional crowd or some wanting a few C++ features. What specifics bothered you? And why did you need circular dependencies?
Go wins at compile time in part because its import system avoids a ton of the redundant work that C++ includes bring with them. So, yes, go would compile lot faster than C+l -O0, but that's a language difference, not a compiler difference.
Wait, wait, did you say incremental compilation? As in, instantaneous compiles of individual functions like LISP or my old 4GL? Or cached, one-module-at-a-time compilation like most 3GL tools? Really hoping it's the former.
HELL YES! You people are embodying The Right Thing approach yet again! I just received more motivation to learn this language given it might soon be first mainstream one to equal LISP in a key way. Aside from the mainstream LISP in Java land of course....
Now, the only thing left is a real-time interpreter with live code updates. I recall the LISP box could do instant changes interpreted for exploratory stuff on running image. Solidify that super fast with per-function, typed compiles. Plus do whole program compiles if you had to. So yall getting close but what's odds of those other features happening?
Note: Live, interpreted image with save the world also makes it easier to debug stuff locslly and remotely. Send devs the whole, running state.
Some people have worked on a Rust REPL, but it wasn't really useable last time I checked. Part of the motivation to develop this was the possibility to use LLVM as a JIT, which is pretty nice.
Personally, I would love to see this as part of an IDE that can execute _parts_ of a Rust file with various inputs to quickly see if a function behaves as expected (this could also be easily converted into test cases.)
That's the idea. They're great for exploratory programming. In LISP, safety was optional. This was actually OK... would be in Rust... if your goal in that mode was to understand requirements, algorithm, solution space, etc. Get an idea of how you might handle it. Then, turn safety back on, try to get a solution going. When it works, compile that module. Future tweaks do incremental compilation.
> 1)-O0 code from LLVM will run faster than Go code?
It depends on the language. It would be interesting to see -O0 LLVM vs. 6g/8g on Go code.
> 2) Since we are talking order of magnitude more time, Will optimized code from LLVM will be order of magnitude faster than Go?
Maybe? If you vectorize it sure could be. But I don't see why it's relevant. Who cares if your final release builds for your browser are 10x slower if you're shipping them to 100 million users and they get a 3x speedup?
I guess you will agree business applications are far more commonly written than browser engines. For my business application in Java it is neither super fast to compile (~20sec from ant script). Quite slow to start due to VM startup time, and ok performance. I would really like if compile times are much faster.
Yes, LLVM was designed with speed in mind. However, look at how much faster compile times are in JS VMs compared to LLVM; LLVM's slow compile times are why none of them use it, even though they tried (e.g. WebKit which is dropping LLVM). A lot of SSA-based JITs are just a lot faster than LLVM.
I think it's a matter of tradeoffs. LLVM has multiple IRs on the way to machine code, some quite large, which let it emit pretty good output, on par with gcc. But other designs are possible that avoid a lot of that overhead, and can be far faster than LLVM, like JS VMs, B3 [1] and SubZero [2]. And clang is overall more or less comparable with gcc these days in terms of speed, it's no longer clearly faster [3] (although that also takes into account the frontend).
With all that said, I agree with you that making such a decision without talking to LLVM is a little silly. But, I doubt it would change the outcome: If Go wants fast compile times, has the resources to write its own compiler, and is ok with trading off throughput for compile time, then it's a reasonable decision to avoid LLVM.
You can certainly go faster than LLVM if you're willing to sacrifice code quality (which B3 and SubZero do... or for the extreme example there is no way on Earth LLVM will catch up to TCC). But I think that DannyBee is totally right that "we can go faster than LLVM at the same level of code quality just by rewriting it" is magical thinking. As far as I'm aware, there are no design decisions in LLVM that are pervasive mistakes that sacrifice compilation speed for no reason [1]. If there's nothing you can point to and say "THIS is what I'm going to do better than LLVM", then you're probably going to end up at the same speed as LLVM. The parent comment's point is that none of the attempts to answer that question have been valid: so far the reasons cited have been based on misconceptions about what LLVM provides.
[1] Well, OK, I'm not a fan of SelectionDAGISel's interpreter. But switching that to AOT won't result in huge differences in compile times. (Note that it's been a couple of years since I really worked with LLVM closely.)
Do you have a specific question?
It is not gonna be there before 2y I think. You can search for GlobalISel on the llvm mailing list to see discussions and patches.
I disagree. It's not that LLVM made "pervasive mistakes", it's that other design decisions can be much faster, such as those mentioned in the B3 JIT link above.
Of course, some tradeoffs are made, but actually I don't see why they substantially limit B3's output code quality. Perhaps slightly, but in return for a massive speedup in compilation times.
Well, if B3 is able to do something faster with the same level of code quality, then I'd say it was a mistake in LLVM to not make the same decisions.
But this proves the overall point: B3 is able to specifically say "we are going to be faster than LLVM because we are replacing RAUW with identities, packing multiple operands into an Inst, fusing operations into macro-ops, using arrays instead of linked lists, etc." Those are specific technical decisions that the WebKit authors believe will make things faster than LLVM, and they aren't based on misunderstandings of the things that LLVM provides.
I expect B3 and JS JITs in general to remain much faster, for the simple reason that speeding up compilation by 2x might be worth a 5% throughput loss for a JS VM (numbers made up, but you get the idea). But it is very unlikely such a tradeoff would be acceptable to LLVM, given the projects and corporations already heavily invested in it.
In theory, LLVM might support both a very fast compilation model and a slower and more efficient one. But supporting two complete codegen backends is a lot more effort.
And overall, codegen compilation speed has never been a priority for LLVM to anywhere near the extent that it is for JS VMs. It still doesn't have parallel codegen, while all JS VMs do. That shows the very different focuses on those projects.
"Well, if B3 is able to do something faster with the same level of code quality, then I'd say it was a mistake in LLVM to not make the same decisions.
"
It's more "nobody has had the time to erase this particular technical debt yet". Chandler, for example, is focused on erasing the debt of the old pass manager first. The B3 guys, had they focused on doing this in llvm instead of writing a new JIT + new passes + .... probably could have done that in less time.
But at this point, there are concrete plans to erase it, so as you suggest, it is highly unlikely advantages will persist in the long term :)
"it's that other design decisions can be much faster, such as those mentioned in the B3 JIT link above."
The B3 JIT link describes things that LLVM plans on doing in the next year, precisely for these reasons, so ...
Had they emailed the list, ever, they would have known this.
It's not like these were design decisions that someone said "we should never change these", they were design decisions that were good at the time, but like anything else, need to grow and change over time.
If you give up and rewrite an entire jit/compiler every time it might require rearchitecting, that may be fun but it doesn't make a lot of progress.
You will spend years to get to a no-regressions vs old compiler state (unless your old compiler was truly bad)
LLVM based toolchains compile hairy native code faster than any other tools i've seen... GCC, MS, Intel compilers for C/C++ are all very slow by comparison and the benefits are marginal (but still valuable).
for JIT or dynamic stuff LLVM is a poor fit. it doesn't surprise me that JS VMs do better with JS than LLVM, because there is no actual compilation involved as such - its a completely different class of problem, and its just not designed for that kind of language and environment, which is highly derivative, dynamically late binding and built in many layers, the vast majority of which are themselves compiled with C/C++ toolchains like Clang/LLVM, GCC or the MS compiler from necessity...
quoting that first article you link: "it isn’t specifically designed for the optimization challenges of dynamic languages like JavaScript."
To be fair, there are some limitations around stack maps that make certain things difficult (see [1] for an example), but I agree that there's nothing stopping them from just providing patches or feature requests to LLVM to improve stack map support for their use case (as [1] is doing).
> - Runtime information. The runtime needs accurate maps of stack frames for both GC and stack copying, something that is not available from standard backends today.
DannyBee addressed most of these points, however I just wanted to note that even if LLVM didn't provide stack maps, it's easy to recover stack information using lazy pointer stacks [1]
> Just as an experiment I cleaned up the runtime function mapaccess1_fast64 by hand in assembly and made it 29% smaller and with a speed improvement too small to measure.
There is no rigorous definition of functional programming. But SSA is trying to achieve similar goals. Google the paper "SSA is functional programming" by Andrew Appel if you want to know more.
I wonder if it'd make more sense for the go compiler developers to use ANF (A-normal form [0]) instead of SSA? ANF is less well-known outside of language research but seems like it'd be a better fit given the design of golang.
Doesn't seem easy to translate to it from an imperative language, the wiki page says it's used in functional compilers. Are there examples of ANF used for imperative languages?
SSA is fairly well studied, there are many algorithms to transform an IR into SSA and also lots of algorithms for optimizing programs in SSA form.
ANF is mostly used in functional compilers, but there are plenty of functional languages which aren't purely functional (e.g., Scheme, SML, OCaml) -- which is why I'm wondering if it could be adapted for a more imperative language like go.
Its not that ironic. SSA has the property that it's interference graphs are chordal and thus can be colored (an NP problem) in polynomial time. Aka, we can do optimal register allocation really fast. Among other benefits.
It doesn't matter how it's structured, just that it's faster.
That's just one advantage of many. Without SSA, you can't even constant fold without doing dataflow analysis. So I would say the structure is very important, that's why everyone is using it now.
C/C++ is not a good choice for writing a compiler. I do not know of any modern functional language compiler that is written in C/C++. But what does this have to do with SSA?
And then your CPU does it again! After all that work, your compiler outputs a totally ordered stream of instructions; then the CPU tries to figure out data dependencies in hardware and execute instructions out of order and in parallel.
It seems as though C-like imperative languages and x86 are baked in forever... but the world is actually parallel.
I've recently been thinking that we are looking at a situation analogous to the one Ben Franklin was in when he identified the two types of electrical charge as "positive" or "negative" pressure in the "electrical fluid" - he took a guess, which happened to be wrong, and ever since we have been stuck describing a surplus of electrons as "negative" and a deficit as "positive". This is no obstacle for the experienced but will remain an eternal hangup for beginners.
By analogy, of course, I am suggesting that the Church model of computation might have served us better as a foundation than the Turing model has done, since it seems that everything's turning up lambdas as the technology S-curve for silicon computers continues to flatten out.
Or maybe we needed to scale to some point with the Turing model for the Church model to assert itself and prove its merits in comparison.
It's a bit more thrilling to think of it that way, as a matter of scale. When space and time resources are scarce, thinking of the computer as a big piece of RAM that we mutate in-place makes the most sense. As we push upwards and outwards into enough resources and a bigger need for parallelism, it suddenly makes more sense to switch perspectives and reason in terms of binding and substitution.
That certainly makes sense. I'm just looking ahead over the next couple of centuries and imagining generations of young programmers stumbling over all these ancient vestiges of mutable state and synchronous, batch-driven control flow which will probably still be littered around the roots of our computing systems long after the dominant paradigm has shifted.
You can see the same pattern with IO models. We have programming languages descended from 50s-era concepts of computing in which the program drives the machine, but that just isn't true at all. A computer is a passive machine, not an active one: it reacts when you poke it with an interrupt, until it reaches a steady state and settles down again. Operating systems go to a great deal of trouble to simulate the kind of top-down flow control environment our imperative tradition wants to think it is operating in, but in order to get any real performance out of these systems, we all end up building asynchronous, reactive layers on top of the simulated batch-job anyway.
We'd all be better off if we flipped the paradigm, imagining the process of building a program not in terms of writing instructions for the computer to perform, but in terms of creating a structure which will react appropriately in response to whichever events may be brought to its attention.
Instead, we'll probably still be starting young programmers out with for-loops counting from 1 to 10 and printing the result on an imaginary console for decades to come, even though none of that is even remotely relevant to what's actually happening anymore, and once they've crossed that hurdle they'll promptly begin unlearning all that stuff in order to start getting real work done.
On an unrelated note, I spent a while last fall/winter playing around with the idea of a very low level functional language - could we use these techniques in memory-constrained environments too? I didn't find the model I was looking for, but I think it's probably out there, and it would be very interesting to develop a functional/type-safe/immutable language suitable for microcontroller programming, with no garbage collection or implicit allocation. It may be that the Turing model is a better fit for computing in the small, but I suspect that we may find dataflow and functional composition to be useful at all scales. That way of looking at the world has some profound philosophical strength, after all - "you cannot step twice into the same river" and all that.
I don't really agree... One reason is that computing models don't say anything useful about I/O, which we need in real computers. Turing machines have a straightforward extension to incorporate I/O -- execute it as a side effect at a given step.
In contrast, the Church model doesn't really have any notion of time, so it's not clear how to reason about I/O. What evaluation order is used?
In terms of computation, they're of course equivalent, so you can execute the Church model on the Turing-like machines (or more specifically a Von Neumann architecture). So maybe that was the right "choice" (if there ever was one).
There was an entire movement around dataflow processors AND dataflow languages in the 80's, where the instruction sets were not totally ordered (e.g. SISAL was single assignment). But these didn't fare well in the market.
Closer to the ground, there is a pattern of "throwing away information at interfaces" in computing. Interfaces like x86, C, Unix, etc. get solidified by evolutionary forces. The cost of that modularity is global inefficiency.
Another good example of that is the Java code gen architecture. People say "static types in Java code let you generated better code!" Well, no. The Java compiler throws out all the type information, generating Java byte code, which is dynamically typed. Then the JIT takes the byte code and has to re-infer all the type invariants to generate machine code.
> There was an entire movement around dataflow processors AND dataflow languages in the 80's, where the instruction sets were not totally ordered (e.g. SISAL was single assignment). But these didn't fare well in the market.
My understanding is that the dataflow architectures didn't fare well for technical reasons. The instruction-level parallelism they worked with turned out to be too fine-grained, i.e. the cost of scheduling was greater than the win of parallelism for many programs, especially normal sequential programs that still need to be fast. This led to research in coarse-grained dataflow, but it doesn't seem that much has come of that.
Unless you have a VLIW based architecture and the compiler takes care of the dependencies and hazard checking in software... then you are able to have dramatically simpler hardware (reducing area and power), along with faster performance!
Wait another month and a half and I'll be getting around to writing my blog post in support of VLIW, and why previous attempts have failed miserably.
Maybe this is a gross over-simplification, but isn't the tl;dr that VLIW architectures require significantly smarter compiler backends, and compiler writers were having none of that?
Very overly simplified, but yes. Thankfully my team will be showing the significantly smarter compiler in the coming months. It is primarily for our own architecture that is both VLIW and requires full software management of the memory, but a lot of the techniques we have developed can improve compilers in a general sense. We have also built all of our work within/around LLVM, so our optimizations that occur on the LLVMIR can potentially be applied to other backends, and our backend optimizations make very performant VLIW scheduling actually real.
I've talked with the Mill folks, and while I find their architecture intellectually/academically interesting, I just don't think that stack machines will ever take off. We've stuck to the tried and true von Neumann, while dramatically increasing memory bandwidth within a core, throughout a chip, and when connecting multiple chips, along with enforcing strict determinism at a hardware level, which is why our compilers work. We have one ACM paper published that is intentionally vague, but describes at a high level our scratchpad (software managed) memory techniques... we'll be talking the specifics of our full toolchain later this summer when we have a full public unveiling of the architecture.
Another problem with Mill is that they have been around for a little over 10 years, and have not released anything publicly (though have given a number of very detailed talks). They have had a lot of trouble getting their design into FPGAs, and even more trouble with having working compilers. When I started REX, I believed in getting it into silicon as fast as possible, as that is the point when people would take us seriously. We closed funding in July of 2015, and are taping out our first silicon next month... While many have called us crazy (and we will be giving real information on why we are not that crazy), I definitely don't want to be called vaporware.
The "belt" is very reminiscent of a stack. I was generalizing, but it is much closer to the traditional stack machine in terms of execution without registers than a load/store based RISC machine like every other mainstream architecture is at this point... Even though x86 is technically a CISC ISA, the actual mainstream implementations of it are RISC internally.
At least for myself and my computer architecture friends/colleagues, most of us just throw Mill into the stack machine box even if it is not entirely true... the benefits of the Belt architecture over the traditional stack machine are there in concept, but Mill has also not released any real concrete information on their compilers (at least from what I have seen).
Wow, cool stuff. I've just checked your company's website. Do you provide any resources to programmers interested in learning your architecture? (Emulators, a reference manual for your instruction set, etc.)
Thanks. We'll be releasing a lot more information this summer, but most of our effort has been in actually getting things finished for tape out next month. We currently have some partners that are early evaluators using our current tools and FPGA based platform, and are trying to figure out the best way to make this more publicly available.
We'll have actual hardware development/evaluation kits available this fall, so feel free to contact us or sign up for our mailing list to be alerted when we release details on all of that. As I said in a previous post here, I strongly believe that most people do not care about something that they can not physically touch, so I expect that most developers would much rather start to learn about and work on an architecture that actually has silicon available.
And then the CPU itself is a bunch of wires running in parallel with careful synchronization to pretend to be a serial or barely parallel (multicore) machine. ;)
I wouldn't describe SSA as "a functional language". It was originally designed as an IR for imperative languages, not functional ones. (The functional folks prefer CPS, which really is a functional language.)
I think one could read too much into the "single-assignment" part of SSA. Sure, functional languages don't tend to rebind variables either, but that's really all SSA has in common with them.
I'm familiar with Appel's "SSA is a functional language" article, but the vibe I got was more than he was trying to build some bridges between the SSA and CPS camps to try to get some cross-pollination going and knowldge sharing between them.
I think he could have just as easily called it "CPS is an imperative language", but my hunch is the FP folks are more persnickety and wouldn't have swallowed that as easily as imperative folks would accept the other title.
Like Appel, I wasn't entirely serious about it being a "functional language", but I think the point still stands, it is a major step towards a more mathematical program representation ("variables" instead of "assignables"). And just like "functional programming", the primary goal is ease of reasoning.
CPS is typically used to handle imperative control structures by impure functional programming languages, so it should indeed be of interest to imperative compiler authors.
The paper "A Correspondence between Continuation Passing Style and Static Single Assignment" by Kelsey, suggests SSA has a lot more in common with functional programming than you seem to believe it has.
Why was the Go compiler not based on SSA form originally? Isn't that kind of an embarrassment? All industrial compilers I'm aware of completed their transition to SSA ~15 years ago ... it seems bizarre that a compiler for a language started in 2009 wouldn't have been that way from the start.
Alternative viewpoint: go has also accomplished a lot of its goals for years without needing this. It could reasonably be viewed as a premature optimization.
It's a pretty big architectural change to any compiler, and when all other major compilers have paid that refactoring cost, it's very strange to want to go through the transition pain instead of just doing SSA up front like LLVM did.
Original Go compiler was based on plan 9 C compiler (http://plan9.bell-labs.com/sys/doc/compiler.html) because Ken Thompson and Rob Pike (co)designed and (co)implemented those compilers and they were 2 out of 3 original Go designers/implementers.
Those compilers are at least 16 years old so Pike and Thompson aren't as incompetent as you think them to be.
That just changes the question to why did they base their compiler on an obscure 16 year old codebase? I can guess that the answer is familiarity, but, that doesn't change the negative impact of a low tech compiler on the user base.
98 comments
[ 2.9 ms ] story [ 154 ms ] threadA common question that comes up is “why not just convert to the IR of {llvm,gcc,...} and go from there?” I think there are 3 major reasons:
- Compiler speed. I intend our SSA IR, and the optimizer passes implemented on top of that IR, to be fast by design. We’ll aim for linear-time algorithms wherever possible. The backends of other possible compilers weren’t really designed with fast compile speed in mind.
- Runtime information. The runtime needs accurate maps of stack frames for both GC and stack copying, something that is not available from standard backends today.
- An additional dependence. Do we want a {llvm,gcc,...} backend as a prerequisite for building Go? (Note that this would only be an issue for those developing Go, not those writing Go programs.)
I’m happy to be convinced otherwise - maybe we should throw our effort into getting frame maps out of {llvm,gcc,...} and figuring out how to configure the backend (e.g. which optimizations to turn on) to make it compile quickly.
1. LLVM's SSA based compiler currently uses more linear time algorithms than Go's SSA backend (IE phi placement, etc), and in more places. So yeah. While parts of LLVM definitely could be sped up (particularly the backend), it was originally designed with fast compile speed in mind, just like go! Given how many years it's taken so far, you easily could have gotten the same thing out of LLVM. Would it have been more work? Probably, but not much. Are the other reasons not to do it? Yes. But the idea that their compiler is somehow the only one designed with fast compile time in mind is, honestly, pretty arrogant
2. Stack maps have been supported for quite a while, and statepoint support now exists and is used by real people in real places.
But i'll also just point out he's never actually asked, or talked to the LLVM folks about it (search the mailing list, see if you can find any mail about it).
Note: I honestly don't care whether they write their own compiler or not. I suspect it's better for them to do it because of the community they want to build, because of how much control they want over their toolchain, etc.
But i'm not a fan of saying "someone else's infrastructure sucks, so we are doing it", when
1. That's not the real reason as far as i can tell
2. People are using, in production, the very things they claim don't exist (and they've been told this, it turns out)
3. Answers about linear time algorithms are honestly just BS.
Of course, there is also gccgo and llgo, so once the SSA backend is in stable Go, useful comparisons can be made.
languages that have their own tools built with themselves are cool... but it has zero practical value imo. the number of C/C++ programmers interested in Go and capable of contributing meaningfully far outweighs the number of programmers who do not know C/C++ and are interested in Go
Remember the SSA backend of Go was slower than the normal go compiler for the vast majority of it's life as well.
In any case, people like to build shiny new things they think they can do better at, instead of fixing things that are, in actuality, probably better for what they want but need a little work.
The truth is that there is no magic in building good compilers, so it's not like anyone comes along, waves a wand, and produces a compiler that is X times faster or better than anyone else's.
I can think of a lot of good reasons to write their compiler in go, and not use LLVM. Technical reasons are ... not any of them :)
Go 1.7 in August will be first release with SSA backend. So I do not understand what is that vast majority of life besides development phase of 1 year or so.
> In any case, people like to build shiny new things they think they can do better at, instead of fixing things that are, in actuality, probably better for what they want but need a little work.
I agree with that. It could just be a comment on our society.
> I can think of a lot of good reasons to write their compiler in go, and not use LLVM. Technical reasons are ... not any of them :)
I think goroutine and segmented stacks support was mentioned as technical reason.
If Go adds all the optimizations that LLVM does, then I have no reason to believe that it won't end up just as slow as LLVM.
There's active work to fix both (a) and (b): for (a) there are ideas for an O(1) unifier in typechecking, and for (b) we're working on MIR (which is now able to self-host) to do higher-level optimizations on a language-specific IR to avoid punting them to LLVM, where it may take more work to figure out. (For instance, we can do inlining on polymorphic functions, reducing the time complexity from O(number of instantiations) to O(1).) But the biggest wins will come from incremental compilation, which there's been a ton of progress on lately and might just fix the compilation time issues once and for all in practice.
So my non-expert, just-a-normal-programmer feeling is something still doesn't add up -- I feel like you could compile C++ with optimizations off, and it would still lose at compile time, and really lose at runtime, to Go.
So somehow Go is compiling quickly and running fastishly.
So "it doesn't do optimization is why it compiles fast" is confusing.
Is the story that Go, as a simpler language, is able to compile to decently fast code w/ fewer compiler optimizations?
I'm thinking along the lines of C++ zero-runtime-overhead template stuff is very-large-overhead w/o optimizations.
I've only played a tiny bit with Rust, and it was a long time ago, but my experience is there was no "fast compile time, decent runtime" configuration available. Naturally, that's a really good configuration to have accessible if possible!
Go's compiler is not competitive with a mature backend like GCC or LLVM. It's "fastish" for the niche it's in, but there's no substitute for the nonstop 10+ years of optimization work that has gone into the flagship open source compilers. I don't see LICM in Go's source at all, for instance, and that's a really basic one.
> I've only played a tiny bit with Rust, and it was a long time ago, but my experience is there was no "fast compile time, decent runtime" configuration available. Naturally, that's a really good configuration to have accessible if possible!
There is -O1, but it has basically the same compile time as -O2, so it's not used in practice.
I guess complex is an ambiguous word. Let's just agree that template-heavy "modern" C++ needs more optimizations turned on to get decent performance. So more optimizations => longer compiler times. (Not to even mention all of the parsing the headers multiple times, plus generating multiple versions of the code for all of the various type specializations!)
From the other replies, I feel like there's more to it than just optimizations though -- but as just a compiler-user, not a compiler-writer, I'm out of my depth and just reading tea leaves. :)
Reading those tea leaves, I'll be sadly surprised if the Go compiler ends up slow and happily surprised if a C++ compiler ever ends up as fast.
(I don't know enough about Rust to make any predictions. ;)
(PS. No disagreement that C++ has a higher performance ceiling than Go; of course hand-rolled asm still goes higher than that (ever tried running x264 w/o the assembly bits? it's painfully slow).)
Sort of. But it's also that you're making bad comparisons. C++ has an include based compilation model and heavy reliance on template specialisation that means it'll never be fast.
What you should instead be comparing it to is Java, which is also a simple language, only slightly more complex than Go. However, that comparison is rarely made, because it'd show that compiling fast is not so special a trick ... Java also compiles extremely fast at every level, that's why it's possible to use a JIT compiler with it at all.
Given that "compiles fast" is Go's number one claim to fame, the reluctance to compare to the most popular compiled language is the elephant in the room.
The only elephant in the room is the bloated, insecure platform sitting on many servers. Competition showed one could do much more with less CPU, memory, or money invested in tooling itself.
Few people are as consistently right in their field as Cliff Click is with JITs and language runtimes.
Yes, Pascal/Delphi also compiles very fast, it's true, but they also forbid circular dependencies and impose other restrictions that caused a lot of developer pain.
1. Interpreted vs compiled language.
2. Simple, Oberon-like type checks vs Rust or Ada.
3. Several pages of BNF in grammar vs 1 or 2.
4. Designed for abstract, heap machine or just above real, stack machine?
5. Number of steps needed between source and efficient exdcution.
6. Number of times you perform those steps (eg AOT vs JIT).
7. Cache-awareness of design.
These are a few key differences between Java and Wirth-style languages then. They made compiles rapid on P3. Updating to multicore or 64-bit would be trivial given each update at ETH was a few undergrads work for 6mo-2yr. So, do lessons learned that those attributes Wirth-style greatly aid performance of compilers and runtime still apply today?
I think so given what Go accomplished in its time and resources. Other languages too with design decisions that proved out over time. It took truly epic work and investment to get Java to its current situation.
I havent heard people say Pascal caused them lots of pain aside from functional crowd or some wanting a few C++ features. What specifics bothered you? And why did you need circular dependencies?
https://github.com/rust-lang/rfcs/blob/master/text/1298-incr...
Now, the only thing left is a real-time interpreter with live code updates. I recall the LISP box could do instant changes interpreted for exploratory stuff on running image. Solidify that super fast with per-function, typed compiles. Plus do whole program compiles if you had to. So yall getting close but what's odds of those other features happening?
Note: Live, interpreted image with save the world also makes it easier to debug stuff locslly and remotely. Send devs the whole, running state.
Personally, I would love to see this as part of an IDE that can execute _parts_ of a Rust file with various inputs to quickly see if a function behaves as expected (this could also be easily converted into test cases.)
Rapid development cycle doing features this way.
2) Since we are talking order of magnitude more time, Will optimized code from LLVM will be order of magnitude faster than Go?
It depends on the language. It would be interesting to see -O0 LLVM vs. 6g/8g on Go code.
> 2) Since we are talking order of magnitude more time, Will optimized code from LLVM will be order of magnitude faster than Go?
Maybe? If you vectorize it sure could be. But I don't see why it's relevant. Who cares if your final release builds for your browser are 10x slower if you're shipping them to 100 million users and they get a 3x speedup?
I guess you will agree business applications are far more commonly written than browser engines. For my business application in Java it is neither super fast to compile (~20sec from ant script). Quite slow to start due to VM startup time, and ok performance. I would really like if compile times are much faster.
I think it's a matter of tradeoffs. LLVM has multiple IRs on the way to machine code, some quite large, which let it emit pretty good output, on par with gcc. But other designs are possible that avoid a lot of that overhead, and can be far faster than LLVM, like JS VMs, B3 [1] and SubZero [2]. And clang is overall more or less comparable with gcc these days in terms of speed, it's no longer clearly faster [3] (although that also takes into account the frontend).
With all that said, I agree with you that making such a decision without talking to LLVM is a little silly. But, I doubt it would change the outcome: If Go wants fast compile times, has the resources to write its own compiler, and is ok with trading off throughput for compile time, then it's a reasonable decision to avoid LLVM.
[1] https://webkit.org/blog/5852/introducing-the-b3-jit-compiler...
[2] https://github.com/stichnot/subzero
[3] http://hubicka.blogspot.com/2016/03/building-libreoffice-wit...
[1] Well, OK, I'm not a fan of SelectionDAGISel's interpreter. But switching that to AOT won't result in huge differences in compile times. (Note that it's been a couple of years since I really worked with LLVM closely.)
Of course, some tradeoffs are made, but actually I don't see why they substantially limit B3's output code quality. Perhaps slightly, but in return for a massive speedup in compilation times.
But this proves the overall point: B3 is able to specifically say "we are going to be faster than LLVM because we are replacing RAUW with identities, packing multiple operands into an Inst, fusing operations into macro-ops, using arrays instead of linked lists, etc." Those are specific technical decisions that the WebKit authors believe will make things faster than LLVM, and they aren't based on misunderstandings of the things that LLVM provides.
Edit: That said, there's skepticism that B3's advantages will persist in the long term. See: https://news.ycombinator.com/item?id=11107082 and http://lists.llvm.org/pipermail/llvm-dev/2016-February/09546...
In theory, LLVM might support both a very fast compilation model and a slower and more efficient one. But supporting two complete codegen backends is a lot more effort.
And overall, codegen compilation speed has never been a priority for LLVM to anywhere near the extent that it is for JS VMs. It still doesn't have parallel codegen, while all JS VMs do. That shows the very different focuses on those projects.
Actually, it can be done. It's just not the default.
It's more "nobody has had the time to erase this particular technical debt yet". Chandler, for example, is focused on erasing the debt of the old pass manager first. The B3 guys, had they focused on doing this in llvm instead of writing a new JIT + new passes + .... probably could have done that in less time.
But at this point, there are concrete plans to erase it, so as you suggest, it is highly unlikely advantages will persist in the long term :)
The B3 JIT link describes things that LLVM plans on doing in the next year, precisely for these reasons, so ...
Had they emailed the list, ever, they would have known this.
It's not like these were design decisions that someone said "we should never change these", they were design decisions that were good at the time, but like anything else, need to grow and change over time.
If you give up and rewrite an entire jit/compiler every time it might require rearchitecting, that may be fun but it doesn't make a lot of progress. You will spend years to get to a no-regressions vs old compiler state (unless your old compiler was truly bad)
LLVM based toolchains compile hairy native code faster than any other tools i've seen... GCC, MS, Intel compilers for C/C++ are all very slow by comparison and the benefits are marginal (but still valuable).
for JIT or dynamic stuff LLVM is a poor fit. it doesn't surprise me that JS VMs do better with JS than LLVM, because there is no actual compilation involved as such - its a completely different class of problem, and its just not designed for that kind of language and environment, which is highly derivative, dynamically late binding and built in many layers, the vast majority of which are themselves compiled with C/C++ toolchains like Clang/LLVM, GCC or the MS compiler from necessity...
quoting that first article you link: "it isn’t specifically designed for the optimization challenges of dynamic languages like JavaScript."
[1] http://lists.llvm.org/pipermail/llvm-dev/2015-July/087832.ht...
DannyBee addressed most of these points, however I just wanted to note that even if LLVM didn't provide stack maps, it's easy to recover stack information using lazy pointer stacks [1]
[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.158....
This doesn't sound very exciting.
[0]: https://en.wikipedia.org/wiki/A-normal_form
SSA is fairly well studied, there are many algorithms to transform an IR into SSA and also lots of algorithms for optimizing programs in SSA form.
It doesn't matter how it's structured, just that it's faster.
It seems as though C-like imperative languages and x86 are baked in forever... but the world is actually parallel.
By analogy, of course, I am suggesting that the Church model of computation might have served us better as a foundation than the Turing model has done, since it seems that everything's turning up lambdas as the technology S-curve for silicon computers continues to flatten out.
It's a bit more thrilling to think of it that way, as a matter of scale. When space and time resources are scarce, thinking of the computer as a big piece of RAM that we mutate in-place makes the most sense. As we push upwards and outwards into enough resources and a bigger need for parallelism, it suddenly makes more sense to switch perspectives and reason in terms of binding and substitution.
You can see the same pattern with IO models. We have programming languages descended from 50s-era concepts of computing in which the program drives the machine, but that just isn't true at all. A computer is a passive machine, not an active one: it reacts when you poke it with an interrupt, until it reaches a steady state and settles down again. Operating systems go to a great deal of trouble to simulate the kind of top-down flow control environment our imperative tradition wants to think it is operating in, but in order to get any real performance out of these systems, we all end up building asynchronous, reactive layers on top of the simulated batch-job anyway.
We'd all be better off if we flipped the paradigm, imagining the process of building a program not in terms of writing instructions for the computer to perform, but in terms of creating a structure which will react appropriately in response to whichever events may be brought to its attention.
Instead, we'll probably still be starting young programmers out with for-loops counting from 1 to 10 and printing the result on an imaginary console for decades to come, even though none of that is even remotely relevant to what's actually happening anymore, and once they've crossed that hurdle they'll promptly begin unlearning all that stuff in order to start getting real work done.
On an unrelated note, I spent a while last fall/winter playing around with the idea of a very low level functional language - could we use these techniques in memory-constrained environments too? I didn't find the model I was looking for, but I think it's probably out there, and it would be very interesting to develop a functional/type-safe/immutable language suitable for microcontroller programming, with no garbage collection or implicit allocation. It may be that the Turing model is a better fit for computing in the small, but I suspect that we may find dataflow and functional composition to be useful at all scales. That way of looking at the world has some profound philosophical strength, after all - "you cannot step twice into the same river" and all that.
In contrast, the Church model doesn't really have any notion of time, so it's not clear how to reason about I/O. What evaluation order is used?
In terms of computation, they're of course equivalent, so you can execute the Church model on the Turing-like machines (or more specifically a Von Neumann architecture). So maybe that was the right "choice" (if there ever was one).
There was an entire movement around dataflow processors AND dataflow languages in the 80's, where the instruction sets were not totally ordered (e.g. SISAL was single assignment). But these didn't fare well in the market.
Closer to the ground, there is a pattern of "throwing away information at interfaces" in computing. Interfaces like x86, C, Unix, etc. get solidified by evolutionary forces. The cost of that modularity is global inefficiency.
Another good example of that is the Java code gen architecture. People say "static types in Java code let you generated better code!" Well, no. The Java compiler throws out all the type information, generating Java byte code, which is dynamically typed. Then the JIT takes the byte code and has to re-infer all the type invariants to generate machine code.
My understanding is that the dataflow architectures didn't fare well for technical reasons. The instruction-level parallelism they worked with turned out to be too fine-grained, i.e. the cost of scheduling was greater than the win of parallelism for many programs, especially normal sequential programs that still need to be fast. This led to research in coarse-grained dataflow, but it doesn't seem that much has come of that.
https://www.cs.ucf.edu/~dcm/Teaching/COT4810-Fall%202012/Lit...
Wait another month and a half and I'll be getting around to writing my blog post in support of VLIW, and why previous attempts have failed miserably.
Another problem with Mill is that they have been around for a little over 10 years, and have not released anything publicly (though have given a number of very detailed talks). They have had a lot of trouble getting their design into FPGAs, and even more trouble with having working compilers. When I started REX, I believed in getting it into silicon as fast as possible, as that is the point when people would take us seriously. We closed funding in July of 2015, and are taping out our first silicon next month... While many have called us crazy (and we will be giving real information on why we are not that crazy), I definitely don't want to be called vaporware.
At least for myself and my computer architecture friends/colleagues, most of us just throw Mill into the stack machine box even if it is not entirely true... the benefits of the Belt architecture over the traditional stack machine are there in concept, but Mill has also not released any real concrete information on their compilers (at least from what I have seen).
We'll have actual hardware development/evaluation kits available this fall, so feel free to contact us or sign up for our mailing list to be alerted when we release details on all of that. As I said in a previous post here, I strongly believe that most people do not care about something that they can not physically touch, so I expect that most developers would much rather start to learn about and work on an architecture that actually has silicon available.
I think one could read too much into the "single-assignment" part of SSA. Sure, functional languages don't tend to rebind variables either, but that's really all SSA has in common with them.
I'm familiar with Appel's "SSA is a functional language" article, but the vibe I got was more than he was trying to build some bridges between the SSA and CPS camps to try to get some cross-pollination going and knowldge sharing between them.
I think he could have just as easily called it "CPS is an imperative language", but my hunch is the FP folks are more persnickety and wouldn't have swallowed that as easily as imperative folks would accept the other title.
CPS is typically used to handle imperative control structures by impure functional programming languages, so it should indeed be of interest to imperative compiler authors.
Those compilers are at least 16 years old so Pike and Thompson aren't as incompetent as you think them to be.