A Relaxed Guide do memory_order_relaxed

 Just a quick post to a nice presentation on relaxed atomics by Hans Boehm and Paul McKenney

https://www.youtube.com/watch?v=cWkUqK71DZ0

Very instructive if you are designing locks or lock-free code.

Full PRD here http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2055r0.pdf

Is Parallel Programming still hard?

CppCon 2017 is over and some of the talks are starting to trickle in.
One that is definitely worth watching is the one by Michael Wong, Paul McKenney and Maged Michael. If you don't know who these guys are then go and read this post.

Here are the two videos:

My favorite quote from the talk:
"It is possible to split atoms, but doing that spoils them for electronics use".

Nice intro to false sharing, store buffers and caches. All of those are hardware details that (unfortunately) are important in multi-threaded programming, and are rarely talked about.
 
About the Reader-Writer Lock slides (a subject I've dug deep into with Andreia), there is a much simpler way than using a TLS RW-Lock, namely the scalable reader-writer locks. More info can be seen on this post:
http://concurrencyfreaks.blogspot.nl/2015/01/scalable-reader-writer-lock-in-c1x.html

Let's see what the next talks will be about...

Why is memory reclamation so important?

As it so happens, object lifetime tracking (or Memory Reclamation as I prefer to call it) is the current most difficult open problem in shared memory concurrency.
If you want to design or implement a lock-free or wait-free data structure, the hardest part isn't designing/implementing the data structure itself. The hardest task is to add memory reclamation to this data structure, without reducing the progress or throughput of the data structure you designed/implemented.

Huhhhh wait, are you saying that implementing a lock-free data structure is easy when compared to memory reclamation? Wwwhhaaaat?!?
No, I'm only saying that memory reclamation is even harder  :)
Let me try to explain why, and there are four reasons behind it:

Reason number 1, progress

So let's say you designed/implemented/found-on-github a non-blocking data structure to serve your needs, but this data structure comes without memory reclamation, and unless you're on a language with a Garbage Collector, you now come face to face with the problem of adding memory reclamation to it.
Think of it this way, what is the purpose of going through all the trouble of doing lock-free/wait-free stuff if then you end up having to slap a blocking mechanism on top of it?
Obviously, it would be kind of fruitless to put a blocking memory reclamation on top of a non-blocking data structure because the end result would be blocking.
This implies that whatever memory reclamation you're going to use on your favorite data structure, needs to have at least the same progress guarantees as the data structure. If not, then all that work that went into designing/implementing a lock-free data structure, just goes down the drain, and you might as well go back to using a global lock, which has low overhead and provides safe memory reclamation (just grab the lock before calling delete/free on nodes of the data structure).

Btw, even if you have a GC, no known GC is lock-free (much less wait-free), so you don't really have non-blocking guarantees of progress. Just take a look at the previous post with Erez Petrank's presentation.

Reason number 2, throughput

When we use a non-blocking data structure, whether lock-free or wait-free, one of the goals is to achieve more performance. By performance I mean either more throughput, or lower tail latency, or both.
Typically, as developers, what we want from these data structures is to have higher throughput as the number of threads working on the data structure increases, and maybe we also care that the tail latency stays low. If we didn't care about one or both of these things, then we could just protect whatever single-threaded data structure we needed to use, with one global lock and be done with it, but as everyone knows, this doesn't scale.

Progress is not enough, if the lock-free data structure you're using is fast, then you need a memory reclamation technique that is at least as fast as it, so as to not become the bottleneck.
What is the purpose of having a super-duper fast lock-free data structure if then you slap on top of it a lock-free-but-horribly-slow memory reclamation technique which drags down performance? Well ok, you may still have the progress guarantee, which will give you low tail latency for wait-free data structures with wait-free memory reclamation, but really... if it's slow, will you use it?

Reason number 3, simplicity

When we apply a memory reclamation on top of a pre-existing non-blocking data structure, we want it to be as simple as possible. The simpler it is, the less likely it we will be that we make mistakes. Unfortunately, most memory reclamation techniques are hard to deploy on pre-existing data structures.
I've previously wrote an entire post explaining just how hard it can be for Hazard Pointers and how much easier it is for URCUs:
http://concurrencyfreaks.blogspot.com/2016/08/hazard-pointers-vs-rcu.html

The jist of it is, that it requires expert knowledge about the data structure where the memory reclamation is being applied, so expert that most data structure designers/researchers don't bother to add memory reclamation to their data structures. They claim it's "an implementation detail", but I know better, it's because it's really hard. Don't take it the wrong way, it's not that they aren't smart enough, it's just that this kind of work is not valued in academia, therefore, there is no incentive for them to waste precious space in their articles explaining how to make a data structure that is actually deployable in a production setting.  Not to mention spending brain power thinking about it (it's true, it always gives me a headache).
And if you're convinced that things like Hazard Pointers can be tricky to use, well then, it can be even more complex, for techniques like Drop The Anchor.

Reason number 4, resilience

Another reason to go with lock-free/wait-free data structures is because they are resilient to failures. On a shared memory system with multiples processes accessing the same data structure, even if one of the processes dies, the others will be able to progress in their work. This is the true gem of lock-free data structures: progress in the presence of failure.
Blocking data structures (typically) do not have this property (there are exceptions though).
If we add a blocking memory reclamation (like URCU) to a lock-free/wait-free data structure, we are loosing this resilience because one dead process will prevent further memory reclamation and eventually bring down the whole system.
There goes the resilience advantage out the window.

The three families of memory reclamation

Manual memory reclamation comes in one of three flavors: Atomic reference counting, quiescent-based, pointer-based.
All memory reclamation techniques belong to (at least) one of these families. Many memory reclamation algorithms exist but we'll focus only on the ones that can be implemented using the C++ memory model and atomics.

Atomic Reference Counting is just what the name says, it's a "reference counting" technique but with atomics. The details are a bit more tricky than your usual reference counting (aka smart pointers), but it's still graspable for most. They can be implemented in a wait-free way (in x86) but they have two main drawbacks: they're slow and they aren't universal.
They're slow because whenever we have to traverse a list of nodes we need to atomically increment a counter in one node and decrement a counter in another... even though we're just reading.
They're not universal because of several reasons, most of them described in section 9.1 of Paul McKenney's excellent book
https://www.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook-e1.pdf

Quiescent-based is where Epoch-Based-Reclamation (EBR) and all Userspace RCUs belong. The fastest memory reclamation is here (for readers). These methods tend to have very little synchronization, are easy to deploy in nearly all algorithms (i.e. data structures) and they're easy to understand.
When everything goes well, these are the fastest way of doing memory reclamation.
The downside is that they're blocking for memory reclamation. This isn't a simple limitation of the current algorithms that someone will one day be able to crack. Nope, it's something intrinsic to this approach. Reclamation with EBR or URCU is, and always will be, inherently blocking.

Pointer-based is where Hazard Pointers, Pass The Buck, Drop The Anchor and Hazard Eras belong. Pointer-based, well, they're not too hard to implement, but they can be extremely tricky to deploy. Their main problem is they're slow (though faster than atomic reference counting).
They can be completely wait-free, for readers and reclaimers. In case you didn't notice, this makes them the only family that can be used generically and capable of providing lock-free/wait-free progress.
Hazard Eras are the fastest of these, approaching (and in some scenarios surpassing) the best URCUs, but they do it at a cost in memory usage. It's the typical trade-off memory vs CPU.

You may notice that most (ok, almost all) academic papers on non-blocking data structures don't mention memory reclamation anywhere, or just briefly mention it in one sentence. This is because they would need many pages to detail all the intricacies of adapting such algorithm to have safe memory reclamation. Their typical approach is to say "That's not my problem, I'm just designing the algorithm. Memory Reclamation is an implementation detail."
... an "implementation detail", yeah, right.

Going back to our four reasons why memory reclamation is a hard problem (progress, performance, simplicity, resilience), if we look at the three families and compare some of the techniques of each family we see their advantages/disadavantages.


In the end there is no one solution fits all and it's highly unlikely that there ever will be. As always in engineering (software or not) some solutions are better in some scenarios and others in different scenarios. Though I have to say that Hazard Eras works well for scenarios with traversal of linked lists.

Wrapping up

The point I'm trying to make is the following: The fact that the memory reclamation technique needs to have the same progress (or better) as the data structure where you're using it, means that for fully lock-free or wait-free data structures the only true solution is to use pointer-based memory reclamation. Moreover, if we want the data structure to be fast, we need the memory reclamation needs to be just as fast (on top of having the same progress).

Let me be super clear on this. As of this writing, and likely for all eternity, the biggest bottleneck on deploying a lock-free or wait-free data structure is the memory reclamation technique.
If you think about it, a memory reclamation technique that is wait-free, must itself be composed of one or several data structures, likely to have wait-free progress, so we're stuck in a catch-22 where we want to make wait-free data structures faster, but we need to use (other) wait-free data structures to protect those wait-free data structures.

To end on a positive note, yes it's sad we likely can't make memory reclamation any faster than URCU or Hazard Eras, but we can certainly make it easier to use, and that's one of the things Andreia and I are working on. More on this in a future post  ;)

What is Eventual Consistency ?

On this post we're going to talk about Eventual Consistency in the context of lock-free and wait-free data structures, with focus on the C++ memory model, although most (or all) of what we're going to cover also applies to other memory models likes the ones in D, Java , Rust, C11, <insert language here>.
If you're looking for an explanation on what Eventual Consistency is in the context of databases then this (may or) may not be what you're looking for!

Before we explain what is eventual consistency in C++, we need to explain a little of what shared memory is and a what is a memory model.
Computers do many things: arithmetic computations, decide different things based on logical expressions, sending and receiving packets, putting pixels on a screen, etc. For this post, we care about reading from main memory and writing to main memory. This means "loads" and "stores".
The whole C++ memory model is about what happens when you do loads and stores from different threads, and all the other stuff that the computer does is pretty much out of the picture.
Obviously, stores are used to store a value in a certain memory location, and loads are used to read a value from a given memory location:
    x.store(value);
    value = x.load();

Also, from the memory model's point of view, all loads are indistinguishable, and so are all stores. CPU vendors have peculiarities, like some stores may re-order but others not (think stores on the same cache line), but the memory model doesn't really care about that, so for this post, we won't care either.

Ok, so this was really important. If you're not convinced that everything is about loads and stores then you better go and read the memory model of your favorite language and then come back.
Let me say it once more: It's all about loads and stores.


Combinatorically, if we have two different operations (loads and stores) we can define ordering constraints based on four cases:
1. A load may not reorder with a subsequent load;
2. A store may not reorder with a subsequent store;
3. A load may not reorder with a subsequent store;
4. A store may not reorder with a subsequent load;

When none of the four constraints above are set, and if we want to share data among threads or processes (remember, our context is lock-free and wait-free data structures) then in C++ this is called memory_order_relaxed. In this memory ordering any loads can reorder with any stores. Whatever the order of the code you wrote, the compiler may decide to reorder the loads and stores in whatever way it thinks is the best.
This has reduced synchronization and gives a lot of leeway to the compiler, thus resulting in high performance code. The downside is that most lock-free and wait-free algorithms were designed with a specific order in mind, and when this order is not respected, the algorithm no longer works.

To enforce constraint 1, the first load has to be done with a memory_order_acquire or memory_order_seq_cst. In the C++ memory model, loads with memory_order_acquire can not be reordered with any subsequent load or store. Most of today's CPUs enforce this constraint by default already, which means that it needs no synchronization as well.

To enforce constraint 2, the second store has to be done with a memory_order_release or memory_order_seq_cst. In the C++ memory model, stores with a memory_order_release can not be reordered with any previous load or store. CPUs with Total-Store-Order (TSO) like x86, enforce this constraint by default already, which means it needs no explicit synchronization. In practice the CPU internally has synchronization to achieve this strong ordering, but that's out of scope.

To enforce constraint 3, the first load has to be done with memory_order_acquire or memory_order_seq_cst. x86 CPUs provide this guarantee without explicit synchronization (barriers/fences).

To enforce constraint 4, both the load and the store have to be memory_order_seq_cst. No practical CPU provides this by default (such a CPU would be too slow) and to have such a constraint requires costly synchronization, typically a full fence or at least a store-load fence.
Explaining why this requires such high synchronization would require an entire (large) post about this topic, so let's just accept it as it is.

To sum it up, if we want all four constraints, we have to use sequentially consistent memory ordering, while if we want only the first three constraints, then the acquire-release memory ordering is enough.
Notice that stores and loads are done at the word level, 64 bits let's say. Therefore, when we talk about sequential consistency we are talking about it at the word level. Any object bigger than one word and this guarantee disappears because it will take multiple stores (or multiple loads) to modify (or read) such an object.


So what about eventual consistency?
Roughly speaking, eventual consistency guarantees if no new updates (stores) are made to a data item (word), then eventually all accesses (loads) to that item (word) will return the last updated value.
In other words, if we stop doing stores in a certain variable, eventually, when we go and read it from another thread, we will see the last store that was made. Pop quiz: which memory ordering is the weakest that gives this guarantee?
Answer: It's memory_order_relaxed (memory_order_acq_rel and memory_order_seq_cst also provide this guarantee but at a greater cost).
You see, something I didn't say about memory_order_relaxed is that the end result must look like the code you wrote, which means that eventually it will have to keep whatever was the last store you wrote in your code. This is highly non-obvious from reading the specs, but that's how it works, otherwise it would let the compiler produce incorrect programs, even in single-threaded code.


Ok, so now that we know that in C++ memory_order_relaxed provides eventual consistency (at the word level), what can we do with that?
Well, the answer to that depends on how useful you think that eventual consistency is.
The term eventual consistency is meant as a consistency property of an item, or object in C++ parlance. If the object is the size of a word (64 bits or less) then just make it atomic<> and all stores and loads to/from it must be changed to use memory_order_relaxed.
If the object is larger than a word then things start to get more complicated because then we could have concurrent stores touching different words of the object and it would leave it in an inconsistent state. Example below:
struct myobject {
    atomic<uint64_t> a {0};  // Consistency for this object implies that a is equal to b
    atomic<uint64_t> b {0};
}

myobject obj;

Thread 1:
    obj.a.store(1, memory_order_relaxed);
    obj.b.store(1, memory_order_relaxed);
   
Thread 2:
    obj.a.store(2, memory_order_relaxed);  // May occur before a.store() in thread 1
    obj.b.store(2, memory_order_relaxed);  // May occur after b.store() in thread 1
   
Thread 3:
    while (true) {
        if (obj.a.load() == obj.b.load()) break; // This may loop forever
    }   
   
In the above example, we defined the object to be consistent when having a and b members equal. The stores with Thread 1 may interleave with the stores in Thread 2, causing the object to be left in a inconsistent state permanently, with a=1 and b=2, which is not eventually consistent because the stores on the object have stopped but thread 3 will be in an infinite loop waiting for the object to be consistent.


Even without going into the topic of whether or when is eventual consistency useful, we still have to care about a subtle but extremely important detail in the definition of eventual consistency: it refers to an object.
Let me say this again because it's important: Eventual Consistency requires you to define the item (or object) on where this consistency is being applied.
This means that what you define to be the object affects the consistency.
Saying that you provide eventual consistency in your application is completely irrelevant unless you define at which granularity level you're providing such a guarantee.
If you're providing eventual consistency at the word level, then it's easy to implement, just make all accesses memory_order_relaxed;
If it's eventual consistent at the C++ object level, then each object must itself be atomic<>, which means that the underlying implementation is using a mutual exclusion lock to protect it, thus denying any benefit from doing eventual consistency. You might has well say you're providing strong consistency because you are in fact providing linearizability (at the object level);

In the context of data structures, if we say that a data structure is eventually consistent, it still needs to be atomic itself and all its nodes/whatever constitutes it. This means that the data structure itself needs to be consistent, or atomic. This is extremely hard to achieve without going into a fully linearizable (or at least sequentially consistent) algorithm, so perhaps this is not very useful in practice.

However, if we have multiple data structure instances, even if each of them is linearizable, doing operations or two or more of these data structures is not trivial to make them appear atomic (unless we're protecting everything with a global lock, or using a transactional memory). In such case, we can simply say that we're providing eventual consistency at the data structure level, and it would be correct to say so, because in each data structure instance we provide atomicity (linearizable consistency) but across data structure instances we only guarantee that eventually the modifications will be seen over all the instances.

If you take anything away from this post it should be this:
Eventual Consistency only makes sense when we define what is the "object" where this consistency is being applied.

Nitsan Wakart on Lock-Free Queues

About a year ago Nitsan Wakart gave a very nice presentation about lock-free queues
Here is the link to vimeo:  https://vimeo.com/131688512

Nitsan works for Azul Systems and he has a blog named Psy-Lobotomy-Saw.

If you're into non-blocking queues then make sure not to miss out this video because it has lots of interesting facts.
Some of the topics he covers are:

• The difficulty in running proper benchmarks for lock-free queues. IMO the hardest to obtain is determinism.
• What is throughput on a queue? single-enqueue-single-dequeue or bursts?
• Throughput vs Latency.
• Benchmarking empty queues vs non-empty.
• Warmup on benchmarks.
• Memory Bounded (circular array or ring buffer) vs Memory Unbounded (singly-linked list).
• When can we discard the volatile keyword in Java Queues (hint: very rarely), and even some of the masters have made this mistake.
• False Sharing.

Concurrency talks at CppCon 2016

The program for CppCon 2016 is out and there are some really interesting talks coming up.
On the topic of Concurrency, I'm looking forward to these three talks:
- JF Bastien on "No Sane Compiler would optimize atomics"
- Hans Boehm on "Using weakly ordered C++ atomics correctly"
- Paul McKenney on "A lock-free concurrency toolkit for deferred reclamation and optimistic speculation"

JF Bastien has some really good insights into optimizing code with atomics and the different memory orders, so I really want to see what he's going to say this year.
If you don't know who he is, then take a look at his interview from last year's CppCon or from CppCast:
http://concurrencyfreaks.blogspot.pt/2015/11/interviews-for-channel9.html
http://cppcast.com/2015/07/jf-bastien/
and a preview of what his presentation will look like:
https://github.com/boostcon/cppnow_presentations_2016/blob/master/03_friday/no_sane_compiler_would_optimize_atomics.pdf
and if you want to see some funny comments then check the last 10 minutes of this talk where JF Bastien gives some comments to the speaker:
https://www.youtube.com/watch?v=k12BJGSc2Nc

As for Hans Boehm, well, if you're a regular reader from this blog I shouldn't need to introduce him, but in case you just landed here by accident, then he's one of the contributors to the C++ Memory Model... and the Java Memory Model.
This year he's at CppCon and he's going to talk about common mistakes with non seq-cst atomics, so I definitely want to see his talk.
Here is some of the content he's going to go over:
https://docs.google.com/presentation/d/1Eapu4G6QcetO9mOeZSQJAuvxB8kK3pHQwxWbHNOLk8w/pub?start=false&loop=false&delayms=3000#slide=id.p
Funny thing, I was considering giving a talk this year precisely about this topic but I'm not able to go to CppCon so I didn't even submit the proposal. Obviously, I wouldn't expect my talk to be as good as his is going to be, I was thinking of focusing more on examples and what kind of optimizations are safe to do when writing an algorithm using C++ atomics.
... ohh well, maybe I can still propose it next year as a more "hands-on-approach".

And finally, Paul McKenney is going to to give two talks, with the first one being about the Issaquah challenge (which he talked about a couple years ago so I hope he's going to go a bit more in depth this time)
https://www.youtube.com/watch?v=1Q-RH2tiyt0
and the second talk is going to be about safe memory reclamation in concurrency.
It looks like Paul, Michael Wong and Maged Michael are trying to add techniques for safe memory reclamation to the C++ standard, namely, adding RCU and Hazard Pointers.
For those of you who don't know what this means, let me just say that most experts in Concurrency (shared memory concurrency) say that Memory Reclamation is the toughest problem in Concurrency. This includes people like Maurice Herlihy, Erez Petrank, and many others.
If Memory Reclamation is the toughest problem in Concurrency, and Concurrency is the toughest way of programming, then Memory Reclamation must be the hardest thing you can do in Programming.

There are three main ways to do memory reclamation in concurrent (non-blocking) applications: Atomic Reference Counters, RCU, and Hazard Pointers (HP).
They have different properties, like different progress conditions for Readers and Reclaimers. By "Readers" I mean the threads calling methods that don't delete anything in the data structure, and "Reclaimers" are the ones doing the deletions.

Atomic Reference Counters are already in the next standard and should be part of C++17.
Herb Sutter was the one that proposed them and I'm glad he did, but when it comes to concurrent data structures, it is pretty much useless because it is only non blocking in certain situations, and it is the slowest of the three methods for Readers because when you're traversing a list with nodes you need to do two atomic_fetch_add() per node that is traversed.
If you want to understand what situations are those, then take a look at chapter 9.1 of Paul Mckenney's book in this link https://www.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook-e1.pdf

RCU is better known for its implementation in the Linux Kernel, but there are many userspace implementations of RCU. We used some of them in the Left-Right technique.
RCU is wait-free (population oblivious) and super fast for Readers, but it is blocking for Reclaimers which means that if you want high throughput or low latency even when doing removal of nodes/objects from a data structure, this is isn't going to give you what you want.
Even with delegation, where the last reader will delete the node/object, it doesn't change the progress condition for the Reclaimers, and it even makes the Readers worse off because now they may have to delete an unbounded number of objects, thus making the Readers wait-free unbounded, which has much worse tail latency.
RCU is the simplest to use of the three techniques because its semantics for the Readers are similar to those of a Reader-Writer Lock.

Hazard Pointers are typically lock-free for the Readers (wait-free in some situations) and wait-free bounded for the Reclaimers.
The main drawback is that they're slow for Readers because we have to do one sequentially consistent store for every node that is traversed.
It's not as slow as Atomic Reference Counter is for Readers, but it is slower than RCU which pretty much has no synchronization apart from the initial call to rcu_read_lock() and the final call to rcu_read_unlock().
Of the three techniques, this is the hardest to use, not because it is hard per-say, but because it requires a very deep knowledge of the algorithm where you're applying hazard pointers to. If you want to make it wait-free then the difficulty goes up a notch, and it typically requires the algorithm to be designed with HPs in mind.
One of the untold advantages of HPs is that they are memory bounded. This means that at any given time you can not have more than (MAX_THREADS x MAX_HPS) nodes/objects in the retired lists waiting to be deleted (for an 'R' factor of zero). RCU has no such bound and if you have memory constraints this can become problematic and it can impact your tail latency for the Reclaimers.

There are many other methods for safe memory reclamation, but they are either variations on these ideas or they rely on some architecture/OS specific functionality, like needing Posix signals, or some CPU instructions that only exist on some hardware. Those are "outside" of the C++ Memory Model, i.e. you can't implement them using only atomics and the Memory Model and therefore, their implementations are not portable.

Paul McKenney is one of the authors of RCU.
Hazard Pointers are the brain-child of Maged Michael.
Obviously, there is a bit of friendly rivalry between the authors of the two best methods for non-blocking memory reclamation  :)
Having the two of them together in this endeavor to provide safe memory reclamation in C++, is like having Professor Xavier and Magneto joining forces to bring down Apocalypse  :)
Yes, it's really _that_ cool!

Sure, I'm a fan boy and I'm exaggerating. Just like Andreia was saying the other day, you can implement yourself Hazard Pointers and RCU, efficiently, in C++, and you don't really need library support for that, and in fact _we_ have done it.
However, I'm not going to say it was easy (it wasn't, specially the hazard pointers stuff) and most people just want to use a pre-existing library/API which they know is correct and fast for most usages, and that's why having Paul, Maged Michael, and Michael Wong behind this is a great thing for C++ and its community.
If you care about Concurrency and if you're at CppCon this year, make sure to attend this talk, it should be epic!

The importance of Sequential Consistency

Today we're going to talk about Consistency Models, things like Linearizability, Sequential Consistency, and Serializability.
https://en.wikipedia.org/wiki/Linearizability
https://en.wikipedia.org/wiki/Sequential_consistency
https://en.wikipedia.org/wiki/Serializability

I'll use C++ for the code examples, but this applies to all other languages with a memory model (C11, Java, Scala, Clojure, etc).

In the context of concurrent data structures, there are two extra vectors that influence the characteristics of (each method of) a data structure. One is the "Progress Condition" and the other is the "Consistency Model". 
Those of you familiar with databases, know that there is a huge number of different consistency models, but when it comes to concurrent data structures, we usually care if it is Linearizable (or Sequentially Consistent) or something more relaxed (for which no name may even exist).

Linearizability is important in the academic world because it makes it easy(ier) to prove that a certain algorithm is correct, so academics (and even some practitioners) like this very much. In addition, it is very intuitive to reason about for our humans brains.
A good example are Mutual exclusion locks and Reader-Writer locks, that provide linearizability for all its methods: lock(), unlock(), trylock(), etc
Unfortunately, it is a very "strong" condition, so much so, that not only it can be tricky to come up with algorithms that provide this kind of consistency, but doing do can have strong (negative) impacts on the performance, both in terms of throughput and latency.

Just one step below Linearizability, we have Sequential Consistency. This one is still easy to reason about, but it's not composable, and it is harder to prove the correctness of an algorithm (or data structure) that is sequentially consistent, than one that is linearizable.
An algorithm that is Linearizable is also Sequentially Consistent.

Below Sequential Consistency, it starts to be progressively harder to reason about an algorithm, and the number of different consistency models grows quickly, each one with its own quirkiness. Examples are: Acquire-Release (like the memory_order_acq_rel in the C++ memory model), or Serializability, or even completely relaxed (like memory_order_relaxed in the C++ memory model).
The most relaxed of all is the 'relaxed' (like the name indicates), to the point where calling it a "consistency model" is kind of a misnomer because it really isn't consistent at all.
Personally, reasoning about anything less than Acquire-Release is extremely difficult, and I believe most human brains suffer from the same obstacle  ;)

