St³ — Stealing Static Stack

具有 FIFO 窃取和 LIFO 或 FIFO 语义的工作窃取队列的不锁定、有界队列

概述

Go 调度程序和 Tokio 运行时是高性能调度程序的示例，这些调度程序依赖于固定容量（有界）工作窃取队列，以避免与无界队列（如 Chase-Lev 工作窃取双端队列）相关的分配和同步开销，例如 Crossbeam Deque。这对于使用全局注入器队列的调度程序来说是一个自然的设计选择，因为后者通常可以在几乎没有额外成本的情况下，在本地队列满时缓冲溢出。对于此类应用程序，St3 提供了高性能、固定大小的、不锁定 FIFO 和 LIFO 工作窃取队列。

FIFO 队列基于 Tokio 队列，但提供了更方便、更灵活的 API。LIFO 队列是一个新颖的设计，具有与它的 FIFO 对应方相同的 API 和性能指标；它可以被视为 Chase-Lev 双端队列的更快、固定大小的替代方案。

用法

将此添加到您的 Cargo.toml

[dependencies]
st3 = "0.4.1"

示例

use std::thread;
use st3::lifo::Worker;

// Push 4 items into a queue of capacity 256.
let worker = Worker::new(256);
worker.push("a").unwrap();
worker.push("b").unwrap();
worker.push("c").unwrap();
worker.push("d").unwrap();

// Steal items concurrently.
let stealer = worker.stealer();
let th = thread::spawn(move || {
    let other_worker = Worker::new(256);
    // Try to steal half the items and return the actual count of stolen items.
    match stealer.steal(&other_worker, |n| n/2) {
        Ok(actual) => actual,
        Err(_) => 0,
    }
});

// Pop items concurrently.
let mut pop_count = 0;
while worker.pop().is_some() {
    pop_count += 1;
}

// Does it add up?
let steal_count = th.join().unwrap();
assert_eq!(pop_count + steal_count, 4);

安全性 —— 一点注意事项

St³ 队列是低级原语，因此它们的实现依赖于 unsafe。测试套件广泛使用了 Loom 来评估正确性。然而，尽管它很神奇，但 Loom 只是一个工具：它不能形式化证明没有数据竞争。

在 St³ 在领域中得到更广泛的应用和审查之前，您在使用它之前应谨慎行事。特别是 LIFO 队列是一个新的并发算法，因此可能会发现测试套件未能捕获的健全性问题。

性能

St³队列不使用原子栅栏，并且几乎不使用原子读-改-写（RMW）操作。与Tokio队列类似，它们在push操作中不需要RMW，而pop操作中只需要一个。偷取操作在LIFO变体中只需要一个RMW，而在FIFO变体中需要两个。

第一个基准测试测量了单线程、无偷取情况下的性能：一系列64个push操作（或在大批量情况下256个）之后，接着进行同样数量的pop操作。

测试CPU：i5-7200U

第二个基准测试是一个合成测试，旨在表征具有并发偷取的多线程性能。它使用一个玩具式的工作偷取执行器，在4个工作者中的每一个上安排任意数量的任务（从1到256），每个任务通过将其重新注入到其工作者中任意次数（从1到100）来重复。每个工作者最初分配的任务数量和每个任务要重复的次数由伪-RNG随机确定，这意味着所有基准测试队列的工作负载都是相同的。所有队列都使用Crossbeam Dequeue工作偷取策略：一半的任务被偷取，最多32个任务。尽管如此，由于线程时间的影响，通过工作偷取重新分配任务最终是非确定的。

鉴于基准测试的某种简单和主观设计，以下数据必须持保留态度。特别是，这个基准测试没有模拟消息传递。

测试CPU：i5-7200U

ABA

就像Tokio队列一样，St³队列容易受到ABA问题的影响。例如，在一种简单的实现中，如果偷取操作在错误的时刻被中断，正好需要的时间足以弹出与队列容量相等的项目，而推送的项目少于弹出的项目，那么一旦恢复，偷取者可能会试图偷取比可用更多的项目。ABA通过使用可以多次索引实际缓冲区容量的缓冲区位置来克服，从而将周期长度增加到最坏情况中断之上。

因此，当目标支持64位原子操作时，St³将使用32位缓冲区位置，这应该在实际中提供对ABA的完全抵抗力。只支持32位原子操作的目标（例如MIPS）将使用16位缓冲区位置，这在理论上引入了极小的ABA风险。请注意，Tokio在版本1.21.1之前使用16位位置为所有目标，因此你可能不必太担心这个问题。

致谢

尽管LIFO实现最终相当不同，但Tokio FIFO队列的灵感帮助确定了性能目标。

Tokio的队列本身就是Go的工作偷取队列的修改版。Go使用类似于Seqlock模式的东西，其中偷取者乐观地读取所有标记为偷取的项目，然后如果它们已经被并发地从队列中驱逐，则稍后丢弃它们。由于Rust的更严格的别名规则，这种模式很难实现，因此Tokio队列被设计为能够“预订”项目，这个想法被St³的LIFO队列借鉴。

许可证

此软件根据您的选择，受Apache许可证版本2.0或MIT许可证的许可。

测试套件和基准测试中的一些资产可能根据不同的条款进行授权，这些条款在这些资产中明确列出。

贡献

除非您明确声明，否则根据Apache-2.0许可证定义，您有意提交以包含在该作品中的任何贡献都将按上述方式双重授权，没有任何附加条款或条件。