Rust中的Triple Buffering

这是什么？

这是一个用Rust编写的三缓冲区实现。您可能觉得它在以下类型的线程同步问题中很有用

• 有一个生产者线程和一个消费者线程
• 生产者想要定期更新共享内存值
• 消费者想要随时访问生产者的最新更新

使用它的最简单方法是以下这样

// Create a triple buffer
use triple_buffer::triple_buffer;
let (mut buf_input, mut buf_output) = triple_buffer(&0);

// The producer thread can move a value into the buffer at any time
let producer = std::thread::spawn(move || buf_input.write(42));

// The consumer thread can read the latest value at any time
let consumer = std::thread::spawn(move || {
    let latest = buf_output.read();
    assert!(*latest == 42 || *latest == 0);
});

在将原始值移除且在消费者侧无法修改它代价太高的场景中，例如如果创建新值涉及到动态内存分配，您可以使用一个低级API，允许您直接访问生产者和消费者的缓冲区，并精确控制何时传播更新

// Create and split a triple buffer
use triple_buffer::triple_buffer;
let (mut buf_input, mut buf_output) = triple_buffer(&String::with_capacity(42));

// Mutate the input buffer in place
{
    // Acquire a reference to the input buffer
    let input = buf_input.input_buffer();

    // In general, you don't know what's inside of the buffer, so you should
    // always reset the value before use (this is a type-specific process).
    input.clear();

    // Perform an in-place update
    input.push_str("Hello, ");
}

// Publish the above input buffer update
buf_input.publish();

// Manually fetch the buffer update from the consumer interface
buf_output.update();

// Acquire a mutable reference to the output buffer
let output = buf_output.output_buffer();

// Post-process the output value before use
output.push_str("world!");

给我详细说明！它与其他替代方案相比如何？

与互斥锁相比

• 仅适用于单生产者、单消费者场景
• 是非阻塞的，更精确地说是有界无等待的。并发访问会被缓存竞争减慢，但不可能出现死锁、活锁或线程调度引起的减速。
• 允许生产者和消费者同时工作
• 使用更多的内存（3x有效负载 + 3x字节 vs 1x有效负载 + 1个布尔值）
• 不允许原地更新，因为生产者和消费者不访问相同的内存位置
• 应该有更快的读取和更慢的更新，特别是在原地更新比写入新数据副本更有效时。
  • 当数据未被更新时，三缓冲区的读取事务只需内存读取，无需原子操作，并且可以与任何正在进行的事务并行执行。
  • 当数据已被更新时，读取事务需要不可失败的原子操作，这可能与大多数互斥锁实现中使用的可失败原子操作一样快或更快。
  • 除非您的数据不能原地更新而必须始终完全重写，否则互斥锁提供的原地更新数据的能力应该使更新更加高效，远远超过来自同步协议的性能差异。

与Linux内核中的读-复制-更新（RCU）原语相比

• 仅适用于单生产者、单消费者场景
• 在松散内存架构（ARM、POWER等）上有更高的脏读开销
• 不需要为读取者的“宽限期”进行会计：一旦读取者获取到最新值，同步事务就结束了
• 在更新时，不使用比较和交换的硬件原语，这从设计上是不高效的，因为它迫使用户在循环中重试事务。
• 不受ABA问题的影响，允许代码更简单
• 仅在初始化时分配内存，而不是在每次更新时
• 可能需要更多的内存（3倍负载 + 3倍字节与1倍指针 + 依赖于读取和更新模式的负载和引用计数量相比）
• 如果更新很少，则应该较慢；如果更新频繁，则应该更快
  • RCU的愉快读取路径略快（无需检查标志），但其更新过程更加复杂且成本更高。

与在消息队列上发送更新相比

• 仅在单生产者、单消费者场景下工作（队列可以在其他场景下工作，尽管实现效率较低）
• 消费者只能访问最新状态，不能访问之前的版本
• 消费者不需要通过每个先前状态
• 是非阻塞的，并且使用有限的内存量（与队列相比，这是一个选择，除非你使用那些在满载时静默丢弃数据的邪恶队列）
• 可以单次传输信息，而不是两次
• 对于任何兼容的使用案例，应该更快
  • 队列迫使你移动数据两次，一次进入，一次出来，这对任何非平凡数据都会产生显著的成本。如果内部数据需要分配，它们迫使你在每次事务中分配。按照设计，它们迫使你存储并遍历每个更新，而你只对数据的最新版本感兴趣时，这并没有用。

