CX - Wait-Free Universal Construction

After many years, we've decided to make public the source code for the CX Universal Construction and explain what it is. Source code can be obtained here: https://github.com/pramalhe/CX
and paper here: https://arxiv.org/abs/1911.01676

CX is the first wait-free Universal Construction that can actually be used in practice.
It can take lambdas for its operations, it has integrated (wait-free) memory reclamation, it was extensively tested and it doesn't leak.
CX allows you to take a sequential data structure or object (single-threaded code) and make a wait-free concurrent implementation of the same object by simply encapsulating the methods in calls to updateTx() or readTx(). The resulting data structures have linearizable operations.

Transforming a sequential data structure with CX is not trivial, but it is simple enough that a developer fresh out of college can do it. There are a few rules specific to wait-free UCs that need to be followed (no I/O, no exceptions, no side effects, deterministic code only) but these are easy enough to adhere to.

Unlike handmade wait-free and lock-free data structures, you can have any kind of type in your container (there are limitations on the return values though). All lock-free data structures I've seen so far were meant for integers only, or something equal or smaller than 64bits. Moreover, with CX it's easy to modify the data structure later and add more functionality.

Unlike STMs, CX does not need to have interposing and therefore, we can use CX to wrap data structures in libraries to which we don't have access to the source code. For example, you can use CX to wrap STL containers (we have!). Here is an example on how to make a wait-free std::set
https://github.com/pramalhe/CX/blob/master/examples/WFStdSet.hpp
or even easier, just create the instance and do the operations on the fly:
https://github.com/pramalhe/CX/blob/master/examples/example1.cpp

All you need is a copy constructor for the underlying data structure you want to protect. As long as your sequential data structure has a copy constructor (or something logically equivalent) and deterministic operations, you should be able to convert it to a wait-free data structure.

We've used CX to make the world's first wait-free balanced binary tree, with integrated wait-free memory reclamation, capable of supporting multiple types. How did we do that? Well, we wrapped a std::set in CX and BOOM, out comes the world's first wait-free balanced BST  :)


Several years ago, when Andreia first came up with the idea that we could use a reader-writer lock to achieve wait-freedom, I though that was crazy, but cool. After joining up forces with Pascal and a lot of work, we were able to turn that into a universal construction, CX.
Sure, it has its limitations, but it opens new venues for research and is evidence of some contrarian concepts:
- wait-freedom can be generic and fast (at least for read-mostly workloads);
- wait-free memory reclamation can be lightweight;
- wait-freedom can be achieved with locks;


Now for the bad news: just because it's wait-free, doesn't mean it scales.
CX serializes all mutative operations which means it's flat at best if the workload consists of only mutations on the sequential object.
It also consumes larges amounts of memory and in the very unlikely worst case, may require 2x MAX_THREADS replicas of the sequential object. If the object is a data structure with 1000 nodes, then it doesn't make a dent, but if we're talking about a container with multiple millions of keys and tens of threads writing to it, then it's going to chew up with DRAM pretty fast.
This high memory usage means CX likely won't be your favorite concurrency approach when deploying in production.

The good news is that it scales really well for read-only operations. This means that as long as your workload is read-mostly, it will be able to scale.
Synchronization for read-only operations in CX is very low, typically a few acquire-loads and a single seq-cst fence instruction and beyond that it's just regular loads.
Yes, that's right, the user-code you place in the lambdas is being executed without having to do any load acquires or heavy synchronization fences, just like when you execute code inside a lock!
This is what makes CX be very fast for read-mostly workloads.


In fact, it's so fast that when we submitted the paper to conferences, a few reviewers complained that it was too good to be true and it couldn't possibly be correct. That's how fast it is  ;)
Hand-made lock-free data structures can take months (or years) of work by expert researchers to complete, therefore it's normal be greeted with disbelief when we show them a technique capable of transforming generic sequential code into wait-free safe code. Something a young developer can do in minutes. If on top of that we say that it has wait-free memory reclamation and on top of it we show plots where it beats multiple handmade data structures in read-mostly scenarios, then they go ballistic and think it's all a bunch of BS.
It's understandable, we all have our biases. Mine is to think that it's a good idea to trade off large amounts of memory for a generic construct that scales in read-mostly workloads.What's yours?

