Hacker News Reader

Comment by tomp | Hacker News Reader

It's answered in the post:

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.

View on HN

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

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.

[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...

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.)

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.

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...

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.

" It still doesn't have parallel codegen, while all JS VMs do."

Actually, it can be done. It's just not the default.

"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)

FYI a new instruction selector is in development to replace SDAG.

That's great news. LLVM keeps getting better and better :)

Do you have more information about that effort?

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.

really?

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).

[1] http://lists.llvm.org/pipermail/llvm-dev/2015-July/087832.ht...

You say it is arrogant but is it untrue? Rust uses LLVM backend and it takes order of magnitude longer to compile compare to Go.

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.

Well, Go still won't be paying for (a) right?

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 appreciate the detailed replies!

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.

HotSpot's sea of nodes IR is far beyond anything Turbo Pascal did in terms of balancing compile time and runtime. It's not even comparable.

Few people are as consistently right in their field as Cliff Click is with JITs and language runtimes.

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.

Yes, and they didn't do any optimization. That's not particularly interesting; TCC is there if you want it.

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.

It's recompiling only the functions that have changed. The code to build and persist the dependency graph has already landed.

https://github.com/rust-lang/rfcs/blob/master/text/1298-incr...

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.

Rapid development cycle doing features this way.

1)-O0 code from LLVM will run faster than 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?

> 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?

True for browser.

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.

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.

Not Invented Here is a powerful thing.

Is "Stack maps" the same as "segmented stacks" that Mr Cox refers to?

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.

Note that Go no longer uses segmented stacks (and hasn't since 1.2). It uses contiguous, copyable stacks: http://agis.io/2014/03/25/contiguous-stacks-in-go.html

Segmented stacks are basically what safestack offers, and that is also something llvm does :)

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.

> - 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]

[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.158....

sorry i missed your reply at the time, but DannyBee's comment is very close to what i would have said in response thankfully. :)

Reply on news.ycombinator.com