[erlang-questions] : lock-free hash table

[Raimo Niskanen]

Since I am not really into these problems my comments may be
rumour'ish, but anyway...

We are trying to use Atomic operations, in combination with
appropriate algorithms, when possible. Using Atomic-based
(lock-free) research paper data structures is however not
something we have done yet.

There may not be that many data structures in the Emulator
that fit well to e.g FIFO queues, but it sure is worth
keeping in mind.

As an example, the most heavily used locks in the Emulator
are the process locks, so we already do a number of tricks
to firstly save memory not having to use some 10 mutexes
per process, and secondly avoid taking locks all the time.

Up to just recently the SMP work has been about correctness.
If it is not as stable as the non-SMP version, it is
mostly useless. We will optimize while it is stable enough.

One of the first optimizations we are planning is to use
Atomic operations for locking the process table, making
it lock-free. We know of no lock-free data structure
suitable for the job, but we think we can use Atomic
operations anyway. After that we will see which locks
are next to be optimized.

For the record: Atomic operations (necessary for lock-free
data structures) are not that innocent. "single instructions
such as compare-and-swap" sure sound harmless, but for
such an instruction to work in a multiprocessor machine
it will have to invalidate caches on all other processors
as well as write through to real (slow) memory, so it is
a heavy operation. Lighter then mutexes, but the gain
is much smaller than one might expect.



On Tue, Aug 07, 2007 at 10:37:18PM -0500, Serge Aleynikov wrote:
> 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
> 
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions

-- 

/ Raimo Niskanen, Erlang/OTP, Ericsson AB