Hey, nobody's perfect!

The difference between a Universal Construct and a Software Transactional Memory

In this post we're going to talk about Universal Constructs (UC), Software Transactional Memory (STM), the different between the two of them, and why it's not possible to have a UC for persistent memory.

Waaaiiiittt what?!?! It's not possible to have a Universal Construct for non-volatile memory?!? Why not?

The reason is at end of the post, first, like on all voyages, we start at the beginning.
Back in 1991, Maurice Herlihy (yes, it's the guy that wrote "The Art of Multiprocessor Programming" with Nir Shavit) decided he was tired of locks and blocking progress, and tired of dealing with errors in lock-free data structures, and he proposed a thing he called a "Universal Wait-Free Construct".
https://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf
You can see an implementation in Java of this UC in chapter 6 of his book.
A UC is a construct (an object) that wraps a sequential implementation of an underlying object (or data structure) and provides safe concurrent access to the underlying object. In the case of a universal wait-free construct, it provides wait-free access to the underlying object.

In other words, you can write a data structure as if it was single-threaded, and then, instead of slapping a lock on top of it (which is blocking), you slap a wait-free UC (which is wait-free) and booom! You get a wait-free data structure.
In hand-made lock-free and wait-free data structures, if you so much as modify a single line of code in them, they're likely going to break apart completely. On the other hand, when using a UC you don't have that problem, as long as the sequential implementation is still correct from a single-threaded point of view. It's as if we're decoupling the concurrency part from the actual object, while providing wait-free progress.


Hummm, so how come I've never heard of this "Universal Construct" thingy?!?

Well, the main reason is that completely wait-free UCs have been until now, extremely slow.
There are partially wait-free UCs, like Left-Right, which provides blocking (starvation-free) progress for writers and wait-free progress for readers. Left-Right is simple and pretty fast, but anything that provides wait-free progress for both readers and writers, is bound to be slow.
The reason behind this slow performance is related to the Copy-On-Write (COW) pattern behind almost all wait-free UCs. Wait-free UCs typically make an entire copy of the underlying object for every mutation. If the object is small, this will be fast, but if the "object" is a data structure with one million nodes, then its going to be super slow.
This means, that UCs are great for theoretical research, but not so great for making non-blocking data structures.
If you want to know more about this topic, then take a look at P-Sim which is probably the best know wait-free UC:
https://dl.acm.org/citation.cfm?id=2664096
or to our own UC named COWMutationQ which is simpler and has a similar performance:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/papers/cowmq-2015.pdf

UCs have a few peculiarities.
First, they can protect a single object, or if you prefer, they have a single root pointer from which all inner objects must be accessible. UCs allow for transactions to be made as long as the objects in that transaction are accessible from the same root pointer, and they must not be accessible from any other root pointer (in case you have other UC instances).
In other words, objects inside the UC have a 1-to-1 connection to the UC (as if it was a lock) and the wait-free UC provides wait-free progress with linearizable consistent for any operation being applied to the underlying object(s).
Second, for multiple objects to be protected by the same UC (as is the case of nodes in a data structure), there has to be a well defined way of copying those objects, what is called in C++ terminology a copy constructor. Without a copy-constructor, or something equivalent, you can't have data structures inside the UC. This pretty much leaves out low-level languages like C from having any practical usage for UCs, ohhh well.
Third, there is no annotation of the sequential implementation.
Let me repeat this one because it's going to be really important later in this post: The user does NOT have to annotate the sequential implementation of the underlying object that is put on the UC. None, Zero, Nada!
The whole point of the "Universal" part of UC is that it can be applied universally to any underlying object, without having to modify it in any way whatsoever.


And what does this have to do with STMs?

It turns out that Maurice is actually a pretty smart guy (should not be a surprise to anyone) and he figured out that if you relax some of these constraints you might be able to improve the performance.
So, only two years later, in 1993, him and JEB Moss coined the term "Transactional Memory" to describe a construct that can do pretty much the same as a UC but without the first and second constraint I mentioned on the paragraph above.
Granted, they originally though TMs were going to be deployed in hardware (HTM) and it's true that it eventually happened, but they also though it was going to be wait-free, and it's currently worse than blocking. For example, Intel's HTM doesn't guarantee any kind of progress.

In 1997, Nir Shavit and D. Touitou showed the first Software Transactional Memory (blocking). From then until now, many, many STMs have been created, but very few with lock-free progress, and I doubt any has been made with wait-free progress. Even if they do exist, they are likely to be just as slow as P-Sim and COWMutationQ.

I'm pretty sure Maurice has been a bit disappointed by this turnout of events. He must have been expecting someone to come up with a lock-free or wait-free STM that had some nice performance. In fact, I asked him about this on a conference once, and he said that "If someone could come up with a lock-free STM, then it would be something that's actually very useful". I could tell his eyes were sparkling as he said that  :)

The main disadvantage of STMs is that they require some kind of annotation of the underlying object(s). In other words, you can't just write a sequential implementation of a data structure, slap an STM on top of it and get concurrent access for free. Nope, you need to annotate or even modify (depending on the STM) some code of the sequential implementation.
Granted, the annotations are typically small, such as changing data types or calls to allocator or deallocator, but still, some work needs to be done by the user. The process is not automatic and it's not "universal".

Just to summarize:
- STMs can have multiple root pointers. UCs can have only one root pointer;
- STMs allow transactions between any object (allocated in the TM). Each UC can execute transactions only within the objects it protects;
- STMs don't need copy constructors. UCs need copy constructors or equivalent methods;
- STMs require annotation of the underlying object. UCs require no annotation or change to the sequential implementation;

Just to consolidate the idea: If it needs annotation, it's not a Universal Construct!


What about that stuff you said about not having UCs for persistent memory ?

Now we get to the insightful part.
Any code that modifies data in Non-Volatile Memory (NVM) must (currently) flush the cache lines after the modification. On x86 this is done with a CLFLUSH or CLFLUSHOPT or CLWB instructions.
The only way to do the flushing automatically is to have some kind of annotation, typically in the type of the variables modified. Yes, the compiler can hide that from me, but I still have to have a way of telling the compiler which data is volatile and which data is non-volatile, and that is typically done through type annotation. The compiler can't guess what data is meant to be persisted and what data is meant to be volatile, there is just no way for it to figure that one out because that is related to application logic, and by definition, only the user knows that. The only way around this is to have _everything_ be non-volatile, but that requires hardware which doesn't currently exist, and may not be an interesting programming model anyways.
This means, that the whole concept of "Universal Construct" kind of fades away when it comes to NVM, because the main point of having a UC, is not doing any change to the underlying code, but the only way to have a sequential (non persistent) implementation of an object be persistent, is to annotate it.
Of course, if they ever make an architecture where writing to NVM doesn't need to be flushed, then ok, it should be possible for someone to make a UC with persistence, but that's very unlikely to happen (the no-need-for-flushing-cpu-architecture).

In practice all of this is fine because we still have STMs, and STMs are particularly suited for working in NVM because they were designed to provide transactions. Having NVM is just an added bonus that can make the transactions persistent, which is great because it gives ACID.

Up until recently, STMs only had ACI, there was no Durability, but now with NVM, STMs can provide full ACID support, just like databases... and that is a game-changer.

Ultimately, whether you call it a UC or an STM depends on the interface that is being given to the user. If it needs annotation, it's not a UC. But then again, having to annotate a data structure is typically not too hard, therefore, it's fine to do it if you get some extra performance in return for that extra work.

An update: Actually, there is a way to make a universal construct for NVM, it's just a matter of flushing the entire memory region on each operation. So I guess I was wrong, yes, it is possible to have universal constructs for persistence, it's just that their performance will go down the drain if we have to flush the entire NVM region on every single transaction. Moral of the story, if you're into to persistence, better stick to STMs.

A Lock-Free Persistent Queue

Lock-free queues have been discovered many years ago, with the best-known and likely the simplest of all, being the one by Maged Michael and Michael Scott back in 1996
http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf

Nowadays, the trendy stuff is in mixing concurrency with persistence, and when I talk about persistence, I mean Non-Volatile Memory, or Storage-Class Memory, or NVDIMMs.

The simplest way to have a persistent queue is to take a transactional persistency engine, or PTM as I like to call it (Persistent Transactional Memory) and wrap a sequential queue implementation in it. An example is to use PMDK, which this CppCon presentation covers in some detail:

https://github.com/pmem/pmdk

However, PMDK and the other log-based techniques for consistent persistence are all lock-based. What if you want a lock-free data structure, something as simple as a queue?
Well then, you would be stuck, or at least until now you would be stuck  :)

