java.util.concurrent.atomic

[markspace]

Hi all,

In spite of the fact that I think I know the Java API well, I often find
classes or methods that I was unaware of. Here's some examples from
java.util.concurrent.atomic that I was unaware of.

AtomicBoolean
AtomicInteger
AtomicLong

I think most folks are aware of these three basic atomic classes.

AtomicReference

Here's something I forget about: update an object reference atomically.
I'm having trouble thinking of a good use case for this class however.
Does anyone have an interesting example of its use?

AtomicIntegerArray
AtomicLongArray
AtomicReferenceArray

Holy cow! Remember when we get questions about "can I make array
elements with volatile memory semantics"? I recall us answering "no" to
that question. Guess what the three classes above do? Yup, access
arrays atomically with volatile memory semantics. Very useful.

AtomicIntegerFieldUpdateder
AtomicLongFieldUpdater
AtomicReferenceFieldUpdater

These are hella cool. They update fields within a class atomically.
Yet I'm having trouble thinking of uses cases for these as well. Any ideas?

AtomicReferenceFieldUpdater has an worked out code example involving a
node with left and right sub-nodes, but I don't think I grok it completely.

<http://docs.oracle.com/javase/7/doc...rrent/atomic/AtomicReferenceFieldUpdater.html>

AtomicMarkableReference
AtomicStampedRefernce

Ditto with these two classes. They seem cool, but I'm not sure what I'd
use them for.


Additional comments and insights on these classes are appreciated!

 

[Kevin McMurtrie]

Hi all,

In spite of the fact that I think I know the Java API well, I often find
classes or methods that I was unaware of. Here's some examples from
java.util.concurrent.atomic that I was unaware of.

AtomicBoolean
AtomicInteger
AtomicLong

I think most folks are aware of these three basic atomic classes.

AtomicReference

Here's something I forget about: update an object reference atomically.
I'm having trouble thinking of a good use case for this class however.
Does anyone have an interesting example of its use?

AtomicIntegerArray
AtomicLongArray
AtomicReferenceArray

Holy cow! Remember when we get questions about "can I make array
elements with volatile memory semantics"? I recall us answering "no" to
that question. Guess what the three classes above do? Yup, access
arrays atomically with volatile memory semantics. Very useful.

AtomicIntegerFieldUpdateder
AtomicLongFieldUpdater
AtomicReferenceFieldUpdater

These are hella cool. They update fields within a class atomically.
Yet I'm having trouble thinking of uses cases for these as well. Any ideas?

AtomicReferenceFieldUpdater has an worked out code example involving a
node with left and right sub-nodes, but I don't think I grok it completely.

<http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/atomic/AtomicRe
ferenceFieldUpdater.html>

AtomicMarkableReference
AtomicStampedRefernce

Ditto with these two classes. They seem cool, but I'm not sure what I'd
use them for.


Additional comments and insights on these classes are appreciated!

The atomic package is for atomic operations that will compare and set or
compare and swap.

Say you have a function like this:

x= f(x, a)

The variable 'x' depends on its previous value so it's not normally
thread safe. For example, you're building a linked list on shared head
value. If multiple threads did that on a simple shared variable then
links would get orphaned:

head= new Link(head, value); //Not thread safe on 'head'

CAS lets you update a value only if it has not changed. Make the
variable 'head' an AtomicReference<Link> and you're good.

