71 ms·
Generics can make your Go code slower
- ctvo 5y agoBravo on the informative content and presentation. That component that shows the assembly next to syntax highlighted code? chefs kiss
- lokar 5y agoIt seems like the code size vs speed trade-off would be well managed by FDO.
- maxekman 5y agoSimilar to how the GC has become faster and faster with each version, we can expect the generics implementation to be too. I wouldn’t pay much attention to conclusions about performance from the initial release of the feature. The Go team is quiet open with their approach.
- trey-jones 5y agoThis is a really long and informative article, but I would propose a change to the title here, since "Generics can make your Go code slower" seems like the expected outcome, where the conclusion of the article leans more towards "Generics don't always make your code slower", as well as enumerating some good ways to use generics, as well as some anti-patterns.
- deleted 5y ago[deleted]
- Ensorceled 5y agoInterestingly the original title and your proposed title imply, to me, the opposite of what I think they imply to you. This suggestion is really unclear.
- SomeCallMeTim 5y agoIn C++, generics (templates) are zero-cost abstractions. So no, generics do not de facto make code slower.
- gmfawcett 5y agoThat's only 99% of the story. :) Having too many specializations of a C++ template can lead to code bloat, which can degrade cache locality, which can degrade performance.
- pjmlp 5y agoDepends if LTO is used.
- mcronce 5y agoYou're definitely right. While it's not a particularly common problem, it does exist; one thing I'd really like to see enter the compiler world is an optimization step to use vtable dispatch (or something akin to Rust's enum_dispatch, since all concrete types should be knowable at compile time) in these cases. I expect it would require a fair amount of tuning to become useful, but could be based on something analogous to the function inliner's cost model, along with number of calls per type. Could possibly be most useful as a PGO type step, where real-world call frequency with each concrete type is considered.
- nu11ptr 5y agoenum dispatch in Rust is one of my favorite tricks. Most of the time you have a limited number of implementations, and enum dispatch is often more performant and even less limiting (than say trait objects)
- mcronce 5y agoI'm a huge fan. It's very little work to use, as long as all variants can be known to the author, and as long as you aren't in a situation where uncommon variants drastically inflate the size of your common variants, it's a performance win, often a big one, compared to a boxed trait object. Even when you have to box a variant to avoid inflating the size of the whole enum, that's still an improvement over a `dyn Trait` - it involves half as much pointer chasing It'd be cool to see this added as a compiler optimization - even for cases where the author of an interface can't possibly know all variants (e.g. you have a `pub fn` that accepts a `&dyn MyTrait`), the compiler can
- addcninblue 5y agoIs it the expected outcome? I was under the initial impression that the author also noted: > Overall, this may have been a bit of a disappointment to those who expected to use Generics as a powerful option to optimize Go code, as it is done in other systems languages. where the implementation would smartly inline code and have performance no worse than doing so manually. I quite appreciated the call to attention that there's a nonobvious embedded footgun. (As a side note, this design choice is quite interesting, and I appreciate the author diving into their breakdown and thoughts on it!)
- kubb 5y agoReading the title I'm worried, should I keep using reflection instead?
- AYBABTME 5y agoUse generics if it makes your dev experience better. Profile if it's slow. Optimize the slow bits.
- LanceH 5y agoIf you're worried you should benchmark the differences on your requirements.
- morelisp 5y agoIf you're using reflection or storing a bare interface{}, you should probably instead try using generics. If you're using real interfaces, you should keep using interfaces. If you care about performance, you should not try to write Java-Streams / FP-like code in a language with no JIT and a non-generational non-compacting GC.
- linkdd 5y agoPremature optimization is a bad thing. Just implement naively, then if you have performance issues identify the bottleneck.
- morelisp 5y agoIgnorance of how your language works is a bad thing. Knowing where performance issues with certain techniques might arise is not premature optimization. Implement with an appropriate level of care, including performance concerns. Not every kind of poor performance appears as a clear spike in a call graph, and even fewer can be fixed without changing any external API.
- 8note 5y agoThe language is a tool for a job. If I'm using low torque, I don't need to know the yield strength of my wrench
- brundolf 5y agoThis is super interesting and well-written. Also, wow, that generated-assembly-viewer widget is slick.
- morelisp 5y ago> there’s no incentive to convert a pure function that takes an interface to use Generics in 1.18. Good. I saw a lot of people suggesting in late 2021 that you could use generics as some kind of `#pragma force-devirtualization`, and that would be awful if it became common.
- mcronce 5y agoWhy would that be awful?
- morelisp 5y agoFirst, because `[R io.Reader]` is an awful way to spell "force devirtualization". It's not explicit about what it means, and it's not derivable from first principles like Go's other odd spellings, e.g. `interface{}` or `var _ Reader = T{}`, are. Second, it doesn't really promise to devirtualize it. If what I have is a variable of type `io.ReadCloser` - not just implementing it, but already boxed - it's not going to be able to unbox it for me. Third, if that was all or even primarily what we wanted out of generics it would've been much better to spend the past two years hacking on the inliner and other parts of the compiler to improve devirtualization. I don't think it would be awful to fix the unncessary pointer indirection (which looks like it's already happened), but I don't want 10x or even 2x longer compile times just because someone is trying to get the compiler to avoid boxing. It's a tradeoff, vs. e.g. spending that time simplifying methods to get the inliner to approve of them, which is win/win.
- eatonphil 5y agoKey tldr from me: > Ah well. Overall, this may have been a bit of a disappointment to those who expected to use Generics as a powerful option to optimize Go code, as it is done in other systems languages. We have learned (I hope!) a lot of interesting details about the way the Go compiler deals with Generics. Unfortunately, we have also learned that the implementation shipped in 1.18, more often than not, makes Generic code slower than whatever it was replacing. But as we’ve seen in several examples, it needn’t be this way. Regardless of whether we consider Go as a “systems-oriented” language, it feels like runtime dictionaries was not the right technical implementation choice for a compiled language at all. Despite the low complexity of the Go compiler, it’s clear and measurable that its generated code has been steadily getting better on every release since 1.0, with very few regressions, up until now. And remember: > DO NOT despair and/or weep profusely, as there is no technical limitation in the language design for Go Generics that prevents an (eventual) implementation that uses monomorphization more aggressively to inline or de-virtualize method calls.
- jatone 5y agoI agree. I find this snippet interestingly incorrect. > with very few regressions, up until now. the idea that this is a regression is silly. you can't have a regression unless old code is slower as a result. which is clearly not the case. its just a less than ideal outcome for generics. which will likely get resolved.
- ramesh31 5y agoWell sure. Not writing hand tuned assembly can make your code slower, too. Go's value as a language is how it fills the niche between Rust and Python, giving you low level things like manual memory control, while still making tradeoffs for performance and developer experience.
- mrweasel 5y agoI might have worded it differently, but yeah, of cause generics can make your code slower, what did people expect.
- tsimionescu 5y agoIt depends what they are replacing. Typically, generics used to replace runtime polymorphism (using [T any] []T instead of []any) would be a speed boost in C#, C++, or Rust; and would have no impact on speed in Java.
- morelisp 5y agoAnd it is also a speed boost in Go, assuming you don't call any methods. (Which, if you were really using [T any], you either weren't or you were dissembling about your acceptable types.)
- zellyn 5y agoI don't know about you, but when I imagine what compilers do with generic code, I typically imagine monomorphization, which (aside from increasing cache pressure a little), should generally not make things slower, but rather introduce possibilities for inlining that could make it faster.
- mrweasel 5y agoApparently I scrolled right past that bit of the article. I’m a little unsure how it’s suppose to make the code faster, but maybe because I compare it wrong. The alternative to generics is writing all the different function by hand, in my mind at least. I don’t fully understand how generics are suppose to be made faster than a custom function for that datatype.
- throwoutway 5y agoThe first code-to-assembly highlighting example here is beautiful. Question to the authors— is that custom just for this article? Is there an open source CSS library or something that does this?
- tanoku 5y agoHey, author here. Thanks for the kind words! This is a custom pipeline that I designed for the article. It's implemented as a Node.js library using SVG.js and it statically generates the interactive SVGs directly in the static site generator I was using (Eleventy) by calling out to the Go compiler and extracting assembly for any lines you mark as interesting. It turned out very handy for iterating, but it's not particularly reusable I'm afraid!
- jatone 5y agowhat I expect to happen now that golang has generics and reports like these will show up is golang will explore monomorphizing generics and get hard numbers. they may also choose to use some of the compilation speeds they've gained from linker optimizations and spend that on generics. I can't imagine monomorphizing being that big of a deal during compilation if the generation is defered and results are cached.
- whimsicalism 5y agoI am unfamiliar with Go. This article discusses that they have decided to go for runtime lookup. Is there any reason why that implementation might make monomorphizing more difficult?
- jatone 5y agonope. it was an intentional trade off with respect to compilation speed. once generics have baked for a bit with real world usage said decision will almost certainly be revisited. edit: for example one could envision the compiler generates the top n specializations per generic function based on usage and then uses the current stuff non-specialized version for the rest.
- zellyn 5y ago(off-topic) Anyone else using Firefox know why the text starts out light gray and then flashes to unreadably dark gray after the page loads? (The header logo and text change from gray to blue too)
- wtetzner 5y agoI'm using Firefox and don't see that issue. Maybe some kind of plugin you have installed?
- pphysch 5y agoMy first use of Go generics has been for a concurrent "ECS" game engine. In this case, the gains are pretty obvious. I think. I get to write one set of generic methods and data structures that operate over arbitrary "Component" structs, and I can allocate all my components of a particular type contiguously on the heap, then iterate over them with arbitrary, type-safe functions. I can't fathom that doing this via a Component interface would be even as close as fast, because it would destroy cache performance by introducing a bunch of Interface tuples and pointer dereferencing for every single instance. Not to mention the type-unsafe code being yucky. Am I wrong? FWIW I was able to update 2,000,000 components per (1/60s) frame per thread in a simple Game of Life prototype, which I am quite happy with. But I never bothered to evaluate if Interfaces would be as fast
- folago 5y agoSounds interesting, is it available somewhere?
- pphysch 5y agoStill want to hit some milestones before releasing anything, so not quite
- siftrics 5y agoAssuming your generic functions take _pointers_ to Components as input, full monomorphization does not occur and you're suffering a performance hit similar in magnitude, if not strictly greater empirically, to interface "dereferences". On this basis, I don't believe your generic implementation is as faster than an interface implementation as you claim.
- pphysch 5y agoYou're right, here's what one of my hot loops look like: func (cc *ComponentContainer[T]) ForEach(f func(*Component[T])) { for _, page := range cc.pool.pages { for i := range page { if page[i].IsActive() { f(&page[i]) } } } } Still, the interface approach is a total nightmare from a readability + runtime error perspective so I won't be going back & will just hope for some performance freebies in 1.19 or later :^)
- klodolph 5y agoI'm excited about generics that gives you a tradeoff between monomorphization and "everything is a pointer". The "everything is a pointer" approach, like Haskell, is incredibly inefficient wrt execution time and memory usage, the "monomorphize everything" approach can explode your code size surprisingly fast. I wouldn't be surprised if we get some control over monomorphization down the line, but if Go started with the monomorphization approach, it would be impossible to back out of it because it would cause performance regressions. Starting with the shape stenciling approach means that introducing monomorphization later can give you a performance improvement. I'm not trying to predict whether we'll get monomorphization at some future point in Go, but I'm just saying that at least the door is open.
- zozbot234 5y agoYes, they seem to have shipped a MVP first, which is a sensible approach. Controlling the extent of monomorphization requires changes in how the code is written, so if they had offered that exclusively it would've been a pitfall to existing users. By boxing everything, they keep their MVP closer to the previously idiomatic interface{} pattern.
- qznc 5y agoA hybrid approach would be monomorphization for native types like int and pointers for records. C# is doing that if I remember correctly.
- Ar-Curunir 5y agoIMO that's a bad trade-off for many performance-sensitive applications, since it means that you can't rely on newtypes and structs for correctness.
- tines 5y agoHaskell does monomorphization as well. See https://reasonablypolymorphic.com/blog/specialization/ https://reasonablypolymorphic.com/blog/specialization/
- SomeCallMeTim 5y ago
- cube2222 5y agoGreat article, just skimmed it, but will definitely dive deeper into it. I thought Go is doing full monomorphization. As another datapoint I can add that I tried to replace the interface{}-based btree that I use as the main workhorse for grouping in OctoSQL[0] with a generic one, and got around 5% of a speedup out of it in terms of records per second. That said, compiling with Go 1.18 vs Go 1.17 got me a 10-15% speedup by itself. [0]:https://github.com/cube2222/octosql https://github.com/cube2222/octosql
- morelisp 5y ago> That said, compiling with Go 1.18 vs Go 1.17 got me a 10-15% speedup by itself. Where did you see this speedup? Other than `GOAMD64` there wasn't much in the release notes about compiler or stdlib performance improvements so I didn't rush to get 1.18-compiled binaries deployed, but maybe I should... (I do expect some nice speedups from using Cut and AvailableBuffer in a few places, but not without some rewrites.)
- cube2222 5y agoI've experienced that speedup on an ARM MacBook Pro. I've just checked on Linux AMD64 and there's no performance difference there.
- hencq 5y agoIt's probably because of the new register passing calling convention. From https://tip.golang.org/doc/go1.18 https://tip.golang.org/doc/go1.18 > Go 1.17 implemented a new way of passing function arguments and results using registers instead of the stack on 64-bit x86 architecture on selected operating systems. Go 1.18 expands the supported platforms to include 64-bit ARM (GOARCH=arm64), big- and little-endian 64-bit PowerPC (GOARCH=ppc64, ppc64le), as well as 64-bit x86 architecture (GOARCH=amd64) on all operating systems. On 64-bit ARM and 64-bit PowerPC systems, benchmarking shows typical performance improvements of 10% or more.
- ptomato 5y agoYeah, 1.17 got register (instead of stack) calling convention on amd64; 1.18 expanded that to arm64, which should be responsible for most of that performance improvement.
- deleted 5y ago[deleted]
- nvarsj 5y agoI'd argue that golang is inherently not a systems language, with its mandatory GC managed memory. I think it's a poor choice for anything performance or memory sensitive, especially a database. I know people would disagree (hence all the DBs written in golang these days, and Java before it), but I think C/C++/Rust/D are all superior for that kind of application. All of which is to say, I don't think it matters. Use the right tool for the job - if you care about generic overhead, golang is not the right thing to use in the first place.
- Thaxll 5y agoThere are very fast DB written in Go so this comment is irrelevant, what is the equivalent of https://github.com/VictoriaMetrics/VictoriaMetrics https://github.com/VictoriaMetrics/VictoriaMetrics in an other language?
- jpgvm 5y agoGorilla which many of VM ideas are based on is in C++. Druid is Java and very fast but not like for like as it's an event database not a timeseries database. Pinot is in the same vein. Most of the very big and very fast databases you have used indirectly though web services like Netflix (Cassandra), etc are written in Java.
- chakkepolja 5y agoThere's highly tuned java software too, like Lucene, do you call java a systems language? All in all I think the semantics debate is irrelevant. No one is going to use go for an OS only because someone on internet calls it a systems language.
- pjmlp 5y agoF-Secure did, https://www.f-secure.com/en/consulting/foundry/usb-armory https://www.f-secure.com/en/consulting/foundry/usb-armory Unless we now start the semantic debate if a Unikernel is an OS.
- baq 5y ago
- AtNightWeCode 5y agoIs there any large project that done an in-place replacement to use generics that has been benchmarked? I doubt that the change is even measurable in general.
- dse1982 5y agoThis is a very interesting article. I was however a bit confused by the lingo, calling everything generics. As I understood it the main point of the article quite precisely matched the distinction between generics and templates as I learned it. Therefore what surprised me most was the fact that go monomorphizes generic code sometimes. Which however makes sense given the way go's module-system works – i.e. imported modules are included in the compilation – but doesn't fit my general understanding of generics.
- ben0x539 5y agoRust also enthusiastically monomorphizes generic code. Templates vs generics seems to be more about the duck typing C++ templates use vs generics doing type parameters with statically checked constraints on the types.
- ki_ 5y agoGenerics are a generic solution, but they are absolutely necessary in my opinion.
- JaggerFoo 5y ago
- throwaway894345 5y agoThe article is like 9k words and it only mentions Rust twice in passing.
- komuW 5y agoGo does has some form of monomorphization implemented in Go1.18; it is just behind a feature flag(compiler flags). Look at the assembly difference between this two examples: 1. https://godbolt.org/z/7r84jd7Ya https://godbolt.org/z/7r84jd7Ya (without monomorphization) 2. https://godbolt.org/z/5Ecr133dz https://godbolt.org/z/5Ecr133dz (with monomorphization) If you don't want to use godbolt, run the command `go tool compile '-d=unified=1' -p . -S main.go` I guess that the flag is not documented because the Go team has not committed themselves to whichever implementation.
- masklinn 5y agoFWIW you can have two different compilers (and outputs) for the same input: https://godbolt.org/z/bb1oG9TbP https://godbolt.org/z/bb1oG9TbP in the compiler pane just click "add new" and "clone compiler" (you can actually drag that button to immediately open the pane in the right layout instead of having your layout move to vertical thirds and needing to move the pane afterwards). Learned that watching one of Matt's cppcon talks (A+, would do again), as you can expect this is useful to compare different versions of a compiler, or different compilers entirely, or different optimisation settings. But wait, there's more! Using the top left Add dropdown, you can get a diff view between compilation outputs: https://godbolt.org/z/s3WxhEsKE https://godbolt.org/z/s3WxhEsKE (I maximised it because a diff view getting only a third of the layout is a bit narrow).
- komuW 5y agothanks!
- kubanczyk 5y agoI feel like a half-idiot but I'm unable to tell how exactly the "unified=1" implements monomorphization. I don't see the extra indirections which OP writes about.
- fulafel 5y ago> Inlining code is great. Monomorphization is a total win for systems programming languages: it is, essentially, the only form of polymorphism that has zero runtime overhead Blowing your icache can result in slowdowns. In many cases it's worth having smaller code even if it's a bit slower when microbenchmarked cache-hot, to avoid evicting other frequently used code from the cache in the real system.
- masklinn 5y agoThe essay is missing a "usually", but it's true that monomorphisation is a gain in the vast majority of situations because of the data locality and optimisation opportunities offered by all the calls being static. Though obviously that assumes a pretty heavy optimisation pipeline (so languages like C++ or Rust benefit a lot more than a language with a lighter AOT optimisation pipeline like Java). Much as with JITs (though probably with higher thresholds), issues occur for megamorphic callsites (when a generic function has a ton of instances), but that should be possible to dump for visibility, and there are common and pretty easy solutions for at least some cases e.g. trampolining through a small generic function (which will almost certainly be inlined) to one that's already monomorphic is pretty common when the generic bits are mostly a few conversions at the head of the function (this sort of trampolining is common in Rust, where "conversion" generics are often used for convenience purposes so e.g. a function will take an `T: AsRef<str>` so the caller doesn't have to extract an `&str` themselves).
- kevwil 5y agoSeems obvious; like, did someone expect all the extra abstraction would make Go faster?
- __s 5y agoWhat extra abstraction? I'd expect without monomorphization the code should perform the same as interface{} code, perhaps minus type cast error handling overhead. That's the model where generics are passing interface{} underneath, & exist only as a type check (à la Java type erasure)
- throwaway894345 5y agoThe article articulates why it's reasonable to expect that generics would make Go faster. From TFA: > Monomorphization is a total win for systems programming languages: it is, essentially, the only form of polymorphism that has zero runtime overhead, and often it has negative performance overhead. It makes generic code faster.
- anonymoushn 5y agoYes? We used code generators to monomorphize our code in like 2015 and it was faster than using interfaces. Generics could reasonably produce the same code we did in 2015, but they don't.
- slackfan 5y agoMeh. The people who screamed loudest about Generics missing in Go aren't going to be using the language now that the language has them, and are going to find something new to complain about. The language will suffer now with additional developmental and other overhead. The world will continue turning.
- sedatk 5y agoThis is a great article yet with an unnecessarily sensationalist headline. Generics can be improved in performance over time, but a superstition like "generics are slow" (not the exact headline, but what it implies to reader) can remain stuck in our heads forever. I can see developers stick to the dogma of "never use generics if you want fast code", and resorting to terrible duplication, and more bugs.
- zachruss92 5y agoFor me Go has replaced Node as my preferred backend language. The reason is because of the power of static binaries, the confidence that the code I write today can still run ten years from now, and the performance. The difference in the code I’m working with is being able to handle 250 req/s in node versus 50,000 req/s in Go without me doing any performance optimizations. From my understanding Go was written with developer ergonomics first and performance is a lower priority. Generics undoubtedly make it a lot easier to write and maintain complex code. That may come at a performance cost but for the work I do even if it cuts the req/s in half I can always throw more servers at the problem. Now if I was writing a database or something where performance is paramount I can understand where this can be a concern, it just isn’t for me. I’d be very curious what orgs like CockroachDB and even K8s think about generics at the scale they’re using them.
- vorpalhex 5y ago> The difference in the code I’m working with is being able to handle 250 req/s in node versus 50,000 req/s in Go without me doing any performance optimizations. Your node code should be in the 2k reqs/s range trivially, with many frameworks comfortable offering 5k+. It is never going to be as fast as go, but it will handle most cases.
- throwaway894345 5y agoHow can you make these claims without information about what his application handles requests? Not everything is a trivial database read/write op.
- hsn915 5y agoesbuild is 100x faster than js build tools, so in general 100x speed up sounds about right.
- randomdata 5y agoSucrase, written in Typescript, claims to be 2x faster than esbuild. I'll leave you to your own benchmarks.
- hu3 5y agoRelated. The introduction of Generics in Go revived an issue about the ergonomics of typesafe Context in a Go HTTP framework called Gin: https://github.com/gin-gonic/gin/issues/1123 https://github.com/gin-gonic/gin/issues/1123 If anyone can contribute, please do.
- socialdemocrat 5y agoReally well written article. I liked that the author tried to keep a simple language around a fair amount of complex topics. Although the article paints the Go solution for generics somewhat negative, it actually made me more positive to the Go solution. I don't want generic code to be pushed everywhere in Go. I like Go to stay simple and it seems the choices the Go authors have made will discourage overuse of Generics. With interfaces you already avoid code duplication so why push generics? It is just a complication. Now you can keep generics to the areas were Go didn't use to work so great. Personally I quite like that Go is trying to find a niche somewhere between languages such as Python and C/C++. You get better performance than Python, but they are not seeking zero-overhead at any cost like C++ which dramatically increases complexity. Given the huge amount of projects implemented with Java, C#, Python, Node etc there must be more than enough cases where Go has perfectly good performance. In the more extreme cases I suspect C++ and Rust are the better options. Or if you do number crunching and more scientific stuff then Julia will actually outperform Go, despite being dynamically typed. Julia is a bit opposite of Go. Julia has generics (parameterized types) for performance rather than type safety. In Julia you can create functions taking interface types and still get inlining and max performance. Just throwing it out there are many people seem to think that to achieve max performance you always need a complex statically typed language like C++/D/Rust. No you don't. There are also very high speed dynamic languages (well only Julia I guess at the moment. Possibly LuaJIT and Terra).
- ovao 5y agoI expect we’re going to see most generic Go code happening at the lower levels of the stack. So cintainer libraries, utility/algo functions, and probably in some contexts around databases/ORMs. Outside of these contexts —- and because most usage will be able to simply leverage type deduction —- I’d guess most app code will look pretty similar to what we’ve seen before.
- dmullis 5y ago
- jimmaswell 5y ago> you create an exciting universe of optimizations that are essentially impossible when using boxed types Couldn't JIT do this?
- YesThatTom2 5y agoPeople that demanded generics don’t care about performance. They care about making excuses about not using Go.
- eliben 5y agoSome of the issues pointed out by this (very good) article may already be fixed in tip Go, with https://go-review.googlesource.com/c/go/+/385274 https://go-review.googlesource.com/c/go/+/385274
- torginus 5y agoThis is essentially how C# generics have worked since forever. If you want performance, don't use pointer type arguments.
- ribit 5y agoMonomorphisation is a double-edged blade. Sometimes keeping the code smaller and hot is better than inlining everything, especially when your application does not exclusively own all the system resources (an assumption that many “systems programming languages” sadly do). There is too much focus on “performance” aka. microbenchmarks, but they don’t tell you the whole story. If you have a heavily async environment, with multiple tasks running in parallel and waiting on each other in complex patterns, more compact, reusable code can not only speed up the work but also allow you to do more work per watt of energy. I think it’s great that golang designers decided to follow Swift’s approach instead of specializing everything. The performance issues can be fixed in time with more tools (like monomorphissation directives) and profile-guided optimization.
- deleted 5y ago[deleted]