July 24th, 2010

Unsafe & CompareAndSwap

RSS icon RSS Category: Personal
Fallback Featured Image

A Short and Sweet (and Deep) Brain Dump –
About Unsafe and CompareAndSwap (and NonBlockingHashMap).
A reader asked me: where is the volatile-like orderings guaranteed in NBHM?

  1. CAS – Compare-And-Swap instruction (or on IBM Power chips: Load-Linked / Store-Conditional).  The unit of Atomic Update on all modern CPUs, required for any sort of multi-cpu programming.
  2. Unsafe – Java-level access to raw memory.  In old-school speak: ”peek” and “poke”.  (and when I mean “old-school” I mean the talk elite hackers use BEFORE the use of “leet speak” came about; I suppose this means I’m older than dirt…).  This bypasses all the managed runtime safety guarantees, and thus isn’t available to normal Java programs.  You can get it e.g. by hacking the JVM’s boot-class-path.
  3. NBHM – Non-Blocking Hash Map.  A very high performance multi-threaded-safe non-blocking hash map.  See this SourceForge link for the code.  I’ll mention KEY/VAL below to mean any key/value pair in the mapping.

Annoying horizontal lines are meant to give you time to chew&swallow, before moving on to the next byte…

I’m using sun.misc.Unsafe.compareAndSwapObject.
It makes no guarantees about volatile ordering.  That is, the docs are silent.
It’s implementation (at the Java level) is a native call.
Like all native calls, the docs are silent as to the exact semantics.
I’m highlighting the word “docs” here because there are a ton of actual requirements demanded by the Real World.
The typical native call implementation is a CAS instruction on X86/Sparc/Azul/IA64, or a LL/SC on IBM Power.
Sometimes the JIT’s inline the native call to a hardware CAS instruction.
The hardware provides volatile-like semantics for CAS ops on X86/Sparc.
The hardware does NOT provide volatile-like semantics for CAS on Azul or IBM Power.  I don’t know about IA64.
Some JITs on some platforms may inline additional memory fences, and thus provide additional guarantees.
HotSpot, in the C2 server compiler, includes extra fences.
sun.misc.Unsafe, since it has no spec, is free to ignore the volatile-ness of anything and everything.
It is, after all, Unsafe.

java.util.concurrent.Atomic.* uses sun.misc.Unsafe.*.
sun.misc.Unsafe does not make any volatile guarantees.
java.util.concurrent.Atomic.* DOES make volatile guarantees (and uses a volatile variable).
Hence, for a JIT’d inlined version of s.m.U.compareAndSwap to be the proper implementation for any j.u.c.A.CAS call, s.m.U.compareAndSwap needs to include some volatile-smarts.  This happens “for free” on X86 or Sparc, because the X86 hardware CAS op includes volatile-like orderings.  This is definitely not “for free” on an Azul box because our CAS does NOT provide any orderings.

Frequently, I have uses for CAS that do not require orderings and that adding orderings would entail excessive cost.  Several of the CAS ops in NBHM do not require orderings; nor do any of the scalable counters (including the CAT counter).  Hence for these uses the Azul version of s.m.U.* does a plain Azul CAS op with no orderings.  The same could be true for e.g. a IBM Power implementation, or for any hardware for which scaling to lots of CPUs is hard and unneeded fencing would slow things down unnecessarily.
Since Azul’s CAS op (hence our s.m.U.* implementation) does not force orderings, our version of the j.u.c.A.CAS ops includes extra fences to force volatile orderings (both in the native code implementation and the JIT’d inlined code).

So back to the original question about NBHM orderings….
On the PUT (i.e. writer) side:

  • if a KEY is newly inserted I may not end up writing to a volatile, but I will do a CAS.  On X86/Sparc platforms the CAS includes the needed orderings.  On Azul, our simple store-buffers has the same effect… but definitely not a happy situation.  There’s no Java-level guarantee (just a guarantee on X86, or with C2/HotSpot).  Technically a bug on, e.g.,  Power platforms.  Thanks for spotting this.
  • if the KEY already exists, and only the VAL is written – the same arguments apply.  CAS suffices on X86, and Azul’s simple processors suffice.

On the GET side:

  • I explicitly do a volatile-read before every key-compare (even if the keys are pointer-equivalent), and a key-compare is needed to get a “hit”.  Hence there is a volatile-read before any GET call returns anything.

Thus for NBHM, (except for non-HotSpot JVMs on Power) there is a volatile-write before any Put and a volatile-read before any Get.


Leave a Reply

Time Series Forecasting Best Practices

Earlier this year, my colleague Vishal Sharma gave a talk about time series forecasting best

October 15, 2021 - by Jo-Fai Chow
Improving NLP Model Performance with Context-Aware Feature Extraction

I would like to share with you a simple yet very effective trick to improve

October 8, 2021 - by Jo-Fai Chow
Feature Transformation with the H2O AI Hybrid Cloud

It is well known throughout the data science community that data preparation, pre-processing, and feature

October 7, 2021 - by Benjamin Cox
Introducing DatatableTon – Python Datatable Tutorials & Exercises

Datatable is a python library for manipulating tabular data. It supports out-of-memory datasets, multi-threaded data

September 20, 2021 - by Rohan Rao
H2O Release 3.34 (Zizler)

There’s a new major release of H2O, and it’s packed with new features and fixes!

September 15, 2021 - by Michal Kurka
From the game of Go to Kaggle: The story of a Kaggle Grandmaster from Taiwan

In conversation with Kunhao Yeh: A Data Scientist and Kaggle Grandmaster In these series of interviews,

September 13, 2021 - by Parul Pandey

Start your 14-day free trial today