Monday, July 1, 2013

Relaxed Atomics in Java

As surprising as you may find it, Java also supports relaxed atomics... kind of.
If you don't know what relaxed atomics are, then you can first watch this presentation from Herb Sutter "Atomic Weapons".

In case you don't want to watch the video, the summary of it is that Relaxed Atomics are a new feature in C11 and C++11 that comes as part of the new SC-DRF (Sequentially-Consistent for Data-Race-Free programs) Memory Model. They are useful to improve the performance on some concurrent algorithms and data-structures, particularly on non-x86 architectures.

Recently, memory barriers have been introduced in Java. To use them we need Unsafe which is not a very nice way to develop code (because the API can change at any time in the future), but ohhh well.

An interesting guarantee given by the JVM is that references and native types are always atomic, with the exception of long and double, for which no such guarantee is given.
This may seem like a trivial matter, but it means that an int variable in Java will never have an intermediate state. To understand how important that is, just try to write a concurrent data structure.... or watch the video mentioned before.

Relaxed atomic operations can be done in Java by using a "regular variable" (except for long or double), and then using loadFence() or storeFence() when barriers are actually needed. The disadvantage of this approach is that it doesn't allow for CAS operations for longs.

Here is a comparison table that shows how different atomic operations can be done on Java and C11, including relaxed loads and stores:

Notice that we can't disable the barriers on volatile variables.
As you can see from the table above, the trick to get relaxed atomics in Java is to use sun.misc.Unsafe, namely:

More info on fences can be found here

To be accurate, C11 and C++11 allow for a much finer tuning of the kind of relaxed operations allowed. For example, we can have re-ordering of loads with stores, but not loads with loads, or other special cases, which in Java are not possible.
In practice, the only kind of relaxed atomics that we have felt the need for in our algorithms are the fully relaxed. For example, because we need the atomicity but we know that the barriers are not needed on a particular place in the code, because soon after there will be a release barrier or, there was an acquire-barrier just before.

One of the things that I've always admired in Java is the Memory-Model, but now with the new memory model in C11 and C++11 the developers of C/C++ have at their disposal a way of writing faster concurrent algorithms than Java developers can achieve, because of the lack of complete support for relaxed atomics.
Time will tell how important is this feature for the performance of concurrent algorithms in current and future CPU architectures, but my bet is on C11/C++11.

Anyways, when it comes to memory models, C11/C++11 has matched and went beyond Java.

No comments:

Post a Comment