What does 'spurious failure' on a CAS mean?

Question

The Java AtomicInteger class has a method -

boolean weakCompareAndSet(int expect,int update)

Its documnentation says -

May fail spuriously.

What does 'failing spuriously' here mean?

Answer 1

That when that happens you'll feel like calling "Bastard" to that method?... :)

Answer 2

It means it might return false (and will not set the new value) even if it currently contains the expected value.

In other words, the method may do nothing and return false for no apparent reason...
There are CPU architectures where this may have a performance advantage over a strong CompareAndSet().

---

A bit more concrete detail on why something like this might happen.

Some architectures (like newer ARMs) implement CAS operations using a Load Linked (LL)/Store Conditional (SC) set of instructions. The LL instruction loads the value in a memory location and 'remembers' the address somewhere. The SC instruction stores a value into that memory location if the value at the remembered address has not been modified. It's possible for the hardware to believe that the location has been modified even if it apparently hasn't for a number of possible reasons (and the reasons might vary by CPU architecture):

1. the location may have been written with the same value
2. the resolution of the addresses watched might not be exactly the one memory location of interest (think cache lines). A write to another location that's 'close-by' may cause the hardware to flag the address in question as 'dirty'
3. a number of other reasons that may cause the CPU to lose the saved state of the LL instruction - context switches, cache flushes, or page table changes maybe.

Answer 3

spuriously: for no apparent reason

According to atomic package javadoc:

The atomic classes also support method weakCompareAndSet, which has limited applicability.

On some platforms, the weak version may be more efficient than compareAndSet in the normal case, but differs in that any given invocation of the weakCompareAndSet method may return false spuriously (that is, for no apparent reason).

A false return means only that the operation may be retried if desired, relying on the guarantee that repeated invocation when the variable holds expectedValue and no other thread is also attempting to set the variable will eventually succeed.
(Such spurious failures may for example be due to memory contention effects that are unrelated to whether the expected and current values are equal.)

Additionally weakCompareAndSet does not provide ordering guarantees that are usually needed for synchronization control.

---

According to this thread, it is not so much because of "hardware/OS", but because of the underlying algorithm used by weakCompareAndSet :

weakCompareAndSet atomically sets the value to the given updated value if the current value == the expected value. May fail spuriously.

Unlike compareAndSet(), and other operations on an AtomicX, the weakCompareAndSet() operation does not create any happens-before orderings.

Thus, just because a thread sees an update to an AtomicX caused by a weakCompareAndSet doesn't mean it is properly synchronized with operations that occurred before the weakCompareAndSet().

You probably don't want to use this method, but instead should just use compareAndSet; as there are few cases where weakCompareAndSet is faster than compareAndSet, and there are a number of cases in which trying to optimizing your code by using weakCompareAndSet rather than compareAndSet will introduce subtle and hard to reproduce synchronization errors into your code.

---

Note regarding happens-before orderings:

The Java Memory Model (JMM) defines the conditions under which a thread reading a variable is guaranteed to see the results of a write in another thread.

The JMM defines an ordering on the operations of a program called happens-before.

Happens-before orderings across threads are only created by synchronizing on a common lock or accessing a common volatile variable.

In the absence of a happens-before ordering, the Java platform has great latitude to delay or change the order in which writes in one thread become visible to reads of that same variable in another.

Answer 4

But why are such allowed to occur at all? Is this because the hardware/OS underneath is buggy? Or is there some good technical reason behind this?