Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Becareful of Lockfree algorithms
32 views
Skip to first unread message
Sky89
May 1, 2018, 7:52:50 PM5/1/18
to
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.
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.
Chris M. Thomasson
May 1, 2018, 9:27:21 PM5/1/18
to
On 5/1/2018 4:52 PM, Sky89 wrote:
> Hello...
>
>
> Becareful of Lockfree algorithms
>
> Look at how they are "much" slower than lock based algorithms,
> read the following from acmqueue to notice it:
Efficient well designed lock-free is much slower than its mutex based
> Hello...
>
>
> Becareful of Lockfree algorithms
>
> Look at how they are "much" slower than lock based algorithms,
> read the following from acmqueue to notice it:
equivalent? Really, on what planet? Wow.
[...]
Dan Cross
May 1, 2018, 10:35:16 PM5/1/18
to
In article <pcauk8$9sf$3...@dont-email.me>, Sky89 <Sk...@sky68.com> wrote:
>Hello...
>
>[snip]
What does ths have to do with C++?
- Dan C.
>Hello...
>
>[snip]
What does ths have to do with C++?
- Dan C.
red floyd
May 2, 2018, 10:19:40 AM5/2/18
to
0 new messages