Hacker News Reader

Comment by foldr | Hacker News Reader

Something fishy here. A generic data structure is exactly the kind of code that you wouldn’t expect to perform better with generics. At most you’re getting the benefits of unboxing and the absence of a single conditional jump for the type check when you convert back from interface{}. But that shouldn’t make much difference to a series of tests that just push and pop items for a queue. I suspect that any realistic code using this data structure would see no tangible performance benefit. These tests are probably just picking up the cost of an extra allocation required to box a primitive type as an interface.

If you’ll excuse the blog spam, I did a dive into the performance of interface{} here: https://adrummond.net/posts/gogenerics

(The blog post was written before it was certain that Go would get generics.)

View on HN

> At most you’re getting the benefits of unboxing

Which is.. 3x? or 10x?

> These tests are probably just picking up the cost of an extra allocation required to box a primitive type as an interface.

I've seen unboxing deliver 100x speed ups cause it allowed the compiler to auto-vectorize multiple loops, fuse them, optimize stuff better etc. Stuff that it can't do if it doesn't know the memory layout of things, or if there are "optimization barriers" inserted in between all these steps (`interface {}`).

---

TBH it's 2022 and it seems that "Go" devs are just seeing fire for the first time in their lives. Yeah, fire heats. And yeah, this type of stuff if why people don't put Go in the same bag of languages as C++ or Rust.

