aarc 0.3.1

Atomically updatable variants of Arc and Weak for lock-free concurrency.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

# aarc


- [Quickstart](#quickstart)
- [Motivation](#motivation)
- [Examples](#examples)
- [Roadmap](#roadmap)
- [Resources](#resources)

### Quickstart


- [`Arc`](https://docs.rs/aarc/latest/aarc/struct.Arc.html) /
  [`Weak`](https://docs.rs/aarc/latest/aarc/struct.Weak.html): drop-in replacements for the standard library's `Arc`
  and `Weak`, but implemented with deferred reclamation semantics.
- [`AtomicArc`](https://docs.rs/aarc/latest/aarc/struct.AtomicArc.html) /
  [`AtomicWeak`](https://docs.rs/aarc/latest/aarc/struct.AtomicWeak.html): variants of `Arc` and
  `Weak` with atomically updatable pointers, supporting standard atomic operations like `load` and `compare_exchange`.
- [`Guard`](https://docs.rs/aarc/latest/aarc/struct.Guard.html): A novel smart pointer that can be loaded from
  `AtomicArc` or `AtomicWeak`, designed to reduce contention when multiple threads operate on the same atomic variable.
  It prevents deallocation but does not contribute to reference counts. (This was renamed from `Snapshot` in an earlier
  version, to reduce confusion.)

### Motivation


Data structures built with `Arc` typically require locks for synchronization, as only
the reference counts may be atomically updated, not the pointer nor the contained data. While locks
are often the right approach, lock-free data structures can have better theoretical and practical
performance guarantees in highly-contended settings.

Instead of protecting in-place updates with locks, an alternative approach is to perform copy-on-write updates by
atomically installing pointers. To avoid use-afer-free, mechanisms for safe memory reclamation (SMR) are typically
utilized (i.e. hazard pointers, epoch-based reclamation). `aarc` uses the blazingly fast algorithm provided by the
[`fast-smr`](https://github.com/aarc-rs/fast-smr) crate and builds on top of it, hiding unsafety and providing
convenient RAII semantics through reference-counted pointers.

### Examples


Example 1: [Treiber Stack](https://en.wikipedia.org/wiki/Treiber_stack)

```rust no_run
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();
        loop {
            let top_ptr = top.as_ref().map_or(null(), AsPtr::as_ptr);
            let new_node = Arc::new(StackNode {
                val,
                next: top.as_ref().map(Arc::from),
            });
            match self.top.compare_exchange(top_ptr, Some(&new_node)) {
                Ok(()) => break,
                Err(before) => top = before,
            }
        }
    }
    fn pop(&self) -> Option<Guard<StackNode>> {
        let mut top = self.top.load();
        while let Some(top_node) = top.as_ref() {
            match self
                .top
                .compare_exchange(top_node.as_ptr(), top_node.next.as_ref())
            {
                Ok(()) => return top,
                Err(actual_top) => top = actual_top,
            }
        }
        None
    }
}
```

### Roadmap


- [ ] relax atomic orderings from SeqCst to Acq/Rel
- [ ] add tagged pointers
- [ ] add more tests and stabilize APIs

### Resources


1. [Anderson, Daniel, et al. "Concurrent Deferred Reference Counting with Constant-Time Overhead."](https://dl.acm.org/doi/10.1145/3453483.3454060)
2. [Anderson, Daniel, et al. "Turning Manual Concurrent Memory Reclamation into Automatic Reference Counting."](https://dl.acm.org/doi/10.1145/3519939.3523730)