论文标题
无锁，有序的链接列表的更务实的实现
A more Pragmatic Implementation of the Lock-free, Ordered, Linked List
论文作者
论文摘要
无锁，有序的链接列表是并发数据结构的重要示例。教科书实现的一个明显的，实用的缺点是，比较和划分（CAS）操作失败导致整个列表的重新列表（重试），这对这种线性时间数据结构尤其有害。我们首先观察到在某些条件下的CAS操作失败的情况不需要完全重试，从而减轻了这一缺点，其次是维护近似向后的指针，这些指针用于在列表中找到更接近的启动位置以进行重试操作。具有最差的确定性基准测试的实验以及在三个共享内存系统（Intel Xeon，AMD EPYC，SPARC-T5）上进行的标准，随机的，混合操作的吞吐量基准，显示了从重要的改进，范围从显着，到巨大的数量级。
The lock-free, ordered, linked list is an important, standard example of a concurrent data structure. An obvious, practical drawback of textbook implementations is that failed compare-and-swap (CAS) operations lead to retraversal of the entire list (retries), which is particularly harmful for such a linear-time data structure. We alleviate this drawback by first observing that failed CAS operations under some conditions do not require a full retry, and second by maintaining approximate backwards pointers that are used to find a closer starting position in the list for operation retry. Experiments with both a worst-case deterministic benchmark, and a standard, randomized, mixed-operation throughput benchmark on three shared-memory systems (Intel Xeon, AMD EPYC, SPARC-T5) show practical improvements ranging from significant, to dramatic, several orders of magnitude.
