A double-ended queue that
Derefs into a slice, also known as a ring buffer or circular buffer.
The main advantages of
nicer API: since it
Derefs to a slice, all operations that work on slices (like
sort) "just work" for
efficient: as efficient as a slice (iteration, sorting, etc.), more efficient in general than
Windows, Linux, MacOS and every other unix-like OS is supported (although maybe untested). The following targets are known to work and pass all tests:
The main drawbacks of
"constrained" platform support: the operating system must support virtual memory. In general, if you can use
std, you can use
global allocator bypass:
SliceDequebypasses Rust's global allocator / it is its own memory allocator, talking directly to the OS. That is, allocating and growing
SliceDeques always involve system calls, while a
VecDequebacked-up by a global allocator might receive memory owned by the allocator without any system calls at all.
smallest capacity constrained by the allocation granularity of the OS: some operating systems allow
SliceDequeto allocate memory in 4/8/64 kB chunks.
When shouldn't you use it? In my opinion, if
- you need to target
- you can't use it (because your platform doesn't support it)
you must use something else. If.
- your ring-buffer's are very small,
then by using
SliceDeque you might be trading memory for performance. Also,
- your application has many short-lived ring-buffers,
the cost of the system calls required to set up and grow the
might not be amortized by your application (update: there is a pull-request open
that caches allocations in thread-local heaps when the feature
enabled significantly improving the performance of short-lived ring-buffers, but
it has not been merged yet). Whether any of these trade-offs are worth it or not
is application dependent, so don't take my word for it: measure.
How it works
The double-ended queue in the standard library (
VecDeque) is implemented
using a growable ring buffer (
0 represents uninitialized memory, and
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 -
as_slices method returns a pair of slices) and has negative performance
consequences (e.g. need to account for wrap around while iterating over the
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
SliceDeque is able to
Derefs into a slice in those systems.
In general, you can think of
SliceDeque as a
This project is licensed under either of
- Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in SliceDeque by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.