Link origHead, newHead;
do
{
origHead= head.get();
newHead= new Link(origHead, value);
while (!head.compareAndSet(origHead, newHead);

The compareAndSet() method will do nothing and return false if the value
is not what you expect it to be. compareAndSet() might stop the CPUs
for a moment to synchronize cache memory but it can never block longer.

Why use code that can never block? Most systems use time slicing. This
is where each thread gets up to a certain number of microseconds of CPU
time before giving up the CPU to another thread. Somewhere in the 100+
thread count you start having problems where a thread will grab a lock
and then have its timeslice run out. Other threads needing that lock
will perform a short spinloop of retries then deactivate. When the
original thread wakes up to release the lock, another thread that is in
a spinloop will acquire it. Since it has been burning up CPU time in a
spinlook, it's fairly likely to use up its timeslice while holding the
lock. The cycle keeps repeating to give you "drop off a cliff"
performance that's difficult to recover from. You'll see high CPU time
with lots of blocked threads, and not much getting done.

 

[Marcel Müller]

AtomicReference

Here's something I forget about: update an object reference atomically.
I'm having trouble thinking of a good use case for this class however.
Does anyone have an interesting example of its use?

Almost any Lock-Free algorithm relies on atomic references.

A classical is a lock free locator with many parallel readers and only a
few writes. The trick is to use immutable and therefore intrinsically
thread-safe objects.
You can make this locator thread-safe with an atomic reference to a
Hashtable. Once a Hastable instance is exposed to the other threads by
this atomic reference it must not be modified any more. So all read
operations are safe. If the Hashtable is to be modified, it is copied,
modified and then the atomic reference is switched to the new revision.
Concurrent writers can be synchronized by a CAS loop or simply by a
synchronized block.
The only thing you have to care about is that the atomic reference does
not provide repeatable read semantics, of course. But you can easily
take a snapshot of the current content by simply taking a local reference.

AtomicIntegerArray
AtomicLongArray
AtomicReferenceArray

Holy cow! Remember when we get questions about "can I make array
elements with volatile memory semantics"? I recall us answering "no" to
that question.

You cannot access the entire array atomically, but surely you can access
/single/ integers in the array atomically. AtomicInteger[] would do the
job as well, but it might be unwanted because of the many allocations
for each AtomicInteger object. However, AtomicIntegerArray is likely to
cause ->false sharing, which can be orders of magnitude slower than the
additional allocations of AtomicInterger[]. So handle with care.

AtomicIntegerFieldUpdateder
AtomicLongFieldUpdater
AtomicReferenceFieldUpdater

These are hella cool. They update fields within a class atomically. Yet
I'm having trouble thinking of uses cases for these as well. Any ideas?

These classes give you the option to access a field with memory barrier
only on demand. An Implementation of the double check idiom might use this.
But, since Java does not support references to built-in value types,
they cannot be used without reflection. So I would recommend not to use
them. Instead make the field volatile or use AtomicXXX and avoid any
unnecessary unsynchronized access to the field by using local copies.
Most of the time this is faster with respect to cache efficiency too.

AtomicReferenceFieldUpdater has an worked out code example involving a

Same applies to this one.

AtomicMarkableReference
AtomicStampedRefernce

Ditto with these two classes. They seem cool, but I'm not sure what I'd
use them for.

I never needed something like that. AFAIK it can be used to implement
some lock-free algorithms like linked lists and skip lists.
The basic idea is to update /two/ fields atomically. The implementations
expose the special case of tuples of <T,bool> and <T,int>.

Some hardware platforms have built-in CPU instructions for this purpose
(atomically access two machine size words). But since the implementation
does not use this, I see no significant benefit of using this classes.

Additional comments and insights on these classes are appreciated!

I often deal with atomic operations and lock free algorithms. The can be
extremely fast and scalable. But developing lock free algorithms is also
art.
Most of the time I use C++ and .NET, but since this is very close to the
hardware there are only minor language dependencies.
The next interesting point will be transactional memory.


Marcel

 

[Andreas Leitgeb]

Why use code that can never block? [...]

That would be fine, if the code really didn't block, but if it
ends up doing the "do { ... } while (...)" idiom, then it really
IS blocking, just in a bad way.

What would be usecases of non-blocking synchronisation that don't
end up polling until success?

 

[Eric Sosman]

Why use code that can never block? [...]

That would be fine, if the code really didn't block, but if it
ends up doing the "do { ... } while (...)" idiom, then it really
IS blocking, just in a bad way.

What would be usecases of non-blocking synchronisation that don't
end up polling until success?

Marcel Müller described one elsethread. Yes, after a failure
the non-blocking algorithm goes back and tries again. What you may
have missed is that it tries again with a new "new value," and
doesn't simply try again with the same old failed one:

while (true) {
Thing oldThing = currentThing;
Thing newThing = modifiedVersionOf(oldThing);

// Done atomically by compare-and-swap:
if (currentThing == oldThing) {
// No other thread got there before me, so:
currentThing = newThing;
break;
} else {
// Rats! Somebody else changed currentThing, so
// the newThing I computed is already obsolete.
// Go back and try *everything* again.
}
}

The advantage of this approach is that you don't need to hold a
lock for however long modifiedVersionOf() takes. The disadvantage
is that currentThing might change during that time, meaning your
effort was wasted. In principle you could stay in the loop
"forever" if other threads are constantly updating currentThing --
but a blocking algorithm wouldn't remove that pain, it would
just distribute it differently (threads could wait "forever"
before acquiring a lock). If currentThing is constantly getting
updated, you at least know that *some* thread is making progress
even if it's not *your* thread ...

On the other hand, blocking code is a good deal easier to
write and understand. I took a week-long course on non-blocking
algorithms from an ACM Fellow, and the main thing I learned is that
you pretty much *need* to be an ACM Fellow to avoid blunders ...

 

[Marcel Müller]

Why use code that can never block? [...]

That would be fine, if the code really didn't block, but if it
ends up doing the "do { ... } while (...)" idiom, then it really
IS blocking, just in a bad way.

As long as your algorithm ensures forward progress, the number of loops
should be finite. But in theory it might end up O(n^2) with n the number
of parallel jobs (the first job terminates after first loop, the second
job after two loops and so on). In practice optimistic locking performs
significantly better most of the time. Typically the probability of
taking more turns until success decreases exponentially.

The idea behind the scenes is that doing a handshake for synchronization
is more expensive than doing the work twice. In fact we are close to the
limits given by Einsteins theory of relativity. Correlated events in
space-time must reachable by the speed of light. In a 1 GHz clock cycle
(nothing special nowadays) you can synchronize over a distance of about
10 cm. Larger distances take longer. This is sufficient for multi-core,
critical for multi-chip servers and impossible for network clusters.

What would be usecases of non-blocking synchronisation that don't
end up polling until success?

Intrinsically atomic operations do not require CAS loops. E.g. atomic
increments/decrements for reference counting perform O(1).

In other algorithms a CAS fail might end up in a way that another
parallel thread does the job for my thread. In this case the number of
instructions is still O(1).


Marcel

 

[Kevin McMurtrie]

Why use code that can never block? [...]

That would be fine, if the code really didn't block, but if it
ends up doing the "do { ... } while (...)" idiom, then it really
IS blocking, just in a bad way.

What would be usecases of non-blocking synchronisation that don't
end up polling until success?

It's not blocking in a manner in that there's no way for other threads
to be permanently blocked. Some may re-execute, but there's always
progress. It solves a problem on highly concurrent systems where
threads might unexpectedly deactivate while holding an important
semaphore. I've seen systems collapse because lots of code was calling
the synchronized get(String) on the system Property singleton.

What works better depends on how long your modification takes. If
there's absolutely no way to make it fast, a blocking lock may be better
because of the lower CPU cost. If the modification is as simple as
allocating a small object and moving a couple of references, the
non-blocking method might collide and re-execute maybe 1 in a million
times.