一句话：提出 RRR 通用方法，使 SMR 下的无锁数据结构能安全重用与移动节点而无需重新分配，并给出 Michael-Scott 队列的高效特化实现。
并发数据结构通常依赖安全内存回收（SMR，如 EBR、HP）管理内存，而 SMR 下新增元素必须重新分配对象。但复杂场景中同一对象常需在多个数据结构间无拷贝移动（如节点从链表移到另一链表再移回），这在 SMR 下通常不可行：ABA 问题使同一指针在未经历完整 SMR 周期后重现；且链表、跳表、哈希表、树等采用非平凡遍历与两阶段删除，逻辑删除的对象可能仍被其他线程访问。本文提出构建 RRR（Reduce、Reuse、Recycle）数据结构的通用方法，在 SMR 下安全地重用与回收内存，适用于链表、跳表、哈希表、Natarajan-Mittal 树等，并给出 Michael-Scott 队列的高效特化版本。x86-64 上对多种结构与 SMR 方案的评估显示良好前景。
Traditionally, most concurrent algorithms rely on safe memory reclamation (SMR)schemes for manual memory management. SMR schemes such as epoch-based reclamation (EBR) and hazard pointers (HP) are typically viewed as the only solution for memory recycling. When using SMR, a new object needs to be allocated whenever something new is added to a data structure. However, in more complex scenarios, the same object may need to be moved between different data structures (e.g., moving a node from one list to another, and then back to the original list) in a copy-free manner, i.e., without deallocating and allocating the node again. It is typically impossible for two reasons: (1) the ABA problem would still arise even when using SMR since the same pointer can reappear (without going through the full SMR cycle) if the same node eventually ends up back in the original data structure; (2) while in simple queues and stacks, nodes can immediately be recycled, it is unclear how to adapt data structures which use non-trivial traversal and two-phase deletion strategies, e.g., linked lists, skip lists, hash tables, trees, etc., where it is seemingly impossible to always immediately move (logically) deleted objects since they might still be accessed by other threads. We propose a general method of creating RRR (Reduce, Reuse, Recycle) data structures to allow safe memory recycling when using SMR which addresses the above-mentioned problems. Our method is applicable to linked lists, skip lists, hash tables, Natarajan-Mittal tree, and other data structures. We also discuss and propose a specialized approach – a more efficient version of Michael-and-Scott’s (recycling) queue. Our evaluation on x86-64 shows promising results when using our methods for different data structures and SMR schemes.
@article{paperbot3097,
title = {RRR-SMR: Reduce, Reuse, Recycle: Better Methods for Practical Lock-Free Data Structures},
author = {Md Amit Hasan Arovi and Ruslan Nikolaev},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {PLDI},
year = {2025},
doi = {10.1145/3729337}
}