A Faster Wait-Free Hash Table
I present a wait-free (lock-free) concurrent Hash Table implementation with better single-thread performance than most Hash Tables, and better (usual much better) multi-thread performance than all other implementations I tried. I demonstrate scaling up to 768 CPUs even with high mutation rates. I show correctness by looking at the problem in a very different light than the usual "happens-before" / memory-order / fencing style of thinking -- indeed the algorithm requires no memory-ordering, no memory fencing, no D-CAS and no CAS-spin-loops.
A second talk, time permitting:
Scaling Up A Real Application On Azul
A short case study of a Java application doing device driver model checking. The basic application uses many small independent tasks; doing any one task may produce more tasks. The work is highly unstructured and very fine grained. In theory, this coding style should be endlessly scalable but in practice there were a number of issues mostly due to the fine-grained nature of the tasks. The initial attempt used only a handful CPUs on Azul, but after 3 or 4 small modifications we got all 384 CPUs cranking away - and ran the job 45x faster than the fast P4 it was running on. Time to complete a proof dropped from *weeks* to *hours*.
I'll demo the tools we used to do basic performance analysis, and some techniques to break scaling bottlenecks.
Slides
Download the slides for the Wait-Free Hash Table in PDF Format. Download the slides for the "time permitting" talk on Scaling Up in PDF format.
About the speaker:
Dr. Cliff Click, Azul Systems. Chief JVM Architect, Distinguished Engineer
With more than twenty-five years experience developing compilers Cliff serves as Azul Systems' Chief JVM Architect. Cliff joined Azul in 2002 from Sun Microsystems where he was the architect and lead developer of the HotSpot Server Compiler, a technology that has delivered dramatic improvements in Java performance since its inception. Previously he was with Motorola where he helped deliver industry leading SpecInt2000 scores on PowerPC chips, and before that he researched compiler technology at HP Labs. Cliff has been writing optimizing compilers and JITs for over 15 years. He is invited to speak regularly at industry and academic conferences, and has published many papers about HotSpot technology. Cliff holds a PhD in Computer Science from Rice University.
Contact information:
Cliff Click
1600 Plymouth Street
Mountain View, CA 94043
408-307-0321
cliffc@acm.org