Go feels fast if you are coming from Python, but if you actually look at what the hardware can deliver in terms of FLOPs and BW, Go programs run at 0% of hardware peak (and no, just because your task manager shows go threads using 100% of the CPU doesn't mean that it is achieving 100% of peak CPU perf).

Exactly. Go was (still is tbh) slow. that is why these improvements are possible. Fast is relative ofc but if you are going to introduce the words "low level" in your description then don't be surprised when C/C++/Rust rear their ugly (but very fast) heads.

> Go was (still is tbh) slow.

"Slow" isn't an objective metric. Slow how?

It's less that it isn't objective but more that it's relative.

As I mentioned in my original comment once you start throwing around the expression "low-level language" or "systems language" you invite comparisons to C/C++/Rust.

Thus you will end up with a list of points like this:

It makes less efficient use of hardware due to poor vectorization and lack of JIT to take advantage of this information which would be apparent at runtime. Namely escape analysis would be particularly good. I imagine that Go on Graal would be a very very fast language if time was invested there.

Also until recently generics weren't a thing so it made it impossible to do -high performance- generic data-structures without code-gen. They were possible, but slow as balls due to interface{} and reflection.

It's garbage collector is mediocre for latency, nothing impressive. But it's straight dog shit for throughput. Definitely not -fast- compared to JVM/Hotspot/ZGC.

So, on the good side of Go it provides easy/good access to primitive types and primitive arrays of said types so as long as you know what you are doing you can generally massage the compiler into doing something not completely stupid.

That said if I want to write really fast code in something that isn't C/C++/Rust I would much prefer Java or C#... or more logically if FAST is the primary concern then I would probably pick C++ or Rust.

> It's garbage collector is mediocre for latency, nothing impressive.

Go's GC is best-in-class for latency. What makes you think otherwise?

It's on par with other latency optimized GCs for pure pause time but because it's architecture pays a gigantic throughput cost making it only a mediocre GC overall. ZGC puts out the same pause numbers with monstrous throughput in comparison.

Even in these microbenchmarks it’s not 10x.

Boxing can be faster or slower depending on the context. For example, if the objects you are storing are large, unboxing them (rather than storing pointers to them) could well make the queue perform worse, as extending the arrays will require more memory to be copied.

There’s no doubt that the unboxing permitted by (Go’s) generics will sometimes lead to better performance. But I think that the article is exaggerating.

> TBH it's 2022 and it seems that "Go" devs are just seeing fire for the first time in their lives.

Come on, let’s keep this patronizing and flamey kind of commentary off HN. I for one am a language nerd who’s tried plenty of languages with various forms of generics. I’ve even been paid to write Haskell code! That said, I was pretty happy with Go without generics.

You can just verify using any language with powerful optimizations and whose generic system supports both boxed and unboxed generics, e.g., Rust.

The difference between passing an unboxed generic and triggering monomorphization vs passing a boxed type-erased generic is night and day in terms of performance.\

Boxed generics generate one version of the code that need to work for all types, independently of layout, and dispatch via the generic ABI (aka `interface {}` in Go).

Unboxed generics generate one version of the code per type, removing memory allocations, and allowing the compiler to optimize the function for each type and each layout independently.

This increases code size and compilation times, but in many cases allows dozens of compiler optimizations that aren't possible for the boxed generic case. The code produced by these optimizations allow others to run, etc. And a 100x improvement in perf isn't uncommon (i've seen order of magnitude larger improvements and regressions in perf than that from switching back and forth between boxed and unboxed generics in Rust).

Let me wade in: I think what you're saying is plausible, because the CPU cache should be an important variable here. Boxing should cause cache misses.

Its not only CPU cache, its the whole CPU.

Having one function per type results in more instructions in total, cause you end up with more copies of the function, but less instructions when dealing with one type, like in a collection of values of one type only.

Less instructions is linear speed up. Single copy of the code enables inlining, constant propagation for type sizes, which enables vectorization of loops. Vectorization alone can buy you up to 32x on modern hardware if the code is flops limited.

Avoiding pointer indirections also trash the cache less, and the BW of caches is orders of magnitude higher than the bandwidth of ram (multiple TB/s vs lower 100 GB/s).

And caches have lower latencies so CPU threads wait less on memory.

So your speed up ends up: less instructions * more FLOPs * more BW, and that can easily be 10x * 32x * 20 ~= 6000x in the worst pathological case.

A 1000x speed up / slowdown per element due to switching between boxed and unboxed generics is less common than a 100x speed up in Rust, but it does happen.

We can already see the comparison in the benchmark in the original blog post.

I edited my previous post to point out that I’m familiar with Rust and other trendy languages. Please don’t assume that I’m not just because I don’t also hate Go.

The speed up (or even slow down!) from boxing is highly dependent on the nature of the code, the size of the relevant type, and the usage patterns for the data structure.

In the context of a generic data stucture, unboxing is not likely to unlock a huge number of optimizations. This is in contrast to e.g. generic code for performing matrix operations, where unboxing could make a huge performance difference.

My original post said “A generic data structure is exactly the kind of code that you wouldn’t expect to perform better with generics.” You then responded by taking about performance improvements deriving from autovectorization, which are relevant to generics in general but not to generic data strucures like a deque.

> n the context of a generic data stucture, unboxing is not likely to unlock a huge number of optimizations.

This is not true, the difference between a Vec<Box<T>> and a Vec<T> is huge. You can't easily vectorize a Vec<Box<T>> cause the elements can be in different memory locations, and this is important because... people do loop over all elements in data-structures super often.

And not only vectorization, but removing the memory indirection would make much better use of caches, depending on the size of T, multiply your memory BW by a big factor, etc.

Hopefully you’re not looping over all the elements in your deques super often, or there wouldn’t be much point in using a deque!

We’re talking past each other here. Yes, unboxing will sometimes give a performance improvement. But I’m skeptical that any realistic code using the deque structure in the blog post would see much of a gain. To repeat, even in the micro benchmark in the blog post, the performance gains are only around 3x. In most realistic application-level code, the code paths that lead to insertion of a new element will also do some allocation, so that the cost of boxing is lost in the noise.

Vectorization strikes me as a fairly niche case. It’s revealing that you use Vec as an example. In any case where autovectorization is going to give a useful performance improvement, you probably can just use a Vec. And of course, the Go equivalent of an unboxed Vec in Rust doesn’t require generics anyway. So I doubt that there is a large body of existing Go code that will suddenly become ripe for autovectorization once data structure libraries switch over to generics.

> Hopefully you’re not looping over all the elements in your deques super often, or there wouldn’t be much point in using a deque!

I do this all the time: one thread fills the deque, while another thread consumes as much of it as passible.

A modern deque is just a contiguous (mirrored) array in virtual memory. From the point of view of the algorithms, it looks just like a Vec.

If I understand the scenario correctly, you're pushing items onto the end of the queue and consuming items from the beginning. You don't really need two arrays in that case. A single array can be efficiently extended at one end and shrunk from the other end. (Admittedly, the way slices work in Go makes it awfully easy to leak memory if you do that in a naive way. But that's a separate issue from generics.)

Edit: I forgot to mention that channels are also a good fit for this sort of use case in Go.

There is a single contiguous memory allocation, which mirrors itself.

One thread produces elements and pushes them at the tail (e.g. I/O bytes, in batch), and one thread consumes as many elements as possible in batch from the other end (e.g. all bytes available, in batch).

The VA mirror is required to allow processing all elements in the deque as if they were adjacent in memory, instead of having to "chunk" them depending on how the deque currently wraps.

This is the library I am using, the array contains an explanation : https://github.com/gnzlbg/slice_deque

It's a cool library. What I'm not quite getting is why your use case requires a deque rather than just a regular queue. If you just used a regular queue then you wouldn't need any virtual memory tricks to keep things contiguous while keeping the required big O characteristics.

Enqueue by appending to a slice; dequeue by incrementing the index of the oldest element. To avoid space growing indefinitely, copy the backing array to a smaller array every time the backing array becomes k times larger than the queue. If you're not enqueuing items at both ends of the queue, that's all you need for an efficient queue that maintains contiguity.

> In the context of a generic data stucture, unboxing is not likely to unlock a huge number of optimizations.

Aside from the optimisation of "Not having to allocate and deallocate memory", you can unlock the optimisations of "removing one step of pointer chasing" and "better memory locality" - arguably the top two things one should be thinking about when writing fast code.

If your datastructure has to access the memory, boxed values hurt you in two ways. One is that on each access you have to chase a pointer to who-knows-where. There's also no reason to believe that this value is going to be stored next to other values in the datastructure.

This hurts you in two ways - the obvious one is that extra pointer hop is another chance to miss cache. The less obvious way is that loading one element doesn't do anything to bring nearby elements in from the cache. If your datastructure tends to access nearby items together (say a btree), this is extremely valuable for performance. An even better feature is that if you start loading some sort of metadata nearby elements (again, like a btree might have), the prefetcher might already start loading your data.

You also get inlining benefits in this case - a virtual call out to some comparison function might compile down to a single instruction.

You bring up a good point, that there are cases where boxing matters like having extremely large elements (you still get inlining with generics though). It also matters less for datastructures that don't actually inspect their elements in any way. But in my experience, if you look at something like a map type datastructure, you don't see keys being 1KB objects - they tend towards things like strings, integer IDs, or fairly small structs consisting of the above.

Benchmarking these effects can be a little tricky - small microbenchmarks can reside entirely in L1 or L2 and get extremely unrealistic allocation patterns (only thing allocating == nice, contiguous, allocations), so a realistic benchmark has to apply some degree of cache/allocator pressure that's relevant to your workload.

> In the context of a generic data structure, unboxing is not likely to unlock a huge number of optimizations.

Reading between the lines here from your other comments, I think you might be excluding simple arrays here, because in Go you could already have monomorphized functions over unboxed arrays of elements without the new Generics feature? (I say "Generics feature" because that's what is new; I'd say Go already had support for "generics" special cases for arrays.)

Because generics over simple arrays is somewhere that unquestionably, vastly improves performance, in most normal situations. That's the impetus for "data oriented design", and the reason for, e.g. pandas using Arrow as a backing store, or why Clickhouse absolutely flies, or the basis for q/kdb: data locality to take advantage of CPU cache lines.

I think that in many situations, iterating over an array of contiguous data is faster than a more "optimal" algorithm (from a Big O perspective) juggling pointers. I've seen a couple talks on this, I think one by Godbolt and one by Strausberg, and they were kind of counterintuitive to me (what do you mean iterating over an array is faster than having a map?), but very thought provoking.

Yes, exactly.

I can see why people say that Go already had a sort of built-in generics feature. However, I think the same could be said about any language that allows you to define arrays with different element types (e.g. C). In common parlance, a language has generics iff it permits you to explicitly abstract over types.

I wish it had occurred to me earlier that C vs. C++ is a good test case here. If generics really led to huge performance improvements in typical application-level code, we'd expect C++ programs to run much faster than C programs. Typically, they don't. Of course there are exceptions, such as code that benefits from libraries like uBLAS.

(I'm aware that you can fake generics in C using macros, but there are also comparable code generation tools for Go.)

If only they'd had them from the beginning and not bolted them on

Then we probably wouldn't have had Go for the last decade, and we wouldn't have all the real world use cases to guide a correct implementation of generics. "Get it completely right the first time" has never happened in the history of software.

Unboxing is a huge optimisation though isn’t it? No need to allocate when inserting a new item into the queue (beyond the standard allocations which happen when growing a slice), fewer pointer indirections when reading the queue, easier garbage clean up at the end (a single deallocation of a slice).

I think (but am not sure) that the Go compiler can add some small primitive types and structs (precisely: those that fit in a machine word) to a []interface{} by storing them inline, removing the need for an allocation. So perhaps you will only see major speed increases when using larger structs.

With larger structs it’s a double-edged sword. Unboxing them also means that the deque implementation has to copy a lot more memory when extending the underlying slices.

Unboxing is typically an optimization, for sure. I guess I disagree that it’s a ‘huge’ one except maybe in the case of arrays/slices (where you can do it anyway in Go without generics).

That's an incredible memory you have. Word sized values can be inline, but they still have the type overhead. I only know this since I just checked

Reply on news.ycombinator.com