aarc

• 快速入门
• 动机
• 示例
• 路线图
• 资源

快速入门

• AtomicArc / AtomicWeak：与 Arc 和 Weak 相似的原子更新指针的变体。
• Snapshot：一种类似于危险指针的新型智能指针，在多个线程从同一 AtomicArc 加载时显著减少争用。它防止分配，但不增加引用计数。

动机

使用 Arc 构建的数据结构通常需要锁来同步，因为只能原子更新引用计数，而不是指针或包含的数据。虽然锁通常是正确的方法，但在高度争用的情况下，无锁数据结构可以提供更好的理论性能和实际性能保证。

而不是用锁保护原地更新，一种替代方法是使用原子安装指针进行写时复制更新。为了确保对象在使用时不会被分配，通常利用安全的内存回收（SMR）机制。然而，像危险指针和基于周期的回收这样的经典技术，以及像分割引用计数这样的原子共享指针算法，往往扩展性差或者需要非常小心地使用。

aarc 通过实现一种混合技术来解决此问题，该技术结合了引用计数的便利性和最先进的 SMR 后端的效率。它提供了几个不同的优势

• 无等待性：引用计数通过基于 Hyaline [3, 4] 的机制进行保护 [1, 2]，这是一种最近引入的回收算法，而不是危险指针、EBR、RCU、锁或分割引用计数。在典型条件下（即有合理数量的线程被创建），所有操作都将 无等待，而不仅仅是无锁。
• 易用性：许多基于上述算法的现有解决方案都需要用户手动保护特定的指针或传递守卫对象。这个crate的API易于使用，旨在构建无锁数据结构，并且应该让Rust用户感到熟悉。提供的原子操作与内置的Arc兼容，并且没有依赖。

示例

示例1：Treiber栈

use aarc::{AtomicArc, Snapshot};
use std::sync::Arc;

struct StackNode {
    val: usize,
    next: Option<Arc<Self>>,
}

struct Stack {
    top: AtomicArc<StackNode>,
}

impl Stack {
    fn push(&self, val: usize) {
        let mut top = self.top.load::<Arc<_>>();
        loop {
            let new_node = Arc::new(StackNode { val, next: top });
            match self
                .top
                .compare_exchange(new_node.next.as_ref(), Some(&new_node))
            {
                Ok(_) => break,
                Err(before) => top = before,
            }
        }
    }
    fn pop(&self) -> Option<Snapshot<StackNode>> {
        let mut top = self.top.load::<Snapshot<_>>();
        while let Some(top_node) = top.as_ref() {
            match self
                .top
                .compare_exchange(top.as_ref(), top_node.next.as_ref())
            {
                Ok(_) => return top,
                Err(actual_top) => top = actual_top,
            }
        }
        None
    }
}

路线图

• 实现核心算法
• 实现各种性能优化
• 添加标记指针
• 添加更多测试并稳定API
• 添加no_std支持

资源

1. Anderson, Daniel, 等人. "具有常数时间开销的并发延迟引用计数法."
2. Anderson, Daniel, 等人. "将手动并发内存回收转换为自动引用计数法."
3. Nikolaev, Ruslan, 等人. "无快照、透明且健壮的无锁数据结构内存回收法."
4. Nikolaev, Ruslan, 等人. "Crystalline：快速且内存高效的等待自由回收法"

* 注意，这个crate的Snapshot与[3]中讨论的快照概念无关；而是[1]中引入的快照指针。