concurrency resources in RTP (was Re: fencing, was: A Lock-Free Hash)

   Wikipedia can explain memory fences much better than I can:

         http://en.wikipedia.org/wiki/Memory_barrier

    By the way, the best book for learning about concurrent programming 
in the context of Java is "Java Concurrency In Practice" (aka JCIP) by 
Goetz, Peierls, Bloch, Bowbeer, Holmes and Lea.
   If you'd like to get some of this from the guy that *really knows*, 
Brian Goetz (primary author) will be speaking at the June 20-22 local 
"Research Triangle Software Symposium":

   http://www.nofluffjuststuff.com/conference/raleigh/2008/06/index.html

  Also, to be clear about yesterday's msg, my point was that "lock-free 
synchronization" often involves "postponing execution", albeit for a 
bounded length of time. So there is no free lunch, just cheaper 
(sometimes hugely cheaper) lunches with "lock-free" data structures 
unless they are completely synchronization-free.
  To return to the anthropomorphic thread analogy, a fence forces you to 
stop and coordinate with all other threads that might potentially be 
checking certain shared memory state and able to see (and be sabotaged 
by) any improper ordering of changes in relation to the change of the 
synchronizing data mutation. And in relation to your speed approaching 
the fence this is like sending a carrier pigeon across town and having 
to spot its landing on a distant roof top before proceeding (i.e. the 
hardware has to actually update main memory or give all cpus a 
convincing illusion that it has done so). Then you can jump over the 
fence and take off again like one of those folks in "The Matrix."
  If you think about a Java object's state change and the Java Memory 
Model term "happens before", these fence/membar operations are hiding 
under the covers of this term. So when the JMM says "X happens before Y" 
it means it is impossible for any thread to see "not X" or "not quite X" 
after seeing Y, where X and Y are object(s) state details. If you have a 
weekend to spare for deep thought, here is the definitive JMM document 
(to read it *after* JCIP):
      http://java.sun.com/docs/books/jls/third_edition/html/memory.html
  In relation to the fence analogy, a lock acquisition is a sign at a 
border fence saying "You might be be able to cross sometime. Take a 
number and wait. Be sure to have a book or your MP3 player with you!" 
The fence might be crossed "soon" or never. But when it matters most 
there may be a crowd ahead of you and one forming behind you. And your 
book is too short or your player exhausts its batteries. :-) At the 
hardware level CPU cache and memory systems can be playing hyper-fast 
ping pong as threads keep pounding on the lock memory, hogging data 
paths. Plus you have to do the carrier pigeon thing if/when your number 
comes up to get over the fence. And then there's a second fence on the 
other side of the "critical section" where the lock is released, and 
this may (typically will) require another confirmed pigeon flight.
  The entire span of time any thread is acquiring and releasing locks 
and executing in the critical section between the acquire and release 
is, by definition, "serialized" execution, feeding into Amdahl's Law 
relating to scaling (see http://en.wikipedia.org/wiki/Amdahl's_law BUT 
ALSO know that Amdahl's Law is a major oversimplification and anybody 
really interested in predicting concurrent performance should read this 
for a more enlightened view:  
http://www.cis.temple.edu/~shi/docs/amdahl/amdahl.html). Another way to 
view this is the synchronization implementation of a lock-free structure 
is like a theoretically minimal size critical section. Cliff goes a step 
further with cost-cutting by using "fenceless CAS" instructions in cases 
where his algorithm simply doesn't care if inconsistent views of memory 
take place. But in my experience when you read the acronym "CAS", 
99.9999% of the time the author means "fenced CAS."
    Another point about lock/unlock operations and fence instructions 
closely related to Java "synchronized" and "volatile" usage is that 
dynamic native code compilers in the JVM (or static, ahead of time 
native compilers)  are often constrained by synchronization with respect 
to code motion: they often can't move code past the synchronization 
operation, and this unfortunately involves any hardware data object that 
might hold an alias (same reference) involved with synchronization (and 
detecting aliases can be extremely difficult). This can really hose the 
performance of state of the art compilers on advanced computer hardware 
(e.g. the Hotspot "server" compiler on a recent Sparc, AMD, and Intel, 
and PowerPC chips). This is because a chunk of their cleverness is 
scheduling memory operations in such a way that their overhead can be 
folded into the same time some other functional units are doing work, or 
else the compiler can pick a point for code generation where the cache  
interface or memory bus is not likely to be busy. Other times it's the 
difference between an operation being moved outside of a loop vs having 
to execute for every loop iteration (e.g. gratuitous/worthless use of 
"volatile" can be a *bad thing* because of this). So, for example, a 
write to memory can go from "only done once outside a loop", to "nearly 
free" (quickly going to/from an L1 cache line) to "OK, got to wait for 
the memory read operation to complete or for (possibly *large* number 
of) write operations to complete!", all depending on the decisions made 
by the programmer.
  But there is no doubt that it can be extremely hard to know what is 
correct in a specific circumstance. This is why you should go listen to 
Brian if you can and keep JCIP under your pillow until you stop being 
surprised by concurrent program behavior. :-)
 
-Pete

PS Disclosure: I work for Sun and Brian Goetz and David Holmes do too. 
Doug Lea collaborates with Sun a great deal. I observed creation of JCIP 
over a long period of time and sent a few comments to the authors. In 
the process I freely admit I became fully brain washed and believe the 
authors deserve to become stinking rich as a reward for providing JCIP 
to the world.

Tom Roche wrote:
> Pete Soper Wed, May 28, 2008 at 10:30 AM
>  > Even a single, simple (fenceless) CAS
>
> What does "fence" mean in this context? My only contact with the term
> (in an IT context :-) is fencing off a dead node in a cluster, and CAS
> I understand only as an operation (from my one assembler class).
>
> _______________________________________________
> Juglist mailing list
> [email protected]
> http://trijug.org/mailman/listinfo/juglist_trijug.org
>