A few top names got together recently and decided to make a persistent lock-free queue, likely based on the MS queue. I haven't read the paper because it isn't out yet, there is only a brief announcement online:
http://drops.dagstuhl.de/opus/volltexte/2017/7968/pdf/LIPIcs-DISC-2017-50.pdf
Their paper has been accepted to PPoPP 2018 so hopefully in a month it will be available somewhere.
Now these names are well known in Concurrency, I mean, we're talking about Maurice Herlihy (invented wait-free and linearizability) and Erez Petrank (him and Alex Kogan made the first MPMC wait-free queue), if these guys have decided to team up to make a queue, it's something worth noticing!

Although no lock-free persistent queue existed so far, since 2016 there was a kind of recipe provided by these other guys:
https://www.cs.rochester.edu/u/jhi1/papers/2016-spaa-transform
Notice that one of the authors is none other than Michael Scott, one of the authors of the original lock-free queue.
Their recipe to transform lock-free algorithms in persistent lock-free algorithms is simple and elegant, even if overkill for most usages.
On x86, you can think of a pwb as being a CLFLUSHOPT instruction, and the pfence or psync being an SFENCE instruction.
Basically:

• Add a pfence before every store-release and a pwb after;
• After every load-acquire add a pwb and then a pfence;
• Before and after every CAS/fetch_add/exchange add a pfence;

