On std::atomic_compare_exchange_*

When I started using the new atomic_compare_exchange_*() functions available on C++11 I struggled a bit to get it right. It seems I wasn't the only one, because other people are complaining that the API is broken... which according to Herb Sutter is not true and he has a post explaining why:
http://herbsutter.com/2014/02/19/reader-qa-is-stdatomic_compare_exchange_-implementable/

After an afternoon of banging my head against the wall, I figured out how to use these functions and got the implementation right for the data structure I was trying to port from Java to C++11.
http://en.cppreference.com/w/cpp/atomic/atomic_compare_exchange

I was mislead by Java's atomics APIs because in Java Atomics classes, there is a compareAndSet(), while the C++11 it is an atomic_compare_exchange_*(). I blame myself for it though, because the names really say it all: one is a set, while the other is an exchange.
The C++11 API does an exchange of the variables, while the Java just sets the variable to the new value.

Yep, it's as simple as that, and I wasted an afternoon on it, which I know, was a dumb mistake, but I guess those are the easier ones to do  ;)

Dave Dice on Pseudo Random Number Generators

For those (very few) of you interested in doing benchmarks of concurrent data structures, or scalable probabilistic counters, you will probably enjoy this post by Dave Dice on PRNGs:
https://blogs.oracle.com/dave/entry/a_simple_prng_idiom

We got into this kind of stuff because, well, my PhD was done using Bootstrap Resampling so having a good random number generator is important, but for our benchmarks of concurrent data structures we need speed much more than we need accuracy, so we had to look a bit into this topic.
This is also related to ThreadLocalRandom, so if you ever used it, you might want to take a look at his post.

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.