3 ms·
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
by 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 agoIt'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.