The first one, named LROrderedLinkedList (LROLL), is just a linked-list-set wrapped in the Left-Right pattern.
The second one, named LROrderedLinkedListSingle (LROLLS), is sightly more complex, but it is faster for modifications (insertions and removals).
These two data structures are interesting as examples of using and implementing the Left-Right pattern in a scalable way in C++14, and they are also the only linked-list sets that are WFPO for read-only operations. In fact, these two are the only linked list sets that are wait-free for read-only operations in C++, AFAIK.
Yes, I know about Harris linked list set which is lock-free for all operations (lookups, insertions, and removals), and I know about its variant with wait-free lookups (wait-free bounded by the number of keys in the set), but there is a detail about the variant with wait-free lookups that it implicitly requires a system with a Garbage Collector. On a system without an automatic GC (like C11 or C++1x) we can't use Harris's linked list by itself without adding some kind of memory management, i.e. Hazard Pointers.
There are two problems with using Hazard Pointers (HP) in Harris list:
First, HPs are not very fast, because they require at least one store with release barrier for each node of the list that is traversed, even though the lookup function is expected to be a read-only operation.
Second, the HP technique is lock-free and not wait-free, which means that using it in the lookup function reduces the progress condition of the lookups from wait-free bounded to lock-free.
In practice, all this means that in C11/C++1x there is no linked list set that is wait-free AFAIK (if you happen to know one, please add the link to it on the comments section).
If you have no idea what Harris linked list is, or what are Hazard Pointers, then here are the links to them:
http://timharris.uk/papers/2001-disc.pdf
http://concurrencyfreaks.com/2014/03/harriss-linked-list.html
http://researchweb.watson.ibm.com/people/m/michael/ieeetpds-2004.pdf
This is where LROLL enters. LROLL is composed of the Left-Right pattern associated with two linked list sets. The basic idea is that read-only operations are going on one of the lists, while a single modifying thread is inserting/removing a node on the other list, and afterwards redirects new lookups to the recently modified list and waits for unfinished lookups before applying the same modification on the opposite list.
Notice that there is only one instance of each key but there are two nodes for each key, and that LROLL does its own memory management without needing an extra memory management.
The big disadvantage is that the Left-Right pattern has a global lock that serializes modifications in the list (insertions/removals). This means that both insertions and removals are blocking, which by itself is not too bad, but the problem is that it's not scalable due to the serialization of the modifying operations. Moreover, two lookups are needed, and the modification has to be applied on two lists, which doubles the pain.
However, there are three big advantages:
First, the WFPO progress condition on the lookups means that the number of synchronized atomic operations is constant (depends on the readIndicator used, but typically just two or three stores with release). This provides excellent performance for lookups and very low latency guarantees.
Second, both HPs and Harris linked list are patented. HPs are patented by IBM, and Harris list by Sun/Oracle. The Left-Right pattern is free for use :)
https://docs.google.com/viewer?url=patentimages.storage.googleapis.com/pdfs/US20040107227.pdf
https://docs.google.com/viewer?url=patentimages.storage.googleapis.com/pdfs/US7117502.pdf
Third, and this is non-obvious, there are no other linked list implementations that provide linearizability for read-only iterators, with the exception of using a mutex or reader-writer lock to protect a linked list, but that approach is blocking for all operations. Both Harris linked list and Michael & Scott linked list provide only weak consistency for iterators of the list, but the LROLL and LROLLS provides linearizability for read-only iterators (this property is sometimes called snapshot consistency).
Just how important is to have linearizabile read-only iterators? Well, it depends on your application, so let me give an example.
Suppose you have a banking application that uses a linked list set of bank accounts. If we use a LROLL, adding a new bank account or removing a closed account are both blocking procedures. Doing a transfer from one account to another is also a blocking operation. Checking the current amount in an account is WFPO (and linearizable).
How about determining the whole amount of cash available in all the accounts, i.e. all the money in the bank? Well, that is also a WFPO operation and linearizable, because it is a read-only iteration that goes over all the accounts. Notice that while this operations is ongoing, any modifying operation will have to wait for this to finish (and for any other read-only operations). Harris and Michael & Scott lock-free lists don't allow for this kind of operation, or they do allow, but not in a linearizable way, which in practice means that the result of a function that goes over all the accounts and sums them all will most likely be very different from the actual amount in the bank because you can count ongoing transfered amounts twice (or multiple times), or never count them. For example, suppose there are only two accounts and while one thread is summing the values from each, there is another thread that is doing a transfer from the first to second, by removing from the first 1M $ and then adding 1M $ to the second... if at the same time the other thread reads the amount after the 1M $ has been withrawed and then reads the value on the second account before it is credited, then it will see 1M $ less than the actual amount of money in the bank.
The above situation can not happen with LROLL
LROLLS extends the idea of LROLL a bit further. Instead of having two instances of the linked list, it has a single physical linked list but two logical lists as shown below:
Each node has two "next" members, one of the logical left list (nextL) and another for the logical right list (nextR):
<template T> class Node {
T *key;
Node *nextL;
Node *nextR;
};
The first benefit of this approach is saving one pointer to the key, thus saving some memory, but the main advantage is the fact that an insertion or removal in the middle of the list does not have to start over and do a second lookup to find the node to insert after (or the node to be removed) because it is the same physical node. In LROLLS it's just a matter or linking/unlinking the new node on the same physical node for both nextL and nextR.
In LROLLS, an insertion has to do one lookup to find the node previous to the one before the insertion point of the new node (let's say it's nextL), and then insert the new node there, wait for the left-right toggle, and then insert on the same node but do it on the opposite list (let's say nextR). In LROLL, this last step requires a lookup from the beginning of the list, but on LROLLS we already know where the node is, so no lookup is needed, which means we don't waste time doing a second lookup. For small lists this isn't much of an advantage because most of the time is coming from the overhead of the synchronization needed by the Left-Right pattern, but for large lists, this can make a difference in performance that is nearly 2x faster for LROLLS than for LROLL.
For example, in LROLLS the removal of the key Y from the set would work like this:
1. The Writer starts from the head of the logical list opposite to the one the Readers are using and unlinks the corresponding next field.
2. The Writer re-directs new Readers to the currently modified logical list, waits for older Readers to finish on the other logical list, and then unlinks the other next field.
3. The node with the key Y can now be deleted/free’ed
All these examples use a linked-list-set, but the idea applies to any other data structure (except for LROLLS which is more specific to link-list based data structures), i.e. you can use the same kind of ideas to create concurrent versions of other single-threaded data structures.
As always, source code is available on github:
LinkedListSet.h - A single-thread only linked list set. The Left-Right pattern uses two instances of this class to create a set with WFPO read-only operations
LROrderedLinkedList.h - LROLL: two LinkedListSet instances protected with the Left-Right pattern using a DCLC readIndicator
LROrderedLinkedListSingle.h - LROLLS: Less memory usage than LROLL and 2x faster insertions and removals
RWLockLinkedListDCLC.h - Uses a DCLCRWLock (based on C-RW-WP) to provide concurrent (blocking) access to a LinkedListSet
RWLockLinkedListPT.h - Uses a pthread_rwlock_t to provide concurrent (blocking) access to a LinkedListSet
RWLockLinkedListSM.h - Uses a std::shared_time_mutex to provide concurrent (blocking) access to a LinkedListSet
PS: Ohhhhh I almost forgot, if you're on C99 or C++99 (no memory model) then you can use the Double Instance Locking instead of the Left-Right in LROLL and LROLLS and obtain lock-free progress condition for read-only operations.
