A double-ended queue that
Derefs into a slice.
The double-ended queue in the standard library (
implemented using a growable ring buffer (
0 represents uninitialized
T represents one element in the queue):
// [ 0 | 0 | 0 | T | T | T | 0 ] // ^:head ^:tail
When the queue grows beyond the end of the allocated buffer, its tail wraps around:
// [ T | T | 0 | T | T | T | T ] // ^:tail ^:head
As a consequence,
Deref into a slice, since its
elements do not, in general, occupy a contiguous memory region. This
complicates the implementation and its interface (for example, there is no
as_slice method, but
as_slices returns a pair of slices) and has
negative performance consequences (e.g. need to account for wrap around
while iterating over the elements).
This crates provides
SliceDeque, a double-ended queue implemented with
a growable virtual ring-buffer.
A virtual ring-buffer implementation is very similar to the one used in
VecDeque. The main difference is that a virtual ring-buffer maps two
adjacent regions of virtual memory to the same region of physical memory:
// Virtual memory: // // __________region_0_________ __________region_1_________ // [ 0 | 0 | 0 | T | T | T | 0 | 0 | 0 | 0 | T | T | T | 0 ] // ^:head ^:tail // // Physical memory: // // [ 0 | 0 | 0 | T | T | T | 0 ] // ^:head ^:tail
That is, both the virtual memory regions
1 above (top) map to
the same physical memory (bottom). Just like
VecDeque, when the queue
grows beyond the end of the allocated physical memory region, the queue
wraps around, and new elements continue to be appended at the beginning of
the queue. However, because
SliceDeque maps the physical memory to two
adjacent memory regions, in virtual memory space the queue maintais the
ilusion of a contiguous memory layout:
// Virtual memory: // // __________region_0_________ __________region_1_________ // [ T | T | 0 | T | T | T | T | T | T | 0 | T | T | T | T ] // ^:head ^:tail // // Physical memory: // // [ T | T | 0 | T | T | T | T ] // ^:tail ^:head
Since processes in many Operating Systems only deal with virtual memory
addresses, leaving the mapping to physical memory to the CPU Memory
Management Unit (MMU),
SliceDeque is able to
Derefs into a slice in
In general, you can think of
SliceDeque as a
pop_front and amortized
The main drawbacks of
constrained platform support: by necessity
SliceDequemust use the platform-specific virtual memory facilities of the underlying operating system. While
SliceDequecan work on all major operating systems, currently only
MacOS Xis supported.
no global allocator support: since the
Allocator API does not support virtual memory, to use platform-specific virtual memory support
SliceDequemust bypass the global allocator and talk directly to the operating system. This can have negative performance consequences since growing
SliceDequeis always going to incur the cost of some system calls.
capacity constrained by virtual memory facilities:
SliceDequemust allocate two adjacent memory regions that map to the same region of physical memory. Most operating systems allow this operation to be performed exclusively on memory pages (or memory allocations that are multiples of a memory page). As a consequence, the smalles
SliceDequethat can be created has typically a capacity of 2 memory pages, and it can grow only to capacities that are a multiple of a memory page.
The main advantages of
nicer API: since it
Derefs to a slice, all operations that work on slices are available for
efficient iteration: as efficient as for slices.
simpler serialization: since one can just serialize/deserialize a single slice.
All in all, if your double-ended queues are small (smaller than a memory
page) or they get resized very often,
VecDeque can perform better than
SliceDeque typically performs better (see
the benchmarks), but platform support and global allocator bypass are two
reasons to weight in against its usage.
Mirrored memory buffer of length
A draining iterator for
An iterator produced by calling
An iterator that moves out of a deque.
A double-ended queue that derefs into a slice.
A splicing iterator for