And that's it, it's so simple that even a compiler could do it for you... and probably one day a compiler will do it for you!

... or maybe it isn't so simple. Things are never as easy as they seem once you start to actual implement stuff.
You see, this automatic transformation works well in most lock-free cases (there are some for which it doesn't, but that's a subject for another post), but a lock-free queue is not just lock-free code, there is also the code in the constructor and the destructor, and that is sequential code.

Implicitly, the MS queue needs a head and tail (persistent) variables and they must be initialized to point to the same sentinel node.
We can't really expect this to happen magically in some atomic way. A failure may occur anywhere during the initialization, leaving these two variables in an inconsistent state, therefore, the initialization and de-initialization must follow a particular sequence, an algorithm.
In fact, this algorithm is quite complex, and I would say is the trickiest part of getting a correct persistent lock-free queue implementation.
Hopefully, that is what Maurice, Erez, Virendra and Michal will show in their paper next month at PPoPP 2018, but until then, here is my take on it, available on github:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/pqueues/PMichaelScottQueue.hpp

Andreia and I discussed a bit about this and I've done a very preliminary implementation of a persistent lock-free queue.
First, we followed the transformation rules with pwb/pfence/psync, but they add too many fences. Andreia is awesome at reducing algorithms to their bare essentials and I gave some contribution as well, the end result being we got rid of most pfences.
This algorithm was designed such that on enqueue(), a successful CAS on ltail->next implies that the pwbs for newNode->item, newNode->next and tail have been done, and a successful CAS on tail means that the pwb on ltail->next has been done. This kind of happens-before implicit guarantee means the queue is always in (at worst) a semi-consistent state, which the next operation can safely recover from, without the need for an explicit recovery method.