I think that the "being able to reason about it" is an excellent argument to go for linearizability/seq-cst/acq-rel and not something more relaxed. In fact, the whole point of things like Actor Models, CSP, and immutable data structures, is to sacrifice some of the performance at the exchange of being easier to reason about the code, so this should be enough of a reason to convince most people.







But it's not just about how hard or easy it is to reason about it, nope, it's much more than that!





To understand the importance of Sequential Consistency, we should start with something like "The Laws of Order": http://www.srl.inf.ethz.ch/papers/popl168gf-attiya.pdf
The implications of this paper may not be completely obvious at first, so I'll let you read it and digest it over a few days, but I will go even further than what the authors are saying: I think that operations with strong non-commutativity implicitly need (at least) Sequential Consistency.
Andreia and I don't completely agree on this point, so feel free to disagree as well.

This "strong non-commutativity" thingy is explained in the paper, but I can explain it in a paragraph as well (won't do a great job though):
Suppose you have a set (or a map, or a multiset, or a multimap) and you do in a single-threaded application the following operations:
    set.add(x);
    std::cout << set.contains(x) ;
This should print out "true" because the element "x" is now part of the set. But doing it the other way around:
    std::cout << set.contains(x) ;
    set.add(x);
will print out "false" assuming the set is initially empty, because "x" is not part of the set yet when we call contains().
This property of these operations of the set is said to be "strongly non-commutative", and it applies to all the operations of the set: add(), remove(), contains()

That's all fine and dandy in the single-threaded world, but what does it mean to have a concurrent set (i.e. multi-threaded world)?
How does this "strong non-commutativity" manifests itself in a concurrent set?

From a Program Order (PO) point of view, we expect that everything behaves in the order (sequence) that we implemented it. For example, if we write:
  set.add(x);
  set.add(y);
  set.add(z);
and then we place some set.contains() somewhere in the middle, we expect them to return true/false (depending on the place where we put them), but more than that, we implicitly expect something else:
- If set.contains(y) is true, then set.contains(x) MUST be true;
- If set.contains(z) is true, then set.contains(y) MUST be true;
If this was ever not the case, then you would (rightfully) complain that the compiler is broken!

So, suppose now you have two threads, T1 and T2 that will execute the following code, where xyz_are_in is an atomic<bool>, initially at false:
T1
  set.add(x);
  set.add(y);
  set.add(z);
  xyz_are_in.store(true);  // memory_order_seq_cst

T2:
    while (!xyz_are_in.load()) Pause();         // memory_order_seq_cst
    std::cout << xyz_are_in.load() << "\n"; // memory_order_seq_cst
    std::cout << set.contains(z) << "\n";
    std::cout << set.contains(y) << "\n";
    std::cout << set.contains(x) << "\n";

I hope everyone agrees that the result of T2 will ALWAYS be true, true, true, true.
I'll let you look at the code for a while until you're convinced of that.

Done?
Ok, great, now let's make it more difficult.
Suppose T2 now doesn't wait for xyz_are_in to become true:
T2:
    std::cout << xyz_are_in.load() << "\n"; // memory_order_seq_cst
    std::cout << set.contains(z) << "\n";
    std::cout << set.contains(y) << "\n";
    std::cout << set.contains(x) << "\n";

What are the possible outcomes?
Well, I didn't say what is the consistency model of this set, so let's not assume anything, i.e. it's relaxed. The possible outcomes are:
- false, any combination of true and false for the three contains(), and I really mean ANY combination
- true, true, true, true
Keep in mind that the rules of the C++ Memory Model say that you guarantee that anything that happened before the xyz_are_in.store(true) in T1, will be visible after the xyz_are_in.load() is true in T2, but it doesn't give any further guarantees, specifically, no guarantee is given on the order of the set.add()s or the set.contains()s.

So now think about the following: the set.add()s in Thread 1 can be re-ordered in any way (as seen from T2), which means that the invariants described above will no longer hold!
There is no "strong non-commutativity" when using a relaxed model  :-O
If there is no "strong non commutativity" then, does it even make sense to talk about a "set"? What is a "set" for which the invariants described above do not hold? What is a "set" that doesn't have "strong non-commutativity"? Is it even correct to still call it a "set"?
It's a set where you put an element in it, and then you go to check if the element is part of the set, and it's not (yet).... huhhhh
To me, a data structure with those properties can maybe be called a "pool", but definitely not a "set".

In fact, it's harder to show, but even for a consistency of acquire-release it will not have "strong non-commutativity".
The only way to have "strong non-commutativity" is to have sequential consistency between the operations of the set, i.e. a "sequentially consistent set"!

Without sequential consistency, it does not make sense to talk about sets, or multisets, or maps, or multimaps.
I know that there is a strong tendency to make data structures with a relaxed consistency because you can make them (waaaayyyy) faster than one that is sequentially consistent (or linearizable), but the thing is, IMHO, it doesn't even make sense to call it a "set" it doesn't have sequential consistency.
Sure, you may not actually need a "set", and something with more relaxed properties is enough, and then, it will be ok with have a "relaxed set", or whatever you want to call it.

It seems to me that the notion of Sequential Consistency is embedded in the very essence of what a "set" is, to the point that a set without seq-cst is not a set.
I know this is a somewhat controversial statement, and I wish I had the mathematical skills to show a proof of this, but I don't, so feel free to try a couple of examples and reach your own conclusions, but I'm confident you'll reach the same conclusion, and if not, that's what the Comments section is for   ;)

Atomics and the Memory Model in C++1x

One of the cool talks in this year's CppCon was the one by Michael Wong on Atomics:

There's nothing really new about this that I hadn't seen before, but it has a very good "round up" of all the main concepts related to this topic and explained in a clear and entertaining way. He's also an ex-physicist, so I'm biased  :)

 

This presentation covers things like:

- Why do we need a Memory Model;
- Why is memory_order_seq_cst not enough and we need also things like memory_order_relaxed, memory_order_acquire and memory_order_release;
- What is Sequential Consistency;
- Caches in modern CPUs;
- The speed of light is the maximum speed to transmit information, and what are the consequences of this;
- The difference between volatile and atomic<>;
- Sequential Consistency and Happens-Before;
- Relative strengths the different memory orders;


This last one was particularly interesting so I'm going to steal a snippet of his slide and show it here:


This is related to the reason why we get different performance benefits when using the different memory orders, like we showed at the end of this post.