Building a Better Go Linker
golang.org
golang.org
Books: Queen and Pawn Against Queen, Roycroft's 5-man Chess Endgame Series
Awards: Turing Award, National Medal of Technology and Innovation, Japan Prize
If anything, OCX is an example of how not to do shared libraries.
And how can it be that a binary called "cmd/compile" has 170k symbols (that's like, global definitions, right?). Not that that's a huge number in terms of today's computing power, but how many millions of lines of source code does that correspond to?
Still, 1M relocations, or 34MB of "Reloc" objects, as indicated, shouldn't be a huge issue to process. Object files should have minimal parsing overhead. Is there any indication how long this takes to link? Shouldn't 1 or 2 secs be sufficient? (assuming 100s of MB/s for sequential disk read/write, and < 1us to store each of the 170k symbols in a hashmap, and < 1us to to look up each of the 1M of relocations).
- I don't think mmap should be used if it can be avoided. It means giving up control over what parts of the file are loaded in memory. And from a semantic point of view, that memory region still must be treated differently, since on-disk and in-memory data structures are not the same.
No, not just global definitions. Closures need linking, too. But the linker is doing much more than linking function entry points. Many automatic (on the stack) variables need linking so the GC can (a) trace the object graph and (b) move them when resizing the stack. Likewise, type definitions require metadata generation for GC tracing. And then there's all the debugging data that needs to be generated, which basically involves everything.
As far as stack variables for the GC, the stack is exactly scanned for all but the last frame (I believe), but conservatively scanned for the last frame. This makes it much easier.
Types -- you're partially right. It is mostly all generated in the compiler, and deduped by the linker.
There's no reason Go's linker couldn't be much simpler and likely even simpler than a standard C linker. You might argue that Go will give up things like LTO, but Go designs out lots of the LTO problem (not PGO) by nature of how packages work, and the fact that there aren't cyclic dependencies.
Overall, the Go linker could be quite simple. It just needs some rework is all. :)
[I've implemented a Scheme before, in C, for context, so I'm wondering if I'm reading what you wrote with common vocabulary.]
In Go the linker also generates DWARF, does deadcode elimination and a bunch of other stuff described in the associated document.
> And how can it be that a binary called "cmd/compile" has 170k symbols (that's like, global definitions, right?). Not that that's a huge number in terms of today's computing power, but how many millions of lines of source code does that correspond to?
As described in the link each global function actually ends up producing 4 symbols.
> Shouldn't 1 or 2 secs be sufficient?
On my system linking cmd/compile takes 1.3 seconds. The problem is that object files get cached so if you have a hot cache (let's say you made a few changes inside a single package and then recompile) compiling takes almost no time and linking accounts for nearly 100% of the build time.
This of course only makes sense for development where the object files are still available for GDB to load the debug symbols from but it is a nice feature.
The MSVC linker has /DEBUG:FASTLINK as well.
Even if it doesn’t do that, fixing up various addresses can be a lot of work if the linker can make code shorter (e.g. by using short branches where possible), or if it tries to increase cache locality by changing function order.
What a great unit of measure :)
[1] Array of opcodes indexed with a program counter (pc) with a giant switch statement for executing each opcode. A simple stack for data implemented as an array and a stack pointer/index (sp). There are plenty of examples online, just make sure you actually implement things yourself, and only go to the examples to answer questions you arrive at yourself. If you understand loops and arrays implementing the VM is trivial. If you can parse a text file line-by-line and split words, implementing the assembler is trivial. Working out the linking might take some thinking, but that's the point. It's like one night of work, max, unless you really get sucked in ;)
[2] E.g. Harvard architecture vs. von Neumann architecture
I think there would be a market for a proprietary compiler and maybe an IDE to go with it — if the performance was better than the open source one. I think this is achievable because as good as Go's performance is now, there's still a lot of headroom. Google isn't exploiting modern CPUs very well, and the linker is not doing extensive LTO.
The biggest constraint is the blazing fast compile times. A compiler and toolchain that was able to take some time for optimization might deliver markedly better runtime performance.
There may be a market but not large enough to pay few top notch compiler/low level system software hacker. I only know of a commercial Go IDE and constant refrain there is how will a poor third world developer afford it. Though I feel real issue is developers are raised on diet of free software feels entitled to it. Paying for good software seems alien to them.
Maybe gocc?
It's a thing that exists, not a proposal.
I thought it was just spitballing an alternative name.
It's only when you want to share code with other implementations that software licensing enters the picture. Gccgo manages to share most of the standard library with the golang.org implementation, so they appear to have the licensing figured out.
So I was saying (mostly tongue-in-cheek) that it probably wouldn't be appropriate.
Sorry for the confusion, and I appreciate the clarification here too. :)
In many ways Go seems like an excuse for Google to fund the continued development of Plan 9. Three of the five most influential people on the Go team (Ken Thompson, Rob Pike, and Russ Cox) were heavily involved in Plan 9. And it shows. Go's toolchain is a direct descendant of the Plan 9 toolchain; in fact, the Go language is really just an evolution of the special C dialect that Plan 9 used [1]. Indeed, for a while, the Go compiler was written in this special dialect of C, and so building Go required building a C compiler (!) that could compile this custom dialect of C, and using that to compile the Go compiler [2].
By all rights, Plan 9 was an interesting research project, and seems well loved by those familiar with it. (I'm not personally familiar; it was well before my time.) But it never took off. What we ended up with is Linux, macOS, and Windows.
Go very much wants to be Plan 9. Sure, it's not a full-fledged operating system. But it's a linker, assembler, compiler, binutils, and scheduler. All it asks of the host system is memory management, networking, and filesystem support, and it will happily replace your system's DNS resolution with a pure Go version if you ask it to [3]. I wouldn't be surprised if Go ships its own TCP/IP stack someday [4].
This is, in my opinion, craziness. What other language ships its own assembler?! [5] To make matters worse, the assembly syntax is largely undocumented, and what is documented are the strange, unnecessary quirks, like
> Instructions, registers, and assembler directives are always in UPPER CASE to remind you that assembly programming is a fraught endeavor. (Exception: the g register renaming on ARM.)
> In the general case, the frame size is followed by an argument size, separated by a minus sign. (It's not a subtraction, just idiosyncratic syntax.)
> In Go object files and binaries, the full name of a symbol is the package path followed by a period and the symbol name: fmt.Printf or math/rand.Int. Because the assembler's parser treats period and slash as punctuation, those strings cannot be used directly as identifier names. Instead, the assembler allows the middle dot character U+00B7 and the division slash U+2215 in identifiers and rewrites them to plain period and slash.
The excuse for the custom toolchain has always been twofold, that a) LLVM is too slow, and fast compiles are one of Go's main features, and b) that the core team was too unfamiliar with GCC/LLVM, at least in the early days, and attempting to build Go on top of LLVM would have slowed the speed of innovation to a degree that Go might not exist [6].
I've always been skeptical of argument (b). After all, one of Go's creators literally won a Turing award, as this document not-so-subtly mentions. I'm quite sure they could have figured out how to build an LLVM frontend, given the desire. Rust, for example, is quite a bit more complicated than Go, and Mozilla's developers have had no trouble integrating with LLVM. I suspect the real reason was that hacking on the Plan 9 toolchain was more fun and more familiar—which is a very valid personal reason to work on something! But it doesn't mean it was the right strategic decision.
I will say that (a) is valid. I recently switched from writing Go to writing Rust, and I miss the compile times of Go desperately.
That said—and this is what I can't get past—the state of compilers would be much better off if the folks on the Go team had invested more in improving the compile and link times of LLVM or GCC. Every improvement to lld wouldn't just speed up compiles for Go; it would speed up compiles for C, C++, Swift, Rust, Fortran, Kotlin, and anything else with an LLVM frontend.
In the last year or so, the gollvm project [7] (which is exactly what you'd expect–a Go frontend for LLVM) has seen some very active development, and I'm following along excitedly. Unfortunately I still can't quite tell whether it's Than McIntosh's 20% time project or an actual staffed project of Google's, albeit a small time one. (There are really only two committers, Than and Cherry Zhang.) There are so many optimizations that will likely never be added to gc, like a register-based calling convention [8] and autovectorization, that you essentially get for "free" (i.e., with a bit of plumbing from the frontend) with a mature toolchain like LLVM.
There are not many folks who have the knowledge and expertise to work on compilers and linkers these days, and those that do can command high salaries. Google is in the luxurious position of being able to afford many dozens of these people. I just wish that someone with the power to effect change at Google would realize that the priorities are backwards. gccgo/gollvm are where the primary investment should be occurring, and the gc toolchain should be a side project that makes debug builds fast... not the production compiler, where the quality of the object code is the primary objective.
[0]: https://dave.cheney.net/2013/10/15/how-does-the-go-build-com...
[1]: http://doc.cat-v.org/plan_9/programming/c_programming_in_pla...
[2]: https://docs.google.com/document/d/1P3BLR31VA8cvLJLfMibSuTdw...
[3]: https://golang.org/pkg/net/
[4]: https://github.com/google/netstack
[5]: https://golang.org/doc/asm
[6]: https://golang.org/doc/faq#What_compiler_technology_is_used_...
It never would have happened. How do you motivate people whose principal frustration is the state of C++ to work on a large C++ codebase?
Heterogeneity is a huge benefit to any ecosystem. Improving existing things is great, but building new things is also very important. Go would simply not exist today if it were built on LLVM or GCC.
I agree that enthusiasm is important! And indeed, for the Go creators, their particular leanings might have been such that they couldn't get excited about building an LLVM/GCC frontend, and adapting the Plan 9 toolchain is literally the only way those three could have Go gotten off the ground. As a member of the Go team, you'd certainly know better than I.
But Go is long past a personal passion project. Go is over ten years old. Go likely has over a million developers [0]. Go 1.0 has been stable for about seven years, and the first meaningful changes to the language are just now being talked about. In my opinion, it is several years past due for Google to start investing seriously in a Go toolchain based on a mature compiler stack.
I realize the audacity of this claim and I don't make it lightly. But if I had the money to spend on a team of developers, I would spend it making llvm-as and lld fast enough and stable enough to be Go's assembler and linker, and abandon the custom Plan 9 ones.
> It never would have happened. How do you motivate people whose principal frustration is the state of C++ to work on a large C++ codebase?
Well, for one, once the language gets off the ground, you can write the frontend in the new language. Rustc manages to be almost entirely Rust, for example.
> Heterogeneity is a huge benefit to any ecosystem. Improving existing things is great, but building new things is also very important.
I agree, and I think Go is an interesting contribution to the P/L landscape—essentially it proved that stripping away a good deal of complexity (generics, inheritance, etc.) results in a very useful, highly productive language. But I don't think Go's custom assembler and linker are meaningfully contributing to the ecosystem. They're useful presently in that they improve Go developers' productivity with ultra-fast builds, but they're not suitable for use by anything but Go. Improvements to Go's linker and assembler benefit only Go. Improvements to lld or gold can benefit practically everyone using a compiled language.
That's a bit presumptuous, prescribing specific implementation details based on the fact that it's "several years past due" that they replace their tech stack with one you would like to see improved.
Remember there already is a mature C compiler alternative for Go: gccgo. There's also already a first-party LLVM based Go toolchain created by Google (gollvm). Whatever hypothetical benefits you might presume would emerge from this kind of synergy already exist. But the community mostly isn't interested.
Also, Google also already invests a massive amount of resource into LLVM. In fact, the principal author of LLVM and Clang works at Google. But even when he was at Apple they were already shoveling resource into the project.
I suspect the community is uninterested because it’s hard to be interested in compilers that a) compile slower than gc, and b) produce slower code than gc. That's a worse compiler on all fronts!
For gccgo or gollvm to be useful, they need to provide some benefit. I suspect we'll see (b) fixed within a year. GCC/LLVM have far more optimizations than gc, and so it's mostly a matter of plumbing enough information from the Go frontend into the LLVM optimizer to unleash its full power.
I don't expect we'll see (a) fixed, unless something changes at Google.
> Also, Google also already invests a massive amount of resource into LLVM. In fact, the principal author of LLVM and Clang works at Google. But even when he was at Apple they were already shoveling resource into the project.
Yes, but Chris Lattner is not actively working on speeding up LLVM. His big project lately has been supporting TensorFlow via MLIR.
> Improvements to lld or gold can benefit practically everyone using a compiled language.
I do not see how a generic framework could be made as fast as custom build stack.
Sorry, but I think you’re still missing my point. It’s well documented that the original creators of Go did not want to build their language on top of LLVM, and did not like C++. That’s totally fine! Of course you have to work on things you like.
But Go is so stable, and has been for more than half a decade. That means Google could spin up a brand new team, entirely separate if they must, of folks who like both LLVM and Go, to build out an LLVM frontend for Go. It’s not like Go is a fast-moving target. There is a very stable spec.
Gccgo is proof that it is possible to have a GCC frontend for Go without too much work. Ian Taylor has been maintaining Gccgo for about ten years, working what seems to be half time. Imagine what could be done if there were a few more folks actively working on improving gccgo, rather than just keeping parity with gc.
> I do not see how a generic framework could be made as fast as custom build stack.
I don’t see why not. It’s mostly a matter of introducing ways of disabling the expensive bits when compiling/linking a simpler language like Go. Yes, it’s probably somewhat slower to develop, but everyone benefits from the work, and you also offload much of the burden of maintaining a compiler/linker for a half dozen different platforms to the LLVM team collectively.
Yeah the creators of go didn't come to praise C++ but to bury it. To kill C++ you need first to knock out gcc and LLVM.
As enneff alludes, Ken Thompson's antipathy towards C++ is well documented: https://bryanpendleton.blogspot.com/2009/12/coders-at-work-k...
Right, you need to specifically throw money and people at the problem of making LLVM faster, not just at LLVM in general. Neither Swift nor Objective-C have "fast compiles" as part of their pitch. Much of the work on LLVM goes into producing the highest quality object code possible, which is a goal often at odds with compiling quickly, and part of the reason the choose-your-optimization-level flag (-O) exists, though -O0 compiles are still not fast enough.
> In hindsight the Go team made the right call to use their own toolchain.
No, we don't have the benefit of hindsight yet. We don't know what could have been if the resources that had been spent on the Go toolchain had been spent on LLVM instead.
If five highly-qualified engineers spent five years trying to speed up gollvm compiles without success, we'd have strong evidence that something about LLVM prohibits the fast compiles that are possible with the gc toolchain. But that's not the situation.
I bet they've designed and executed on more programming languages than you have :)
I see a trend here.
And yet hundreds of thousands of working programmers around the world are productively using Go while still continuing to ignore the supposedly superior solutions.
Hundreds of developers used Basic, Pascal, C, Modula-2, Assembly, Forth productively.
Maybe we should have kept using them, instead of coming up with programming languages that require a PhD. /s
Here's another fallacy for you: false dilemma.
At some point people are going to need to put the money where their mouth is. Or they can live with the software which open source developers developed on their own or employers' dime.
I did learn enough in those six weeks to feel comfortable asserting that there is incredible potential in gccgo/gollvm, and that I think Google is making a mistake by continuing to invest so heavily in the gc toolchain.
[0]: http://meltware.com/2019/01/16/gccgo-benchmarks-2019.html
I don't intend this to sound harsh, apologies if it does. I strongly recommend you introspect on your own confidence and experience levels. I've mentored a lot of junior engineers with similar viewpoints and often there's a lot of hidden complexity they simply lack the experience to understand.
This isn't to say you should take everything anyone with more experience says at blind faith, simply that dismissing without understanding is counter to a growth mentality.
In short, the reasons gccgo produces worse code than gc are the result of fairly basic optimizations that are/were missing. For example, open-coding string slicing [0] and string equality [1] is enough to close the gap in the TimeParse benchmark in the blog post above. In fact, with those changes, gccgo actually produces better code than gc, because the full power of GCC can be unleashed on the IR, and GCC has more aggressive optimizations than gc.
> This isn't to say you should take everything anyone with more experience says at blind faith, simply that dismissing without understanding is counter to a growth mentality.
Quite honestly, I think you're more guilty of dismissing without understanding than I am. It's true that I haven't been programming for decades, but I've spent two years dealing with the Go toolchain's shortcomings on a large Go project, and six weeks specifically on a passion project to improve gccgo. Of course it's possible that I'm wrong! But I've spent a while thinking about it, and often just as relevant as experience is a fresh, outside perspective. It's easy for a team to get stuck in tunnel vision or groupthink.
[0]: https://github.com/golang/gofrontend/commit/62e3a8cc0a862b0a... [1]: https://github.com/golang/gofrontend/commit/89b442a0100286ee...
I repeat, Apple is the major sponsor of LLVM and is sitting on ~$250 billion in cash. If LLVM could be made significantly faster by simply throwing money at it, presumably this has also occurred to Apple management. I can't believe they're not doing it because it doesn't align with their marketing pitch.
That is different from a belief that making LLVM better is worth management's attention or a slice of Apple's budget once it proved a satisfactory replacement for GCC.
The kinds of optimizations LLVM does is way beyond anything golang does. Golang doesn't even optimize passing function parameters in registers, let alone the advanced optimization techniques LLVM and GCC do.
As far as I'm aware, one major reason why Go reinvented so much was to save time and effort. They did whatever they could in order to bootstrap fast and efficiently, and they did so by cannibalizing Plan 9's toolchain, including the compiler and assembly language. The original "gc" toolchain (with inscrutable binary names like "6g" and "6a"), was written in C and came directly from Inferno. You can browse the original commit here [2]. That stuff has all been rewritten in Go.
A key attribute I and others have noticed about highly productive developers is that they tend to build an effective toolchain around themselves and bring it with them for new projects. Sometimes that stuff can become legacy baggage, but there's no denying that it's a good strategy.
Perhaps LLVM or GCC would also have been a good strategy. There are some arguments to the contrary. 11 years ago, when Go was started, LLVM wasn't nearly as mature as today. But look at the hurdles other projects like Rust have had to get over with LLVM. And a large part of Rust's compilation speed is apparently due to LLVM. So LLVM is not a magic bullet. Migrating Go today to LLVM would of course be a big, time-consuming zero-velocity project; you'd want to be really certain that the payoff would be worth the effort.
GCC is not an easy project to deal with, either. For decades, its internal intermediate representation was undocumented and intentionally obfuscated [2] to ensure FSF/GNU control over backends.
I do agree that Go has a certain bias towards a particular, idiosynchratic way of doing things, which is not always a positive.
I don't mean to imply that there's a conspiracy here. What I mean is that I think the Plan 9 heritage is clouding strategic decisions around the Go toolchain. What may have been the right decision to get a new language off the ground is not necessarily the right decision once the language is widely popular and stable.
> Migrating Go today to LLVM would of course be a big, time-consuming zero-velocity project; you'd want to be really certain that the payoff would be worth the effort.
A big project, yes, but it's happening! [3] If a few engineers working on gollvm for a year or two could improve gollvm to the point that it made the average Go program run 20% faster, I'd think that would absolutely be worth it to Google.
> GCC is not an easy project to deal with, either. For decades, its internal intermediate representation was undocumented and intentionally obfuscated to ensure FSF/GNU control over backends.
Very true in general, but the Go team has been lucky in that GCC core maintainer Ian Taylor has been a member since the early days. Gccgo has been a spec-conformant Go compiler since 2012 [2], and so nearly all of the GCC-integration bits have been in place for seven years. As a result, it's far more a matter of staffing the project so that the Go frontend's inliner, garbage collector, and escape analysis can reach parity with gc, rather than dealing with GCC/FSF politics.
> You can browse the original commit here. That stuff has all been rewritten in Go.
Yeah, I'm familiar with the lineage. I don't know that I'd say that it's been rewritten in Go, though, as the toolchain and runtime were converted fairly automatically with a "c2go" tool that Russ Cox wrote [0] around the Go 1.5 release. Have you looked at the resulting code much? Some of it has been rewritten to be idiomatic Go, but a lot of it is still very clearly C code that has been automatically translated [1]. See also the fact that go/src/runtime/runtime.go, go/src/runtime/runtime1.go, and go/src/runtime/runtime2.go all exist—a consequence of the fact that runtime.go, runtime.c, and runtime.h all existed in Go 1.4 [2].
[0]: https://github.com/rsc/c2go
[1]: https://github.com/golang/go/blob/7b294cdd8df0a9523010f6ffc8...
> There are so many optimizations that will likely never be added to gc, like a register-based calling convention.
The calling conventions was marked as undefined as a first step to changing it [1]. The change was introduced by the very author of this post.
Also, a more agressive inlining mitigates the slow calling conventions.
More generally, I think it is a huge achievement for a PL to be self hosting. It makes its development easier as there is only one language to deeply know (plus assembly of course).
I don't think that's true. The build process used GCC to compile the Go and C compilers. The Plan-9-derived C compiler was used for compiling those parts of the runtime that were written in C back then and were supposed to follow the conventions of Go program code.
As you can tell from Inferno (or even Plan 9 from userspace), GCC can compile the Plan 9 C dialect, given the right options.
> What other language ships its own assembler?!
The majority of native code compilers I have seen include their own assembler. Many of them don't have a textual input format, but they are assemblers nonetheless.
This goal is entirely at odds with an unsafe, legacy-ridden C/C++ toolchain.
The Solaris port never used raw system calls.
The MacOS port doesn't use raw system calls since go 1.11.
The remaining ports for Linux/BSDs/Plan 9 have a stable syscall interface.
;)
Maybe some of it can be fixed with a lot of engineering effort, but the fact remains that it is a bad idea to redo so much work every time.
Maybe the people who invented shared libraries had a point after all.
Of course the real problem is software and dependency bloat, but that is unlikely to ever get fixed.
Worse, this needs to happen at every executable invokation.