Here is the code for enqueue(), and yes, it's just the MS algorithm plus some strategically placed persistence fences and pwbs  ;)
void enqueue(T* item, const int tid) {
    if (item == nullptr) throw std::invalid_argument("item can not be nullptr");
    Node* newNode = new Node(item);   // TODO: replace this with NVM allocator
    PWB(&newNode->item);
    PWB(&newNode->next); // Just in case 'item' and 'next' are not on the same cache line
    while (true) {
        Node* ltail = hp->protectPtr(kHpTail, tail, tid);
        if (ltail == tail.load()) {
            Node* lnext = ltail->next.load();
            if (lnext == nullptr) {
                PWB(&tail);
                if (ltail->casNext(nullptr, newNode)) {
                    PWB(&ltail->next);
                    casTail(ltail, newNode);
                    PWB(&tail);
                    PSYNC();
                    hp->clear(tid);
                    return;
                }
            } else {
                PWB(&ltail->next);
                casTail(ltail, lnext);
            }
        }
    }
}

And here is the code for dequeue()
T* dequeue(const int tid) {
    Node* node = hp->protect(kHpHead, head, tid);
    while (node != tail.load()) {
        Node* lnext = hp->protect(kHpNext, node->next, tid);
        PWB(&tail);
        PWB(&head);
        if (casHead(node, lnext)) {
            PWB(&head);
            PSYNC();
            T* item = lnext->item;  
            hp->clear(tid);
            hp->retire(node, tid); 
            return item;
        }
        node = hp->protect(kHpHead, head, tid);
    }
    hp->clear(tid);
    return nullptr;                  // Queue is empty
}

The bold fonts show the added fences needed to guarantee persistency. In fact, this queue is not just durable, it is Durable Linearizable, which is (in my view) the easiest model to reason about for durability, as important to Persistence as Linearizability is important to Concurrency.

The reason the pfences were taken out is because we're assuming that CAS has persistent semantics similar to pfence that doesn't act on the load/store of the CAS itself, only on the other loads and stores. In other words, it's as if a CAS is equivalent to a:
  PFENCE();
  CAS()     // concurrent
  PFENCE();
The reason we assume this, is because on x86, LOCK instructions and read-modify-write instructions like CAS, ensure order for CLFLUSHOPT and CLWB (pwbs). For more details see Intel's manual for CLFLUSHOPT:
https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf

As for the pwb and psync before returning, they're not always needed but it helps to reason about in terms of composability.
The only way to observe effects from this queue is to call enqueue() or dequeue(), therefore, the next call to the same method will flush the cache line and persist it. However, if you want to do something like:
   q.enqueue(a);
   a_is_persisted = true;
   PWB(&a_is_persisted);
then the only way to guarantee correct ordering of a_is_persisted with the element 'a' actually being in the queue and persistent, is to have the pwb and a psync (or pfence) before returning from enqueue()/dequeue().


Adding the persistence fences and then reducing them to a minimum was the easy part. The though part is gluing that together with the constructor and destructor that recovers after failure.
Here is what the constructor and destructor look like:
PMichaelScottQueue() {
    PWB(&head);
    PWB(&tail);
    PFENCE();
    recover();  // re-use the same code as the recovery method
}

~PMichaelScottQueue() {
    destructorInProgress = true;
    PWB(&destructorInProgress);
    PFENCE();
    recover();  // Re-use the same code as in the recovery method
}

