3 ms·

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 tren

by 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.
  - maxwell86 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! 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.
    - deleted 5y ago
      [deleted]
    - foldr 5y ago
      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.
      - maxwell86 5y ago
        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 https://github.com/gnzlbg/slice_deque
        foldr 5y ago
        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.
vgatherps 5y ago
> 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.
losvedir 5y ago
> 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.
- foldr 5y ago
  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.)

by foldr 5y ago

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.
- maxwell86 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! 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.
  - deleted 5y ago
    [deleted]
  - foldr 5y ago
    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.
    - maxwell86 5y ago
      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 https://github.com/gnzlbg/slice_deque
      - foldr 5y ago
        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.

vgatherps 5y ago

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

losvedir 5y ago

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

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