undefined | Better HN

0 pointsmaxwell864y ago0 comments

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

0 comments

3 comments · 1 top-level

foldr4y ago· 2 in thread

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.

maxwell86OP4y 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

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

j / k navigate · click thread line to collapse