Re: A Lock-Free Hash Table - Cliff Click

Shawn Hartsock wrote:
> My apologies if you've all already seen this.
>
> ...floating around on Slashdot right now:
> http://video.google.com/videoplay?docid=2139967204534450862
>
>   
Cliff was the technical lead on the Hotspot "server compiler" (aka 
"compiler2") feature, and wrote a large portion of this code. He also 
dictated key architectural aspects of the server compiler, such as a 
novel intermediate representation ("sea of nodes"). Many aspects of 
Cliff's compiler technology are bona fide "state of the art", as the 
timing of his academic work and the need for an advanced dynamic 
compiler for Java was very fortunate. Cliff continues to improve this 
compiler technology and  maintains a collaborative relationship with the 
Sun Hotspot team in a good example of "coopetition" between the two 
companies technical staff.
> In summary Dr. Cliff Click has written a concurrent data structure
> that gets around what many considered intrinsic barriers to
> multi-threaded programming. His talk is very accessible and he makes
> an interesting use of a Finite State machine as proof-of-correctness.
> I'd love to hear this groups take on Azul and these techniques. I'm
>   
IMO it's the very definition of high tech software/hardware cooperation, 
and a distinctive approach to highlylinear scaling. (By highly linear 
scaling I mean, for example, 100X  performance with 100 processors and 
100 threads sharing a task. Crappy scaling would be, for example, 2X 
performance with 3 processors & threads and 2.5X with 10 processors & 
threads).

Rather than a relatively small number of blinding-fast processors and 
collections of apps that tend to not depend on more than small 
concurrency levels (e.g. 2-4) anyway,  the Azul system combines a 
relatively large number of more modest processors combined with very 
efficient synchronization. By Amdahl's Law this pushes the scaleability 
curve way out. So application developers are encouraged to design 
applications that can efficiently take advantage of high levels of 
concurrency (possibly up to what I think is the current cpu limit for 
Azul: 768!) A key piece of the Azul Java environment is brutally fast 
heap management with special hardware assist, which can aid applications 
that aren't at all concurrent per se, but may churn through objects at a 
high rate. And an app that does depend on concurrency must also exist 
with a very efficient heap to avoid memory management being a bottleneck.

There is a bit of marketing spin in Cliff's talk. :-) For example, early 
on he mentions that the java.util.concurrent.ConcurrentHashMap "has 16 
stripes" and suggests it's just not up to the task (of heavy duty 
concurrent apps). But 16 is just  a default: ConcurrentHashMap is highly 
tunable for multiple goals and tradeoffs. I think Cliff's main point is 
that Azul sets the bar higher by virtue of very efficient concurrent 
primitives apps can build upon. But I don't know all the detailed 
differences between j.u.c.ConcurrentHashMap and Cliff's map design: the 
latter could be superior in every way, for all I know. On the other hand 
I suspect if this is true Doug Lea and friends won't let it stay true 
for long. :-)
> also curious if many Java programmers in the triangle have to deal
> with concurrency themselves or if they happily let Spring/J2EE take
> care of the issues by marking things transactional.
>
> The interesting bit in Click's talk (at least to me) is that he has a
> concurrent data structure that is thread safe and doesn't make use of
> a single lock or synchronize. (If he is I'm missing it and would love
>   
This is not quite correct. An early slide shows that "bounded spin 
locks", abortable locks, an atomic CAS (compare and swap) primitives all 
somehow qualify as parts of his "lockless system."  To draw a practical 
analogy, Cliff would seem to want his audience to think of a garden 
variety spin lock being similar to Houdini in his chains, suspended 
upside down in the water-filled chamber, while his synchronization 
techniques with bounded locks, fenceless CAS, etc are more like bumping 
your forehead on a door that was  slammed shut just before you got to 
it: you recover and grab the knob and get through the door relatively 
faster than Houdini can possibly get out of his chains. IMO both 
scenarios involve locks, but relative to the cost of Houdini's 
constraints a simple "one at a time" door or turnstile could be 
considered "relatively lock free."

The truth is that these things are indeed relative and either their is 
synchronization or not: optimization of frequency and overhead is what's 
being discussed. Even a single, simple (fenceless) CAS (atomic compare 
and swap) instruction executing in the context of a lot of contending 
threads constitutes a "got through the door" experience for one thread 
and "bounced my nose off the slammed-shut door" experience for all the 
others arriving at the same spot at the same time (with the same "door 
address"). And this simultaneous arrival happens *a lot more* than 
people might think, and quite often constitutes a measurable factor 
limiting performance. Unsuccessful threads have to stop and wait before 
the hardware will allow their CAS mutation.  This contention seems like 
"nothing", but adds to the accounting of the fraction of overall work 
made up of serialized work and that determines absolute maximum scaling 
in accord with Amdahl's Law. 

And with a fenced CAS the effect can be dramatic, as  current processor 
designs tend to have a lot of concurrent cache and memory operations "on 
the fly" at any moment. When the fenced CAS is encountered the fence 
semantics are kind of like several running school kids crossing a field 
and suddenly coming to a turnstile. These kids have an absolute pecking 
order: they must go through the turnstile in order. And until they are 
all over the CAS itself cannot complete. And memory operations (register 
to L1, L1 to L2, L2, to L3, L3 to "main memory") are disgustingly slow 
relative to the raw speed of CPU operations these days. Meanwhile, the 
cache and memory states of other threads are distrupted by the fence 
(again, if the same logical location is involved), often causing more 
"mad rushes for the turnstile" when each can finally execute the fenced 
CAS.

Adding a single fenced CAS to the innermost guts of Java can have a big 
effect on performance in a concurrent context. One example is the 
transition between native (e.g. JNI) and Java code. There has to be 
coordination of control returning to Java code execution following 
native execution on the one hand and garbage collection "safepoints" to 
do with guarantees about what can and cannot be mutating on the other. 
This coordination used to use fences in Hotspot, penalizing every thread 
with every transition. But now a clever trick with virtual memory page 
privileges is used so that if there is no contention the threads don't 
have to suffer any penalty. If there is simultaneous garbage collection 
going on a cost will be imposed automatically. The value of this 
optimization is quite small to immeasurable for a single threaded app. 
But with a JVM running a thousand threads it is noticeable. :-)

-Pete

> to be corrected.)
>