Simple huh?... not so fast, now we need to show the recover() method:
void recover() {
    if (destructorInProgress) {
        if (head.load(std::memory_order_relaxed) != nullptr) {
            while (dequeue(0) != nullptr); // Drain the queue
            head.store(nullptr, std::memory_order_relaxed);
            PWB(&head);
            PFENCE();
            delete head.load(std::memory_order_relaxed);  // Delete the last node    // TODO: replace this with NVM deallocator
        }
        PSYNC();
        return;
    }
    hp = new HazardPointers<Node>{2, maxThreads};
    // If both head is null then a failure occurred during constructor
    if (head.load(std::memory_order_relaxed) == nullptr) {
        Node* sentinelNode = new Node(nullptr);    // TODO: replace this with NVM allocator
        head.store(sentinelNode, std::memory_order_relaxed);
        PWB(&head);
        PFENCE();
    }
    // If tail is null, then fix it by setting it to head
    if (tail.load(std::memory_order_relaxed) == nullptr) {
        tail.store(head.load(std::memory_order_relaxed), std::memory_order_relaxed);
        PWB(&tail);
        PFENCE();
    }
    // Advance the tail if needed
    Node* ltail = tail.load(std::memory_order_relaxed);
    Node* lnext = ltail->next.load(std::memory_order_relaxed);
    if (lnext != nullptr) {
        tail.store(lnext, std::memory_order_relaxed);
        PWB(&tail);
    }
    PSYNC();
}

