{'fraction_non_alphanumeric': 0.047784703097067206, 'fraction_numerical': 0.011305986374836933, 'mean_word_length': 4.770281572344578, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
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 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.


Introduction
The lock-free, ordered, singly linked list as proposed in [5,8] is a textbook example of a concurrent data structure [6,12]. The data structure supports lock-free insertion (add()) and deletion (rem()), and wait-free contains (con()) operations on items identified by a unique key. The lockfree implementation is actually quite subtle. The ordering condition and a relaxed invariant makes it possible to do with a single-word compare-and-swap operation (CAS()), and all operations can be shown to be linearizable even though linearization does not always happen at fixed points in the code (CAS() operations). The lock-free data structure has many direct and indirect applications, notably in the implementation of concurrent skiplists and hash tables [8,11,13,14].
An obvious, practical drawback of the standard implementation is the draconic action on failed CAS() operations: A retraversal from the head of the list is simply initiated. For a linear-time data structure, this is particularly harmful since it in the worst case entails traversal of the whole list. For any individual thread, this can happen indefinitely, since the implementation is not starvation-free. Available implementations seem to implement ordered, lock-free lists in this way [1,3,4,7].
In [2], this problem was addressed by maintaining a doubly linked list. The implementation is more complex involving two atomic flags and extra CAS() operations; the paper focuses on a theoretical analysis, and gives no experimental results, and none seem to have been prominently reported.
The present, short paper gives some most pragmatic improvements to the textbook implementation that seem to benefit practical performance from significantly to dramatically. The improvements first seek to avoid complete retraversal of the list wherever possible by examining the reason for each failed CAS() operation. In both add(), rem() and the crucial internal operation for finding the position in the list on which to add or remove an item, there are such possibilities (this may well be done in other implementations, but we have not found any published claims). Second, by extending the list items with a predecessor pointer that is maintained approximately by conditional, atomic stores and loads, all failed CAS() operations traverse the list backwards only to a point where a new, forwards find operation can be started. The backward pointers only have to fulfill that for any list item, there is a path back to the head (sentinel) element of the list. The improvements change the instances where the list operations linearize, but we claim that the implementation remains linearizable largely as the textbook implementation.
Unfortunately, the introduction of backward pointers and cursor significantly complicate the problem of safe memory reclamation. The implementation benchmarked here does only simple memory reclamation after each experiment. How to do proper memory reclamation with these improvements is at the moment beyond this paper.

Improvement and Implementation
The standard lock-free, ordered linked list implementation maintains the invariants that items are in key order and that an item is in the list iff it is reachable from the head and not marked. The mark (flag) kept with each list item is a stolen bit in the item's pointer to the next larger item, such that mark and pointer can be checked and updated atomically by a single CAS() operation. Textbook implementations use a non-visible search function for locating the position where a given key could be; this function has the additional, crucial task of linking out items that have become marked. A CAS() operation is used for linking out a marked item, for inserting a new item, and for marking an item for deletion. Each of these CAS() operations check both that the item from which the operation is performed has not become marked, and that the pointer to the next larger item has not changed.
We observe the following.
• Upon failure of the CAS() operation in the search function, if the item on which the operation failed has not become marked (only the pointer changed due to another thread having had success in linking out the item), there is no reason to restart the search from the head of the list; it suffices to reread the next pointer of the item.
• In the rem() operation, if the CAS() operation fails due to the item having become marked, the delete can be linearized as failed, since the item has been removed by another thread. The linearization point is not the failed CAS(), though, but the earlier of this and the point just before an overlapping add() operation is about to successfully insert an item with the same key. If instead the CAS() failed due to the pointer to the next item having changed, the thread can simply try again to mark the item. This can be repeated until the item to be deleted has become marked, successfully by some thread. Once the node is marked it is logically deleted and will be removed eventually. So a failure of the subsequent CAS() to unlink the node from the list can simply be ignored.
• In an add() operation, if the CAS() operation fails due to the next pointer having changed (but not the mark), the search for the position where to add can be continued from the item, there is no reason to go back to the head of the list. All that is needed is to reread the pointer.
The three observations lead to three mild, pragmatic improvements of the textbook implementation. The first (search function) and second (rem()) are illustrated with concrete code snippets from our implementation (that is available from the authors) in Listing 1 and Listing 2. The third mild improvement (in add()) is handled by the search function which checks the mark of the current element. Implementation is done in C11 using the standard atomic operations with the C11 memory model (acquire-release); LOAD, STORE and CAS are macros for these. It is worth noting that these changes do not introduce any issues regarding memory reclamation; any of the commonly used techniques will do.
The changes to the rem() operation makes another (platform specific) improvement possible, namely to use an atomic fetch-and-or operation to set the delete mark on the next pointer. On architectures that natively support this operation this would have the advantage that the marking operation cannot fail. We also benchmarked this potential improvement in the course of this paper by relying on the corresponding C11 operation. We note that x86 architectures can support and atomic (lock) or operation, but not an atomic fetch-and-or.
The more intrusive improvement which actually entails the milder improvements for free, extends list items with a backwards pointer to a previous, smaller key element. On a CAS() failure, the search function will simply have the task to go backwards in the list, that is through smaller key items, until an unmarked element is found from which the search in increasing key order can be started.
The search function with backward pointer is shown in Listing 3. In order for the implementation to be correct, the backward pointers only have to fulfill that for any item, there is a path via backward pointers back to the head of the list. When a new item is inserted into the list, the backwards pointer of the successor is set with an atomic store to point to the new element. Likewise, when an item is removed, the backwards pointer of the successor item is updated to skip the removed item. This suffices to maintain the invariant, but through long sequences of (concurrent) insertions and deletions, backwards pointers can become imprecise in that they skip many items that are actually in the list. As seen in Listing 3, we try to maintain more precise backwards pointers by updating them during forwards traversals. Since updates with atomic stores are expensive due to cache coherence activity, we only update a pointer if a test (with non-atomic, relaxed loads) shows that a pointer is not correct. Also, when a marked item is linked out, the backwards pointer of its successor is updated to skip the linked out item. One reason for this is that memory reclamation can (only) be done when there are no pointers to a removed item.
In contrast to the algorithm of [2], this optimistic implementation has no extra flag to be maintained with possibly expensive (failing) CAS() operations.
The final, highly pragmatic improvement is to exploit throughout the doubly linked structure of the list. Each thread maintains a cursor item in the list. On its next operation, depending on the key of the item to be located, the find operation will search either forwards (increasing key order) or backwards (smaller key order) in the list from the cursor. Each add(), rem() and con() operations sets the cursor to the item before the located item.
Obviously, keeping a cursor to an item in the middle of the list reduces the average runtime complexity for a singly linked structure as well, since we only have to search from head to cursor, or from cursor to end, depending on the key of the item to be located.
Unfortunately, the introduction of backward pointers significantly complicates the problem of safe memory reclamation, because it can happen that a backwards pointer references a node that has already been removed from the list. In order to retire a node for reclamation, it has to be ensured that it is not referenced by any next or backwards pointer. Proper memory reclamation with these improvements is currently outside the scope this work.

Experimental results
We have conducted a number of experiments with the described C11 implementations on different platforms to illustrate concrete, pragmatic benefits of the observations and improvements we discussed. Experiments have been done on three standard multi-core systems: 1. A 64-core AMD EPYC system with two 32-core AMD EPYC 7551 sockets at 2.9GHz 2. An 80-core Intel Xeon with 8 E7-8850 sockets at 1.06GHz 3. A 64-core SPARC v9 system with eight 8-core SPARC-T5 sockets at 3.6GHz and 8x SMT.
We have used two different benchmarks.
• Deterministic worst-case benchmark: Starting from an empty list, each tread performs the following three sequences each of length of n: con(k(i)), add(k(i)), con(k(i)), add(k(i)) for i = 0 to n − 1, then con(k(i)), rem(k(i)), con(k(i)), rem(k(i)) from i = n − 1 to i = 0, finally con(k(i)) for i = 0 to n − 1. The key function k(i) is chosen either such that each thread t has its own sequence of keys, disjoint from all other threads, k(i) = t + ip (p number of threads), or such that all threads have the same key sequences, k(i) = i. Due to the linear search in the ordered lists, the sequential behavior per thread is O(pn 2 ) (for disjoint keys) or O(n 2 ) (for same keys) steps.
• Standard random operation mix benchmark: Keys are chosen uniformly at random in an interval [0, U − 1] (random r). The list is prefilled with some number of items f , then a mix of randomly chosen add(), rem() and con() operations is performed with predefined probability for each operation (here we report only for the mix 10 − 10 − 80). Each thread performs the same number of operations c, and threads have different seeds for the random number generator (we use the thread-safe random r() generator, except on SPARC since this function is not available on Solaris). For chosen f and U the number of elements of the list will not vary too much.
We use OpenMP to manage threads and time the benchmarks. The benchmarks can also be configured such that each thread operates on a private list, such that there is no interaction required between threads. In this configuration, we can use either the lock-free implementation, or a standard, sequential (doubly or singly linked) list implementation. These configurations can give an idea of the system and memory overheads when there is no actual interaction between threads. We do not report on the thread private behavior here. We report on six implementation variants, namely a) draconic (textbook implementation), b) singly linked list with mild improvements, c) Table 1: Deterministic benchmark k(i) = i, AMD EPYC system, p = 64, n = 100000. Operation breakdown: "adds" is the number of successful add() operations, "rems" the number of successful rem() operations, "cons" the number of element traversals over all con() operations, "trav" the number of list element traversals in the search function, "fail" the number of CAS() failures, and "rtry" the number of retries in the search function. Variants: a) draconic, b) singly, c) doubly, d) singly-cursor, e) singly-fetch-or, f) doubly-cursor. doubly linked list with approximate backward pointers and retry from from head of list, d) singlycursor singly linked list with per thread retry from the last recorded position (cursor) in the list, e) singly-fetch-or singly linked list with per thread retry from the last recorded position (cursor) and atomic fetch-and-or in the rem() operations, and f) doubly-cursor doubly linked list with per thread retry from the last recorded position (cursor) in the list. On Intel and AMD we used the standard glibc memory allocator; on SPARC we used the libumem allocator. All implementations and code used in the experiments are available from the authors. Results for fixed number of threads on the different platforms for the two benchmarks are shown in Tables 1, 2, 3, 4, 5, and 6. We report throughput over the number of operations, and also count the number of failed CAS() operations, the number of retries, the total number of list item traversals in the search operation, and the total number of traversals in contains operations, and the total number of successful add() and rem() operations. The results in the tables are for one single specific run of the benchmarks. Runs differ, but in a tolerable range.
We investigate the (weak) scalability of five of the six (excluding the atomic fetch-and-or variant) variants with the random operation mix benchmark. Here, we plot the mean throughput of 5 experiments. The scalability results are shown in Figures 1, 2 and 3. The experiments were run with a key range of 32768 and an update ratio of 50% (25% add(), 25% rem()); the lists were prefilled with 16384 items. These settings are comparable to those used in [3].
In the tables and plots, p denotes the number of started threads, n the list length for the deterministic benchmark, c the number of operations per thread for the random mix benchmark (thus weak scaling in the scalability experiments, since the number of operations per thread is kept fixed for increasing p), f the number of prefilled elements, and U the upper bound for the key range.

