Wednesday, May 30, 2007

A Lock-Free Hash Table

Here’s a Google Tech Talk of Cliff Click discussing a Java hash table implementation that supports concurrent access using compare-and-swap rather than locking:

I present a lock-free concurrent Hash Table implementation with better single-thread performance than most Hash Tables, and 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.

1 Comment RSS · Twitter

Too bad his actual implementation code uses Thread.Sleep for resizing.

Leave a Comment