A more Pragmatic Implementation of the Lock-free, Ordered, Linked List
A more Pragmatic Implementation of the Lock-free, Ordered, Linked List
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 …