Discussion
The mild improvements over the draconic textbook implementation clearly reduce the number of retries; as a consequence it also reduces the completion time and improves the throughput, but not as much as expected. The (emulated) atomic fetch-and-or operation as expected brings no improvement over the corresponding improved singly linked list with cursor. Table 2: Deterministic benchmark k(i) = t+ip, AMD EPYC system, p = 64, n = 10000. Operation breakdown: "adds" is the number of successful add() operations, "rems" the number of successful rem() operations, "cons" the number of element traversals over all con() operations, "trav" the number of list element traversals in the search function, "fail" the number of CAS() failures, and "rtry" the number of retries in the search function. Variants: a) draconic, b) singly, c) doubly, d) singly-cursor, e) singly-fetch-or, f) doubly-cursor.  Table 3: Random operation mix benchmark, AMD EPYC system, p = 64, c = 1000000, f = 1000, U = 10000. Operation Mix 10% add(), 10% rem(), 80 % con(). Operation breakdown: "adds" is the number of successful add() operations, "rems" the number of successful rem() operations, "cons" the number of element traversals over all con() operations, "trav" the number of list element traversals in the search function, "fail" the number of CAS() failures, and "rtry" the number of retries in the search function. Variants: a) draconic, b) singly, c) doubly, d) singly-cursor, e) singly-fetch-or, f) doubly-cursor.  Deterministic benchmark k(i) = i, Intel Xeon system, p = 80, n = 100000. Operation breakdown: "adds" is the number of successful add() operations, "rems" the number of successful rem() operations, "cons" the number of element traversals over all con() operations, "trav" the number of list element traversals in the search function, "fail" the number of CAS() failures, and "rtry" the number of retries in the search function. Variants: a) draconic, b) singly, c) doubly, d) singly-cursor, e) singly-fetch-or, f) doubly-cursor.     Figure 1: Scalability with threads of random operation mix benchmark, AMD EPYC system, c = 50000, f = 16384, U = 32768. Operation Mix 25% add(), 25% rem(), 50% con() Table 6: Random operation mix benchmark, Intel Xeon system, p = 80, c = 1000000, f = 1000, U = 10000. Operation Mix 10% add(), 10% rem(), 80 % con(). Operation breakdown: "adds" is the number of successful add() operations, "rems" the number of successful rem() operations, "cons" the number of element traversals over all con() operations, "trav" the number of list element traversals in the search function, "fail" the number of CAS() failures, and "rtry" the number of retries in the search function. Variants: a) draconic, b) singly, c) doubly, d) singly-cursor, e) singly-fetch-or, f) doubly-cursor.        Table 9: Random operation mix benchmark, SPARC-T5 system, p = 64, c = 1000000, f = 1000, U = 10000. Operation Mix 10% add(), 10% rem(), 80 % con(). Operation breakdown: "adds" is the number of successful add() operations, "rems" the number of successful rem() operations, "cons" the number of element traversals over all con() operations, "trav" the number of list element traversals in the search function, "fail" the number of CAS() failures, and "rtry" the number of retries in the search function. Variants: a) draconic, b) singly, c) doubly, d) singly-cursor, f) doubly-cursor.    However, the situation changes when we keep a cursor to the last used item. In case of the doubly linked list this allows us to starting search in the backwards/forwards direction from last item position; for the singly linked list it still cuts the list into two pieces, allowing us to start searching either from the last position or from head, depending on the key of the item to be located. This can improve performance dramatically, in particular for the doubly linked list in the deterministic benchmark (orders of magnitude).
But also in the random mix benchmark the cursor based implementations are significantly faster. When using a cursor, the ability to search backwards in doubly linked list pays off, resulting in significantly better performance, at least on Intel and AMD; on SPARC, the cursor based singly/doubly linked list implementations perform more or less on par.
The mild improvements (with cursor) are easy, unintrusive improvements to the standard, textbook implementation of the lock-free, ordered linked list with significant enough performance improvements to be considered, also for more complex algorithms (skip lists and hash tables) that build on the linked list data structure. These improvements do not comprise the chosen memory reclamation scheme. The approximate backward pointers in the doubly linked improvements can be extremely beneficial in certain cases (the deterministic benchmarks that were designed to highlight this), but come at cost, and complicate memory reclamation. A possible application is a simplification in the implementation of the Stamp-It memory reclamation system [9,10].