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

Groups > comp.programming.threads > #4237 > unrolled thread

Becareful of Lockfree algorithms

Back to article view | Back to comp.programming.threads

Contents

  Becareful of Lockfree algorithms Sky89 <Sky89@sky68.com> - 2018-05-01 19:52 -0400

#4237 — Becareful of Lockfree algorithms

Hello..


Becareful of Lockfree algorithms

Look at how they are "much" slower than lock based algorithms,
read the following from acmqueue to notice it:

==

In practice, however, lock-free algorithms may not live up to these 
performance expectations. Consider, for example, Michael and Scott's 
lock-free queue algorithm.11 This algorithm implements a queue using a 
linked list, with items enqueued to the tail and removed from the head 
using CAS loops. (The exact details are not as important as the basic 
idea, which is similar in spirit to the example in figure 4.) Despite 
this, as figure 6a shows, the lock-free algorithm fails to scale beyond 
four threads and eventually performs worse than the two-lock queue 
algorithm.

The reason for this poor performance is CAS failure: as the amount of 
concurrency increases, so does the chance that a conflicting CAS gets 
interleaved in the middle of a core's read-compute-update CAS region, 
causing its CAS to fail. CAS operations that fail in this way pile 
useless work on the critical path. Although these failing CASes do not 
modify memory, executing them still requires obtaining exclusive access 
to the variable's cache line. This delays the time at which later 
operations obtain the cache line and complete successfully (see figure 
5b, in which only two operations complete in the same time that three 
operations completed in figure 5a).


Read more here:

https://queue.acm.org/detail.cfm?id=2991130

==



Thank you,
Amine Moulay Ramdane.

[toc] | [standalone]

Back to top | Article view | comp.programming.threads

csiph-web