4 ms·

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

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

ogogmad 5y ago
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.
- maxwell86 5y ago
  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.
foldr 5y ago
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.
- maxwell86 5y ago
  > 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.
  - foldr 5y ago
    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.

ogogmad 5y ago

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.

maxwell86 5y ago
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.

foldr 5y ago

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.

maxwell86 5y ago
> 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.
- foldr 5y ago
  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.