3 ms·

> 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

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

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.