Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #26440 > unrolled thread

java.util.concurrent.atomic

Back to article view | Back to comp.lang.java.programmer

Contents

  java.util.concurrent.atomic markspace <markspace@nospam.nospam> - 2013-10-26 17:25 -0700
    Re: java.util.concurrent.atomic Kevin McMurtrie <mcmurtrie@pixelmemory.us> - 2013-10-26 19:56 -0700
      Re: java.util.concurrent.atomic Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2013-10-29 20:35 +0000
        Re: java.util.concurrent.atomic Eric Sosman <esosman@comcast-dot-net.invalid> - 2013-10-29 17:27 -0400
        Re: java.util.concurrent.atomic Marcel Müller <news.5.maazl@spamgourmet.org> - 2013-10-29 22:36 +0100
        Re: java.util.concurrent.atomic Kevin McMurtrie <mcmurtrie@pixelmemory.us> - 2013-10-29 21:17 -0700
    Re: java.util.concurrent.atomic Marcel Müller <news.5.maazl@spamgourmet.org> - 2013-10-27 10:09 +0100

#26440 — java.util.concurrent.atomic

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/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!

[toc] | [next] | [standalone]

#26441

In article <l4hmhq$282$1@dont-email.me>,
 markspace <markspace@nospam.nospam> wrote:

> 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.

[toc] | [prev] | [next] | [standalone]

#26450

Kevin McMurtrie <mcmurtrie@pixelmemory.us> wrote:
> 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?

[toc] | [prev] | [next] | [standalone]

#26451

On 10/29/2013 4:35 PM, Andreas Leitgeb wrote:
> Kevin McMurtrie <mcmurtrie@pixelmemory.us> wrote:
>> 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 ...

-- 
Eric Sosman
esosman@comcast-dot-net.invalid

[toc] | [prev] | [next] | [standalone]

#26452

On 29.10.13 21.35, Andreas Leitgeb wrote:
> Kevin McMurtrie<mcmurtrie@pixelmemory.us>  wrote:
>> 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

[toc] | [prev] | [next] | [standalone]

#26453

In article <slrnl70709.mol.avl@gamma.logic.tuwien.ac.at>,
 Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> wrote:

> Kevin McMurtrie <mcmurtrie@pixelmemory.us> wrote:
> > 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.

[toc] | [prev] | [next] | [standalone]

#26444

On 27.10.13 02.25, markspace wrote:
> 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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web