切片环形缓冲区

一个双向队列，可以解引用为切片，也称为环形缓冲区或循环缓冲区。

⚠️ 注意 ⚠️

这是一个基于 SliceDequeue 的分支，由于原始项目不再维护，添加了安全补丁。我将保持仓库更新，包括安全补丁等，但不会进行积极的功能开发。欢迎 Pull requests

优点

SliceRingBuffer 的主要优点是

• 更好的 API：因为它可以解引用为切片，所以所有适用于切片的操作（如 sort）对 SliceRingBuffer 都适用。

• 高效：与切片一样高效（迭代、排序等），通常比 VecDeque 更高效。

平台支持

支持 Windows、Linux、MacOS 以及所有其他类 Unix 系统（尽管可能未经测试）。以下目标是已知可以工作并通过所有测试的

Linux

• aarch64-unknown-linux-gnu
• arm-unknown-linux-gnueabi
• arm-unknown-linux-musleabi
• armv7-unknown-linux-gnueabihf
• armv7-unknown-linux-musleabihf
• i586-unknown-linux-gnu
• i686-unknown-linux-gnu
• i686-unknown-linux-musl
• mips-unknown-linux-gnu
• mips64-unknown-linux-gnuabi64
• mips64el-unknown-linux-gnuabi64
• mipsel-unknown-linux-gnu
• powerpc-unknown-linux-gnu
• powerpc64-unknown-linux-gnu
• powerpc64le-unknown-linux-gnu
• x86_64-unknown-linux-gnu
• x86_64-unknown-linux-musl
• aarch64-linux-android
• arm-linux-androideabi
• armv7-linux-androideabi
• x86_64-linux-android

MacOS X

• i686-apple-darwin
• x86_64-apple-darwin

Windows

• x86_64-pc-windows-msvc

缺点

SliceRingBuffer 的主要缺点是

• "受限制"的平台支持：操作系统必须支持虚拟内存。通常，如果你可以使用 std，你也可以使用 SliceRingBuffer。

• 全局分配器绕过：SliceRingBuffer绕过了Rust的全局分配器/它是自己的内存分配器，直接与操作系统通信。也就是说，分配和增长 SliceRingBuffer 总是涉及系统调用，而由全局分配器支持的 VecDeque 可能会接收到分配器拥有的内存，而无需任何系统调用。

• 最小容量受操作系统分配粒度限制：某些操作系统允许 SliceRingBuffer 以 4/8/64 kB 块的形式分配内存。

什么时候不应该使用它？在我看来，如果

• 你需要针对 #[no_std]，或者
• 你不能使用它（因为你的平台不支持它）

你必须使用其他东西。如果

• 你的环形缓冲区非常小，

那么使用 SliceRingBuffer 可能是内存与性能的权衡。另外，

• 如果你的应用程序有许多短暂的环形缓冲区，

设置和增长 SliceRingBuffer 所需的系统调用成本可能不会被你的应用程序分摊（更新：当启用功能 use_std 时，有一个打开的pull-request，它会在线程局部堆中缓存分配，显著提高了短暂环形缓冲区的性能，但它尚未合并）。这些权衡是否有价值取决于应用程序，所以不要只相信我的话：要衡量。

它是如何工作的

标准库中的双端队列（VecDeque）使用可增长的环形缓冲区（0 代表未初始化的内存，而 T 代表队列中的一个元素）实现。

// [ 0 | 0 | 0 | T | T | T | 0 ]
//               ^:head  ^:tail

当队列增长到分配缓冲区的末尾时，其尾部会环绕

// [ T | T | 0 | T | T | T | T ]
//       ^:tail  ^:head

因此，VecDeque 不能 Deref 到切片，因为其元素通常不占用连续的内存区域。这增加了实现和其接口的复杂性（例如，没有 as_slice 方法 - as_slices 方法返回一个切片对）并带来负面的性能影响（例如，在迭代元素时需要考虑环绕）。

此crate提供 SliceRingBuffer，这是一个使用可增长的 虚拟 环形缓冲区实现的双端队列。

虚拟环形缓冲区的实现与在 VecDeque 中使用的实现非常相似。主要区别在于，虚拟环形缓冲区将两个相邻的虚拟内存区域映射到相同的物理内存区域。

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

也就是说，上面的虚拟内存区域 0 和 1 映射到相同的物理内存（下方）。就像 VecDeque 一样，当队列增长超出分配的物理内存区域末尾时，队列将回绕，并且新元素将附加到队列的开头。然而，因为 SliceRingBuffer 将物理内存映射到两个相邻的内存区域，所以在虚拟内存空间中，队列保持了连续内存布局的错觉。

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

由于许多操作系统中的进程只处理虚拟内存地址，将物理内存映射留给CPU内存管理单元（MMU），SliceRingBuffer 能够在这些系统中将这些系统中的切片引用（Deref）到一个切片中。

这简化了 SliceRingBuffer 的API和实现，在某些情况下使其性能优于 VecDeque。

一般来说，您可以将 SliceRingBuffer 视为一个具有 O(1) pop_front 和摊销 O(1) push_front 方法的 Vec。