Yep, now things are starting to get complicated, which I'm not a big fan of, but it's as good as I can get it  :(
Hopefully the approach which will be shown at PPoPP will be simpler than this.

About the constructor:
As long as the allocator returns a zeroed-out memory region, the 'head' and 'tail' will be nullptr even if there is a crash immediately at the start of the call to the constructor. If the allocator can't guarantee that the data is zero-ed out, then there is no 100% safe way to distinguish between a proper initialization and trash immediately after allocating the queue.
A crash occurring after the 'head' and 'tail' are made persistent (with nullptr) is always recoverable, although there are a few different cases:
- If the head is nullptr then the sentinel node must be allocated;
- If the head is non-null but tail is null, then the sentinel was allocated and assigned to head but not to tail;
- If both head and tail are non-null and tail->next is non-null then tail is not pointing to the last node and we need to advance tail;

About the destructor:
The destructor must first drain the queue to avoid leaking as much as possible. Then, it needs to de-allocate the last node and zero-out the head to make sure then in the event of a failure, the recovery operation will not try to "recover" the queue, therefore, we have a persistent variable named 'destructorInProgress' which is set before starting the destruction operation.
After destructorInProgress has been set to true and ordered with a pfence, we can clear head, and only then can we de-allocate the last node.


How fast is it?
Well, on DRAM emulating NVDIMMs, implementing pwb/pfence/psync as CLFLUSHOPT/SFENCE/SFENCE, we get some not too bad results when compared with the regular MS queue:



For the most attentive of you, this queue seems to have slightly better performance than the one shown in this brief announcement:
http://drops.dagstuhl.de/opus/volltexte/2017/7968/pdf/LIPIcs-DISC-2017-50.pdf
however, our implementation has integrated memory reclamation which may be acting as a kind of back-off... or maybe we have a smaller number of fences. Whatever the reason, when the other queue is out in a month I'll try to re-run the benchmark to compare them  ;)
Btw, our synthetic benchmark is very simplistic: do an enqueue, followed by a dequeue, and then repeat 10 million times. I'm not a big fan of this benchmark but it's what everybody uses in academic papers to measure queue performance, so that's what we use too.


One last note, all allocation and de-allocation operations in this queue are prone to leaking, if the failure occurs immediately before a de-allocation or immediately after an allocation. There is no way around this problem without transactions, and seen as we're trying to get lock-free progress, the transactional mechanism would have to be also lock-free, and there is no lock-free PTM published (yet).
I'm not the only one complaining about this. Paul McKenney points this out as being one of the fallacies in the "lock-free data structures are resilient" argument, typically touted as one of the advantages for lock-free (by myself included). Maurice Herlihy has some interesting stuff to say around that topic as well:
https://www.youtube.com/watch?v=94ieceVxSHs&t=44m40s



We'll talk more about transactions in a future post, for today that's all. In the meantime, have fun with the code:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/pqueues/PMichaelScottQueue.hpp

Dawn of the Universal Constructs

Historical Introduction

Some time ago I saw this nice presentation by Andrei Alexandrescu about Generic Locking.
https://www.youtube.com/watch?v=ozOgzlxIsdg
He starts the talk by giving an introduction to how the "Concurrency Problem" has been attacked.

And what is the "Concurrency Problem" you might ask?
Well, remember this little issue about Moore's Law (on CPU clock speed) having stopped back in 2004 and that nowadays to get more performance you need to use multiple cores, which means using some form of concurrency? Yeah, that's the "Concurrency Problem"!
Sure, if you can write your application or algorithms in a map-reduce form, then you can parallelize it, but not all algorithms are inherently parallel to profit from this approach, and those are the ones we need to worry about.

As Andrei says in his presentation, in the beginning there were mutual exclusion locks, and those were pretty much the only way to deal with concurrency.
Then came reader-writer locks, lock-free and wait-free data structures, CSP, Actor Models, Software Transactional Memory, Hardware Transactional Memory and many others.
For a while, lock-free and wait-free data structures seemed to be the thing, but the fact that there wasn't a memory model to program them in, and that it was very hard to verify their correctness, and very hard to do efficient lock-free memory reclamation (wait-free is even harder), it caused people to try the other approaches. Nowadays, there is no clear winner, and maybe there never will be. Actor models have been gaining a lot of followers, with the whole Rx/Reactive movement based on it... I'm not sure they all realize that at the base of the actor model is the message-passing queue between the actors which is itself based on a lock-free queue.

Anyways, fast-forwarding to 2017, one of the upcoming CppCon talks which will definitly be worth watching, is the one by Paul McKennney, Maged Michael and Michael Wong:
https://cppcon2017.sched.com/event/Bgtm/the-landscape-of-parallel-programming-models-is-it-still-hard-or-just-ok-part-1-of-2?iframe=no&w=100%&sidebar=no&bg=no
As they mention in the abstract, there was a time when writing a simple loop seemed as perilous then as writing a lock-free data structure seems now.
I don't know what their talk will be about, but I do agree that most of the dangers in concurrent programming can be avoided by using better programming tools, and on that note, I would dare go so far as to say that we're entering "The Dawn of the Universal Constructs"!

What is a Universal Construct

Universal Constructs aren't a new thing. The first Wait-Free Universal Construct (WFUC) was invented by Maurice Herlihy back in 1993:
http://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/p745-herlihy.pdf
WFUCs are a construction that encapsulate an object (or data structure) which was written for single-threaded usage, and provide a way to call its methods with wait-free progress.
It's kind of like wrapping all the methods in an object with a call to lock()/unlock() of a mutual exclusion lock, except that a lock is blocking while WFUC are, well, wait-free!



In summary, a Wait-Free Universal Construct lets you write your favorite data structure as if it was "single-threaded code" and then wraps its methods to provide wait-free progress.
If you saw Andrei's presentation at the beginning of the post, you'll know that he has a cool way (in C++) of automatically exporting the methods of an object/data-structure wrapped with a read-lock or a write-lock depending on whether the methods are mutative or read-only. The same kind of approach can be done with WFUCs, which means that they are truly generic.

How come I never heard of this before?

Well, you kind of have heard about this (if you read this blog).
Left-Right for example, is a Universal Construct that provides wait-free progress for readers and blocking (starvation-free) progress for writers:
http://concurrencyfreaks.blogspot.nl/2013/12/left-right-concurrency-control.html
It's fast, it reclaims memory, it's "universal", but it's not completely wait-free, i.e. it's not wait-free for mutations.

There are truly WFUCs in the literature and we've even added (wait-free) memory reclamation to a few of them. The most famous being P-Sim by Panagiota Fatourou and Nikolaos Kallimanis:
http://thalis.cs.uoi.gr/tech_reports/publications/TR2011-01.pdf

But even the best of them still works on the COW principle, in the sense that it requires a full copy of the data structure for every mutation.
Yes, that's right, if we have a map with 1M keys/values, and we want to insert a new key (or remove an existing one), we have to make a full copy of the 1M nodes of the data structure.

Waaaaiiiit wwwhhhaaat? Did you just say that this thingy has to copy 1 million nodes every time I want to insert a new key/value in my hashmap?

Yes, I'm afraid that's how it works. It's not as bad as it looks if the data structure is small, but as soon as you start going to anything bigger than a few thousand nodes in the data structure, throughput is going to go down the drain. And cache locality is a big issue with COW.

What's on the horizon

I happen to have insider knowledge that it is possible to make a wait-free universal construct that is fast enough to be used in production, because it doesn't have to copy the entire data structure (except on very rare occasions). This new way of doing WFUCs is fast enough to be used in real-life applications, in fact, it's capable of beating hand-written lock-free and wait-free data structures.
Yes, it's that good. We call it CX and the paper is almost ready.
... did I say it does wait-free memory reclamation as well?  ;)

