Re: A Lock-Free Hash Table - Cliff Click

Thanks for the perspective. That's quite enlightening.

On Wed, May 28, 2008 at 10:30 AM, Pete Soper <[email protected]> wrote:
> 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.)
>>
>
>
>



-- 
/** Shawn.Hartsock http://hartsock.blogspot.com/ //*/