Hans Boehm on the C++11 Memory Model

Here is a presentation from BoostCon 2011 by Hans Boehm on the C++11 Memory Model and Atomics:

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

Most of this has already been covered by Herb Sutter on his presentation on atomics, which you might find easier to follow, but listening to Hans provides some extra insights which you wouldn't get from anyone (or anywhere) else.

I particularly enjoyed the part about relaxed atomics, which I slightly disagree with him and believe that is one of the most important features of the Memory Model, but the future will show how much more performance gain can we get from them on CPUs with a relaxed memory model.

This is a long presentation and the video quality is poor, but I still think it's worth watching just for the questions of the audience (and Hans's answers to them).

You can see most of the slides from another one of his presentations:
http://ecn.channel9.msdn.com/events/goingnative12/GN12ThreadsAndSharedVariables.pptx

There is another presentation by Hans Boehm which adds a bit more info, specially the part on infinite loops, but it is harder to follow because the screen is not shown:
https://www.youtube.com/watch?v=UWx4EA2uBzs

Harris with AtomicMarkableReference - remove

On a previous post we talked about an implementation of Harris Linked List using Java's AtomicMarkableReference (AMR), and how insertions work in such a data structure.
This time, we are going to see how deletions work in this technique.

Suppose we start with a very small list with just four keys, and their corresponding nodes, as shown in the picture below:


notice that all the AMR instances have a mark of 0 (or false if you prefer).


Suppose we want to remove the key B from the set, and by consequence the node B. We start the removal by creating a new AMR instance that references Node D and has a mark of 1 (true), because the reference and mark are immutable, so the only way to change them is to create a new instance:


The next step is to change node B so that it uses the new AMR instance. This is done with a compareAndSet() (CAS for short) and the goal of this operation is to logically remove the key B from the set, and to prevent further insertions after the node B. From this instant onwards, any contains(B) operation will return false because, even though the node B is still physically in the linked list, it is pointing to an AMR instance that has a mark of 1 and is, therefore, logically removed:


The old AMR instance will no longer be reachable and the Garbage Collector (GC) can now clean it up:


On the following step, we create another AMR instance that is also referencing node D, but with a mark of 0:

Then, using a CAS, in the node A we change from the current instance of AMR that references node B to the newly created AMR instance that references node D. This will unlink node B, thus physically removing node B from the linked list:


All that needs to be done now is for the GC to collect the unused AMR instances and the node B:


For those of you who were not counting, the whole procedure took 2 CAS (because there were no retries in this example), and involved the creation of two new AMR instances (actually, it was of the type Pair to be more precise, which in turn is encapsulated in the AMR class), and the GC had to cleanup one Node instance and three unused AMR instances. All of this just to remove a single key from the set, without any contention.

Obviously, this is a very wasteful technique, and we can do better than this... much better in fact, and that is what we'll look into in upcoming posts.