4 ms·

> 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

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

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.