简而言之，在共享内存位置频繁由单个写入者更新、由单个只想要最新版本的读取者读取，并且你可以节省一些RAM的场景中，你需要的是三重缓冲。

• 如果你需要多个生产者，请另寻他处
• 如果你需要多个消费者，你可能对我的相关“SPMC缓冲区”工作感兴趣，它基本上将三重缓冲扩展到多个消费者
• 如果你无法容忍内存开销或想要原地更新数据，尝试使用互斥锁（或可能是一个读写锁）
• 如果共享值更新很少（例如，每秒更新一次），尝试使用RCU
• 如果消费者必须获取每个更新，尝试使用消息队列

我如何知道你的不安全的无锁代码是否正常工作？

当然是通过运行测试！遗憾的是，这比我希望的要困难。

首先，我们有顺序测试，这些测试非常彻底，但显然没有检查无锁/同步部分。你可以这样运行它们

$ cargo test

然后我们有并发测试，例如，一个读取线程持续观察来自速率限制的写入线程的值，并确保他可以看到每个更新，中间没有任何错误值。

这些测试更重要，但运行起来也更困难，因为必须首先检查一些假设

• 测试主机必须至少有2个物理CPU核心，以测试所有可能的竞争条件
• 没有其他代码应该在后台消耗CPU。包括其他测试。
• 由于适当的写入速率是系统相关的，此测试中配置的值可能不适合您的机器。
• 你必须以发布模式进行测试，因为编译器优化往往会创造更多的竞争条件机会。

考虑到这一点以及相对较长的运行时间（约10-20秒），默认情况下会忽略并发测试。要运行它们，请确保后台没有占用CPU，然后执行

$ cargo test --release -- --ignored --nocapture --test-threads=1

最后，我们有基准测试，这允许您测试代码在您的机器上的性能。我们现在使用criterion进行基准测试，似乎运行它们，您可以简单地做

$ cargo install cargo-criterion
$ cargo criterion

这些基准测试测试了u8有效负载的最坏情况，其中同步开销占主导地位，因为读取和写入实际数据的成本仅为1个周期。在实际应用中，您将花更多的时间更新缓冲区，而花在同步它们的时间较少。

然而，由于微基准测试的人为性质，基准测试必须练习两种场景，分别是过于乐观和过于悲观的

1. 在不争用模式下，缓冲区输入和输出位于同一CPU核心上，这低估了将修改后的缓存行从源CPU的L1缓存传输到目标CPU的L1缓存的开销。
   • 这并不像听起来那么糟糕，因为无论您使用什么类型的线程同步原语，您都将为此开销付费，所以我们在这里没有隐藏triple-buffer特定的开销。您需要做的只是确保当与另一个同步原语进行比较时，该原语以类似的方式进行基准测试。
2. 在争用模式下，被基准测试的三缓冲区的一半正在承受来自另一半的最大负载，这在实际工作负载中要繁忙得多。
   • 在这种配置下，您实际上测量的是CPU的缓存行锁定协议和跨CPU核心数据传输的性能，这是在triple-buffer的共享数据访问模式下的。

因此，将这些基准测试的时间视为从最佳到最差预期的triple-buffer数量级，实际性能将在这两个数字之间，具体取决于您的负载。

在Intel Core i3-3220 CPU @ 3.30GHz上，典型结果如下

• 干净读取：0.9 ns
• 写入：6.9 ns
• 写入+脏读取：19.6 ns
• 脏读取（估计）：12.7 ns
• 争用写入：60.8 ns
• 争用读取：59.2 ns

许可证

此crate根据MPLv2许可证条款分发。有关详细信息，请参阅LICENSE文件。

还可以协商更宽松的许可证（Apache、MIT、BSD...），以换取财务贡献。有关详细信息，请联系knights_of_ni AT gmx DOTCOM。