[erlang-questions] lock-free hash table

[Serge Aleynikov]

Another useful application of SMP-safe lock-free FIFO queues could be 
inside the emulator.  Correct me if I am wrong but in the emulator with 
SMP support different schedulers use mutex synchronization in order to 
get the next process descriptor off of a shared linked list of all 
processes waiting to be dispatched.  Also when copying a message sent by 
some Erlang process to a mailbox of another Erlang process the emulator 
with SMP support uses POSIX locking to ensure thread safety (if I 
remember it correctly).

In both of these cases using lock-free FIFO queues can provide a much 
better scalability when used on multi-core CPUs compared to traditional 
mutex-based locking primitives.

Serge

Serge Aleynikov wrote:
> 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
>> erlang-questions@REDACTED
>> http://www.erlang.org/mailman/listinfo/erlang-questions