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

Groups > comp.programming.threads > #1103

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

Show all headers | View raw

>>> 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:

I did not talk about performance so far. Quite often mutexes perform 
even better than lock free implementations. But your implementation is 
not lock free. It is more like a double check. Trying the fast way first 
and falling back to the slow one in doubt.

There are other reasons to use lock free algorithms, of course. Priority 
inversion is one reason. Scalability is another one. Think about 
architectures like Niagara with up to 128 logical cores per chip.

>                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,

And as you can see the speed depends more on implementation issues like 
the mutex implementation than on the algorithm. Furthermore it is not 
that plausible that the simple CAS implementation is slower than the 
more sophisticated approaches.

> but see the bench_atomic test in cppao http://code.google.com/p/cppao/ or just write your own).

The code did not compile on my platform, mainly because of the missing 
C++0x support. But I was able to port it. And I added a new test case, 
that uses a simple spin lock.

In fact it turned out that the time for completion is unstable by a 
factor of 2. I think the threads do not always end at approximately the 
same time. Besides that the simple CAS (with the ABA problem) is as 
expected the fastest one.
[Time units]
CAS: 18
spin lock: 31
new lifo: 48
new fifo: 75

So, who needs a more complicated version than a simple spin lock if it 
is not lock free?
Furthermore, the new fifo sometimes fails with Error in node structure. 
There seems to be a race condition in the code. In contrast I could not 
get the unsafe ABA version to fail.


> I was getting excited probably because the mutex performance on some platforms is particularly bad.

Well, kernel level mutexes are not intended to be called over and over 
at high frequency. Almost any runtime library comes with a fast mutex 
implementation for this purpose.


Marcel

Back to comp.programming.threads | Previous | Next — Previous 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