[erlang-questions] Lock-free message queue

[Mikael Pettersson]

=?UTF-8?B?QmrDtnJuLUVnaWwgRGFobGJlcmc=?= writes:
 > On 2010-09-22 14:48, Max Lapshin wrote:
 > > Just a curiosity: currently there is some kind of locks in sending message.
 > > Have anybody tried to implement a lock-free linked list:
 > > http://www.amd64.org/fileadmin/user_upload/pub/epham08-asf-eval.pdf
 > >
 > > Or I'm just looking at wrong place and erts_smp_proc_lock is already
 > > using something like this?
 > 
 > The message queue already has this, sort of. The process that owns the 
 > message box has an "inner box" that he has a lock on and an "outer box" 
 > that all senders compete for. So the lock contention is on the tail of 
 > the queue on the "outer box" when lots of processes sends to that 
 > process. The mail box owner is not concerned with it though.

A problem here is that people seem to equate "lock-free" with
"better than locks".  Both approaches ultimately have similar
hardware costs, namely cache lines ping-ponging over a bus
between caches belonging to whichever package/core/thread wants
ownership at the moment.  If you call it a lock or just do the
appropriate memory barrier + CAS or LL/SC doesn't matter IMO.
In addition, lock-free algorithms generally only work as far
as modifying the shared data structure goes; then there's a
very tricky memory management problem(*), which brings in a
whole new set of problems and possible solutions.

Having said that, I do think that the process in-mbox (the outer
one) is simple and restricted enough that a lock-free solution
should be possible.

(*) When you delete a node from a shared data structure,
_who_ exactly gets to free() that node and when?