一句话：提出 Crystalline 系列非阻塞内存回收方案，同时实现高吞吐、高内存效率与完全无等待性。
无锁引用计数等传统内存管理在读密集负载下效率低：EBR 性能好但内存可能无界而阻塞，HP 非阻塞、内存效率高却较慢且通用情形仅 lock-free；WFE 无等待但内存效率与超订阅表现不佳，Hyaline 高效却缺少无等待性。本文提出 Crystalline 系列非阻塞回收方案，兼求高吞吐、高内存效率与完全无等待：线程动态回收时仍保证完全无等待，支持异步回收（任意线程可回收其他线程退休的内存），并使回收负载跨线程近乎均衡。方案在 x86-64 与 ARM64 上实现，随线程数增长吞吐超过 EBR 等快速方案，并为多数据结构场景提供严格非阻塞保证。
Historically, memory management based on lock-free reference counting was very inefficient, especially for read-dominated workloads. Thus, approaches such as epoch-based reclamation (EBR), hazard pointers (HP), or a combination thereof have received significant attention. EBR exhibits excellent performance but is blocking due to potentially unbounded memory usage. In contrast, HP are non-blocking and achieve good memory efficiency but are much slower. Moreover, HP are only lock-free in the general case. Recently, several new memory reclamation approaches such as WFE and Hyaline have been proposed. WFE achieves wait-freedom, but is less memory efficient and performs suboptimally in oversubscribed scenarios; Hyaline achieves higher performance and memory efficiency, but lacks wait-freedom. We present a family of non-blocking memory reclamation schemes, called Crystalline, that simultaneously addresses the challenges of high performance, high memory efficiency, and wait-freedom. Crystalline can guarantee complete wait-freedom even when threads are dynamically recycled, asynchronously reclaims memory in the sense that any thread can reclaim memory retired by any other thread, and ensures (an almost) balanced reclamation workload across all threads. The latter two properties result in Crystalline’s high performance and memory efficiency. Simultaneously ensuring all three properties requires overcoming unique challenges. Crystalline supports ubiquitous x86-64 and ARM64 architectures, while achieving superior throughput than prior fast schemes such as EBR as the number of threads grows. We also accentuate that many recent approaches, unlike HP, lack strict non-blocking guarantees when used with multiple data structures. By providing full wait-freedom, Crystalline addresses this problem as well.
@article{NikolaevR24,
title = {A Family of Fast and Memory Efficient Lock- and Wait-Free Reclamation},
author = {Ruslan Nikolaev and Binoy Ravindran},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {PLDI},
year = {2024},
doi = {10.1145/3658851}
}