As soon as other researchers see what CX is capable of, I'm sure they will have their own ideas and improve upon it, thus bringing about a new age of production-capable WFUCs.

Going back to the Concurrency Problem, how does this change the way we program multi-threaded applications?

Based on my experience as a developer, software engineers rarely use an off-the-shelf data structure as is. We always add a little twist to it.
I don't know whether this happens due to us having big egos and wanting to give our little personal touch to everything we do (I'm generalizing here), or if it's simply because we're tinkerers and we like to see what's under the hood and tweak it to our own desire. the truth is, if we could use it as is then there wouldn't be a need to write all the software people write, there would be just one search engine, just one banking software, just one customer management software, etc.

Whatever the reason may be, the consequence is, that we always make changes to the data structures, and the problem with that, is that lock-free and wait-free data structures will fall apart if they're touched. They have sequences of instructions that have to be done in a particular way, they have optimizations for relaxed memory orderings and subtle details, and memory reclamation, etc, etc. The temptation to touch and tinker a lock-free data structure is just too much, and we end up getting burned and then we say that "lock-free data structures suck", which is not true.
The algorithms behind these data structures are very subtle, and our human nature is to tinker with it, which is incompatible.

This is where Wait-Free Universal Constructs come in.
With an efficient WFUC, any software engineer without any knowledge of lock-free data structures (or atomics or the memory model) can just take a "single-threaded data structure", modify it to satisfy its needs (or ego) and then wrap it with WFUC and BOOOOM, out comes a fast and scalable implementation of its customized data structure, with wait-free progress.
Even more, another software engineer working on the code can later fix bugs or add new features to the data structure without breaking its correct functionality. Try doing that with a lock-free data structure, it's hard enough to get it right the first time, to add new functionality later is just too nuts.
As a software engineer, what more could I ask for?

No wonder that WFUCs are seen by researchers as the Holy Grail of concurrency, it's because they make it so easy to solve the Concurrency Problem in production.
Yes, I'm a fan boy of Universal Constructs, but the hype is called for and needed. This stuff doesn't solve all the concurrency problems, but it solves a a lot of them, enough to become a standard way of dealing with multi-threaded code, or at least for writing multi-threaded data structures.

Whatever happens, Universal Constructs are here to stay as one of the easiest tools to use when writing multi-threaded applications, and we all know that when it comes to multi-threaded programs, any help we can get is not enough  ;)