Optimizing M3: Halving Our Metrics Ingestion Latency by Forking the Go Compiler
eng.uber.com
eng.uber.com
Of course I recommend this more as a last resort than the first thing you reach for, but it's a fantastic option to have in the arsenal, even if you don't reach for it often. I encourage people to at least consider it.
In fact, this is the reason that "Erlang/OTP" is a concept distinct from "Erlang." OTP is a distribution of Erlang, a "fork" that remixes together the core Erlang components in a certain way.
(Specifically, OTP is Ericsson's distro of Erlang targeted at building telecom switches. That means it contains not just regular language stdlib stuff, but libraries like "Megaco/H.248: a protocol for control of elements in a physically decomposed multimedia gateway".)
You're free to make your own distro of Erlang; it's extremely easy (and in fact, everyone is implicity doing it every time they use Erlang's release building process to build an app. An Erlang "release" is a customized, derivative Erlang distribution! You can build a new SDK with the release tooling just as easily as you can build an app runner.)
Even if it's rarely taken advantage of, it's clear that "forking your own Erlang distro and customizing it" is the idiomatic approach for many potential user stories. If you study the Erlang "kernel" library, you'll notice that there are many customizations which the kernel "expects" people to make, but not in the sense that there is any stable ABI grip-point to slot in a plugin via a configuration stanza. Rather, Erlang just has a trivial implementation of the logic in the kernel, sitting there in well-factored module. The kernel authors are expressing a clear intent by doing so: if you want some logic more fancy than this trivial version, just fork the kernel and plop in your own version of this module that does something else!
Personally, I love this way of thinking. Rather than the usual problems cropping up where something in the runtime that wasn't "quite right" for the application's use-case, was then reimplemented as a non-runtime-integrated library, with other warts and higher overhead as a result; instead, users are encouraged to just solve their problem in the runtime. Sometimes that results in upstreaming a patch, but that's not-at-all the goal. The goal is just to have software that has e.g. exactly one IO path, which everything uses.
(Side note: I find it mystifying that Ericsson's OTP release of Erlang is still considered by the community to be "the" Erlang SDK. It's as if Ubuntu was the only Debian-alike and there was no Debian, even though it's very clear exactly what Debian would look like. A "core" Erlang distro—with all the generally-useful OTP stuff like supervisors, but without the telecom-specific stuff—is totally possible; as is rebasing OTP to be a downstream distro of it. But nobody really seems to care about doing so.)
Of course, if it's a true one-off script or some personal hackery, go for it. But I wouldn't consider it a professional option.
(I find myself thinking more and more lately about how to program professionally in the long term, rather than simply solving the problem at hand.)
I agree wholeheartedly that the code in the standard library is very clean.
- Go initially allocates 2KB stack per routine. When it exceeds it it copies all of it into 2x the space.
- This was happening once or twice per request. They didn’t explain exactly why all that stack memory was being used (maybe someone can chime in), but contributing factors were a 30 function deep call stack and a minor code change that tipped it into the next stack growth tier.
- Also this doesn’t get freed up until garbage collection runs.
- They worked around it by implementing a kind of go routine pool that keeps assigning work to the same (stack-expanded) routines, staying ahead of the garbage collector.
My takeaways:
1. Fantastic analysis and job well done.
2. Pooling does not seem to be how things “should” work in Go. It’s more of a hack around undesirable allocator / garbage collector behavior.
3. I’m really interested in reference counted languages like Swift on the server for these reasons. I know ARC means more predictable latency when it comes to garbage collector behavior (which is only indirectly the problem here). Now I’m really curious how Swift allocates the stack and whether it would avoid this “morestack” growth penalty that Go has.
Look at gcc, it has tons, but it took years to get there.
Go has the added advantage of being able to learn off this knowledge
Nowhere, optimisations cost CPU time and the Go developers focus on compilation time. They could already have implemented plenty of well-known and well-understood optimisation passes in the 10 years since the initial release, that they didn't do so and restricted themselves to the sort of optimisation passes you'd find in a bytecode interpreter was by design.
In theory gccgo is where you'd get an optimising go compiler, but apparently even with gcc 8.1's improvements it has issues which lead to the end result being slower than the mainline compiler. I'm sure they'd be glad to get more people involved to resolve this.
> Look at gcc, it has tons, but it took years to get there.
> Go has the added advantage of being able to learn off this knowledge
Go could have used LLVM, they specifically refused to do so on grounds of compilation time being too slow, preferring to not optimise instead.
According to its documentation, dmd doesn't even do function inlining until you specifically opt into that with `-inline`.
OCaml has multiple implementations, it is a matter to choose the right one for the task at hand.
Delphi can make use of C++Builder's backend.
Eiffel uses its MELT VM for development, or compilation via C and C++ code generation, thus enjoying all their optimization capabilities.
D has three main implementations available, including GPGPU support on the ldc one.
.NET Native uses Visual C++'s C2 backend.
And I will thus restate my original assertion: in 3-5 Go (the mainline compiler) will be nowhere in terms of optimisations. If you want an optimising Go compiler, work on and help with gccgo.
[0] whose maintainers simply don't care for advanced optimisations at the cost of compilation speed
Go's community approach seems to keep being "you are holding it wrong", disregarding experience from other language communities.
What's interesting about Swift on the server is that the super lightweight runtime and lack of a tracing garbage collector hold the potential of much more consistent latency with low memory overhead. And as for reference counting overhead, application-level code is much more likely to be able to take advantage of Swift's preferred functional-esque "value type semantics", which don't suffer from that.
[1] https://news.ycombinator.com/item?id=18788069
[2] https://developers.slashdot.org/story/17/01/23/085232/slashd...
[1] https://dsheets.github.io/codoc/cstruct.1.5.0/_build/lib/cst...
It's a mistake to extrapolate too much about the "reference counting vs tracing GC" question from this one low-level driver benchmark. In fact reading their paper, they don't understand why Swift ARC traffic was so high.[1] They weren't allocating a lot of objects or copying. It's probably just an unoptimized use case or bug, not something fundamental in the memory management model. Swift is still quite young.
[1] https://github.com/ixy-languages/ixy.swift/blob/master/perfo...
The fact that the language designers switched to tracing GC on their further work, namely Modula-2+ and Modula-3. Or that Wirth after his 2nd sabbatical year at Xerox PARC decided for tracing GC on his system programming languages, Finally Microsoft own research, also using tracing GCs.
All in all quite telling, where they seen performance gains to be held.
Swift's approach makes sense from Objective-C compatibility point of view. Which also made sense given the failure to add a tracing GC while keeping the underlying C semantics.
From performance point of view not so much.
Having a tracing GC doesn't remove the possibility to have stack allocations, even when they look like heap ones, implement pools or whatever.
Unfortunately Java's approach of not having the same type system as older GC enabled systems programming languages created a bad picture of what is actually available out there.
Look, tracing GC has come a long way. I’m not saying it’s unsuitable for servers at all. I’m just excited to see what sidestepping its problems entirely can do for server apps, especially with respect to tail latency and energy efficiency, increasingly salient metrics for services at scale.
You typically either use Grand Central Dispatch, or directly make OS calls to create threads. In either case, you get way larger stack sizes, 512kB for secondary threads by default (https://developer.apple.com/library/archive/documentation/Co...)
Also, AFAIK, those stacks never grow. If you try to grow a thread’s stack too much, it’s end of game (for that thread, I think, but possibly even for the application)
Go’s smaller stacks allow for way more goroutines to exist in parallel, but as this article shows, if go has to grow a stack, things slow down.
I don't think you can do that, but I think you'd just create a bigger stack when spawning your process / thread: the stack allocation is virtual (at least on unices, possibly not on Windows?) so on a 64b system it's unlikely to be very expensive, physical pages will get allocated on-demand as stack use increases.
This could probably be tested / benched using pthread: pthread_attr_setstacksize lets you define the (virtual) stack size before spawning the process.
Go Can’t do that because it is designed for allowing to run thousands of short-lived threads, even on 32-bit systems.
The Swift people are smart and maybe they have a plan to mitigate this but I don't know what it might be.
I’m not yet convinced by Swift the language, but I think it’s positioned in just the right place.
I would say Swift is easier to learn/use than Rust while aiming to deliver some of the same performance characteristics. At least that's the sweet spot it's shooting for on the server.
On throughput, two things:
- Reference counting only applies object references. It does not apply to value types, and Swift is very strong on the "value semantics" approach to coding. It's like a sensible incorporation of some functional programming concepts without getting dogmatic about it. I'm not sure exactly how this will work out on the server but it seems very promising from a performance and thread safety standpoint.
- Even when we consider throughput burdened by ARC, latency is probably more important of a metric than throughput for a whole lot of services. Throughput is sort of the knee-jerk metric which I feel is a holdover from desktop benchmarking days. For services at scale, p99 latency is where you get the real headaches. And that's one area where ARC is especially good.
If we accept that pooling is necessary in some cases, I'm curious – is there a common source that these applications use?
In trying to answer my own question, I found that M3 has a mature-looking implementation of such an abstract solution. https://github.com/m3db/m3/tree/master/src/x/sync.
Elsewhere, I couldn't find anything similar in the usual suspects. CockroachDB has one-off, specific implementations in the places where they've decided pooling is worth it. Looks like Kubernetes uses the stdlib's `sync.Pool` interface in a similar way, but doesn't use a full-fledged "routine pool".
Do people at Uber think this is a robust enough solution to be used outside of m3? Seems like it might be useful in the stdlib as an implementation of `sync.Pool` :)
all over our code base so its definitely stable enough to use in your own projects if you have a need, although it does require some tuning.
My guess is that the Go team would not consider this critical / core enough to include in the standard library and I'd be inclined to agree with them.
I'd agree that it probably doesn't belong in the stdlib, as there aren't many programs that would really benefit from it. OTOH, it's good one to keep in pocket, for the few applications that would.
I believe they'd prefer to improve the runtime's internal stack allocation algorithm, while keeping it opaque to the average developer. The proposal mentioned elsewhere in this thread, to re-use allocated routines "under the covers" is an example in that direction.
Until they implement something like that (essentially, routine-pooling) in the runtime, these apps will just have to use routine pooling at the application level – which I suppose isn't that bad, after all?
var dontOptimizeMeBro byte
// go:noinline
func makeStackBig() {
var buf [16386]byte
dontOptimizeMeBro = buf[0] + buf[len(buf)-1]
}
What it does, I hope, is extend stack to 16kb, once (as opposed to going from 2kb to 4kb then to 8kb then to 16kb and paying for coyping the memory multiple times).
The stack stays big for the remaining lifetime of the goroutine.
(By the way, Rust used to cache thread stacks back when it had M:N threading, because we found that situations like this arose a lot.)
The idea that generational GC would not be a win does not match the experience of any other language. Generational GC is virtually always a win for languages like Go. This is just another reason why Go should adopt it.
I guess for the runtime it is more expensive to copy the stack contents (so nearly 2K) and e.g. update pointers in it (a simple memcpy might not be enough).
"it looked like the goroutine stack was growing from 4 kibibytes to 8 kibibytes"
The article is very good in providing ideas and tools you can try to use whenever you find yourself in a similar situation.