[erlang-questions] lock-free hash table

Serge Aleynikov <>
Mon Aug 6 01:43:53 CEST 2007


There have been quite a number of publications on the subject of 
lock-free data structures since around mid 90's, most notably by Maged 
Michael (IBM) and Philippas Tsigas / Yi Zhang (Chambers University). 
Here are some selected links:

http://erdani.org/publications/cuj-2004-12.pdf
http://citeseer.ist.psu.edu/sundell04scalable.html
http://www.noble-library.com/
http://research.sun.com/techrep/2002/abstract-110.html

The lock-free algorithms indeed perform exceptionally well in shared 
memory concurrent systems with a large number of CPUs since they don't 
require OS synchronization primitives (relying on a single instruction 
such as compare-and-swap).  I also think that taking advantage of these
algorithms in Erlang's emulator would make it even more scalable on 
large number of cores, especially if interfaces to ports (via shared 
memory) and drivers (via lock-free FIFO circular queues) would offer 
lock-free synchronization with emulator threads.

Serge

Ulf Wiger wrote:
> I just caught Dr. Cliff Click's Google TechTalk on his
> lock-free hash table.
> 
> http://video.google.com/videoplay?docid=2139967204534450862
> 
> The (Java) source is also available
> at sourceforge: http://sourceforge.net/projects/high-scale-lib
> 
> According to his talk, the algorithm "scales well up to 768 cpus".
> 
> I don't know if there is anything in this that would not fit Erlang
> well, but perhaps it's something to look into?
> 
> Anyway, it's always interesting to listen to these performance geeks. ;-)
> 
> BR,
> Ulf W
> _______________________________________________
> erlang-questions mailing list
> 
> http://www.erlang.org/mailman/listinfo/erlang-questions
> 




More information about the erlang-questions mailing list