[erlang-questions] lock-free hash table
Wed Aug 8 05:37:18 CEST 2007
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 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:
> 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.
> Ulf Wiger wrote:
>> I just caught Dr. Cliff Click's Google TechTalk on his
>> lock-free hash table.
>> 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. ;-)
>> Ulf W
>> erlang-questions mailing list
More information about the erlang-questions