Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #1087

Re: New solution for ABA in lock-free lists?

Show all headers | View raw

On Wednesday, 19 September 2012 23:03:23 UTC+1, Marcel Müller  wrote:
> On 17.09.12 12.13, calum74@gmail.com wrote:
> 
> > The basic idea is to introduce a new state to each pointer: NULL, node and BUSY. The BUSY state acts as a mutex, so if you are unlucky for two threads to access the same memory simultaneously, then the second thread must spin until the pointer becomes non-BUSY.
> 
> A spin lock is nothing but a regular mutex. Your algorithm is no longer 
> lock free, because it does not guarantee forward progress. Think if one 
> thread is stopped by the scheduler while the lock bit is set, you might 
> spin forever. Especially the priority inversion problem applies.
> 
> One solution for the ABA problem is a strictly monotonic revision 
> counter. Or, of course, more sophisticated atomic expression. CAS is not 
> the answer to all questions (this is 42 ;-) ). E.g. optimistic memory 
> locks do not share the ABA problem.

Indeed. What matters not is whether it is lock-free or using CAS, but the real-world performance. The performance is not as horrible as you fear, due to the fact that waiting threads yield, and the probability of starvation is low enough to offset the high cost when it happens. The performance figures I get (with 8 concurrent threads; lower is better) are:

              OSX    Windows  Linux
  Naive LIFO  1.05s  5.14s    2.7s
  New FIFO    0.86s  4.4s     2.5s
  New LIFO    0.77s  4.47s    1.9s
  Mutex       28.4s  10.6s    2.8s

(Of course these numbers are meaningless in isolation, but see the bench_atomic test in cppao http://code.google.com/p/cppao/ or just write your own).

I was getting excited probably because the mutex performance on some platforms is particularly bad. I don't have the time or hardware to test this against some of the more exotic algorithms. The published algorithms are more than likely faster, but would prefer numbers instead of hand-waving.

Calum

Back to comp.programming.threads | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

New solution for ABA in lock-free lists? calum74@gmail.com - 2012-09-17 03:13 -0700
  Re: New solution for ABA in lock-free lists? Marcel Müller <news.5.maazl@spamgourmet.org> - 2012-09-20 00:03 +0200
    Re: New solution for ABA in lock-free lists? calumg <spambox@calumgrant.net> - 2012-09-21 04:20 -0700
      Re: New solution for ABA in lock-free lists? Marcel Müller <news.5.maazl@spamgourmet.com> - 2012-09-28 00:58 +0200

csiph-web