Lock-Free Atomic Shared Pointers Without a Split Reference Count? It Can Be Done!

• 语言: 英语
• 格式: .pptx
• 来源: github.com/CppCon

摘要

The document discusses the implementation of lock-free atomic shared pointers without a split reference count, exploring how existing atomic/shared_ptr is implemented using the split reference count technique. It covers concurrency patterns, deferred reclamation (garbage collection in C++), and benchmarks for lock-free code, considering factors like throughput, latency, workload, data locality, and contention. A lock-free stack implementation is demonstrated using atomic/shared_ptr, and the challenges of concurrent operations on shared pointers are addressed through a split reference count approach.

AI总结

《无需分离引用计数的无锁原子共享指针？完全可行！》
作者：丹尼尔·安德森（Daniel Anderson）

### 总结

本文介绍了如何在无锁环境中实现原子共享指针（`atomic`），并探讨了其实现机制、性能和应用场景。以下是核心内容的总结：

---

### 1. **shared_ptr 的内部实现**
`shared_ptr` 通过引用计数机制管理共享资源，其控制块（`control_block`）包含引用计数和指向资源的指针。

---

### 2. **原子变量与并发模式**
- 原子变量（`atomic`）用于在多线程环境中安全地操作共享变量。
- 无锁编程（lock-free）通过 CAS（Compare-And-Swap）操作避免竞态条件，确保并发安全。

---

### 3. **现有 `atomic` 的实现：分离引用计数技术**
现有的 `atomic` 实现通常采用分离引用计数技术：
- 引入一个额外的引用计数结构体（`counted_cb`），包含控制块指针和局部引用计数。
- 通过原子操作管理局部引用计数和全局引用计数，避免了竞态条件。

**关键点：**
- `local_ref_count` 记录了当前存储的指针的未完成加载操作的数量。
- 存储操作（`store`）会将局部引用计数移到全局引用计数中，从而避免了竞态条件。

---

### 4. **延迟回收机制**
延迟回收（Deferred Reclamation）类似于垃圾回收，确保资源在不被引用时安全释放。

---

### 5. **无锁栈的实现**
文中展示了一个基于 `atomic` 的无锁栈实现：

template
struct Stack {
    struct Node { T t; shared_ptr next; };
    atomic> head;

    void push_front(T t) {
        auto p = make_shared(std::move(t), head.load());
        while (!head.compare_exchange_weak(p->next, p)) {}
    }

    optional pop_front() {
        auto p = head.load();
        while (p && !head.compare_exchange_weak(p, p->next)) {}
        if (p) return {std::move(p->t)}; else return {};
    }
};

- `push_front` 和 `pop_front` 使用 CAS 操作确保无锁并发安全。

---

### 6. **性能基准测试**
- 多线程和无锁代码的基准测试具有挑战性，需要考虑以下因素：
- **测量指标：** 吞吐量 vs 潜伏期（Throughput vs Latency）。
- **工作负载：** 读写操作的比例。
- **缓存热度：** 数据是否在缓存中。
- **竞争程度：** 同一位置的操作线程数。

---

### 总结
本文通过对 `atomic` 的实现机制、分离引用计数技术和无锁栈的实现，展示了如何在无锁环境中高效且安全地管理共享指针。其核心思想是通过原子操作和引用计数分离来避免竞态条件，同时确保性能和内存安全。