什么时候无锁数据结构比互斥(互斥体)的性能差? [英] When are lock free data structures less performant than mutual exclusion (mutexes)?

问题描述

我读到某处(无法再找到该页面)，针对某些工作负载"的无锁数据结构更有效，这似乎意味着有时它们实际上速度较慢，或者在某些情况下从中获得的收益可能为零.对我来说，以大约100个周期的命中次数执行锁定指令来执行原子操作比在睡眠和等待调度程序唤醒进程之前快得多，因此在什么情况下无锁数据结构对我来说并不明显不如老式的互斥锁更可取.如果锁有99％的时间可用，并且过程不必进入睡眠状态，那么互斥锁会更快吗?假设有合适的无锁数据结构可用，是否有一条通晓经验的好法则?

I read somewhere (can't find the page anymore) that lock free data structures are more efficient "for certain workloads" which seems to imply that sometimes they're actually slower or the gain from them can be zero in some situations. Taking the ~100 cycle hit of a lock instruction to do an atomic op sounds plenty faster to me than going to sleep and waiting for the scheduler to wake the process back up, so it's not obvious to me under what circumstances a lock free data structure would be less preferable than old fashioned mutexes. If the lock is available 99% of the time and the process doesn't have to go to sleep, is a mutex then faster? Is there a good rule of the thumb for knowing which way to go assuming a suitable lock free data structure is available?

推荐答案

实现无锁数据结构的常用方法是对可变对象进行可变引用，并拥有任何想要更改结构的内容.引用，生成具有适当更改的对象的新版本，然后CompareExchange引用以指向新对象.如果CompareExchange有效，那就太好了.如果没有，请放弃新对象，重新获取引用，然后重新开始.

A common approach to implementing a lock-free data structure is to have a mutable reference to an immutable object, and have anything that wants to change the structure grab the reference, produce a new version of the object with suitable changes applied, and then CompareExchange the reference to point to the new object. If the CompareExchange works, great. If not, ditch the new object, re-grab the reference, and start over.

如果生成新对象的成本很低并且争用程度很低，以至CompareExchange通常可以正常工作，那么这可以很好地工作.如果存在相当大的争用，并且如果生成新对象的速度很慢，则N个线程同时尝试进行更新可能需要N ^ 2的时间才能完成.举一个极端的例子，假设一个CPU上正在运行100个线程，一个更新花费100ms的CPU时间(仅在一个时间片上)，并且所有100个线程试图一次更新一个对象.在最初的十秒钟内，每个线程将在原始线程的基础上产生一个新对象.其中一个线程将成功执行CompareExchange，而其他线程将全部失败.然后在接下来的9.9秒内，将有99个线程生成该对象的新版本，此后一个将成功发布其更新，而98将失败.最终结果是，如果锁定系统可以在大约10秒内完成一次无锁更新，则无锁方法将花费505秒的CPU时间来执行100次更新.

This can work well if producing the new object is cheap and the level of contention is low enough that the CompareExchange will usually work. If there is considerable contention, and if producing the new object is slow, simultaneous attempted updates by N threads may take N^2 time to complete. As an extreme example, suppose 100 threads are running on a CPU, an update takes 100ms of CPU time (just over a time-slice), and all 100 threads attempt to update an object at once. During the first ten seconds, each thread will produce a new object based on the original one. One of the threads will successfully do the CompareExchange, while the others will all fail. Then during the next 9.9 seconds, 99 threads will generate new versions of the object, after which one will successfully post its update and 98 will fail. The net effect will be that the lock-free method will take 505 seconds' worth of CPU time to perform 100 updates, when a locking system could have done them in about 10 seconds.

这篇关于什么时候无锁数据结构比互斥(互斥体)的性能差?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！