当核心数目很大时，无锁算法往往优于锁定算法吗？

Question

AFAIU有一个共同的想法，即通常无锁代码比锁定代码具有更高的开销。

不过，似乎也有一种观点认为，在竞争情况下，无锁算法更具有可伸缩性。

如果有两个核心，两个线程在std::queue (+互斥锁)和boost::lockfree::queue (MPMC无锁队列)的竞争中竞争，那么锁的性能可能会优于无锁(AFAIU，因为无锁算法的一般开销)。如果我有50个线程，锁定版本将非常慢，因为所有的上下文切换，显式锁车队等。

在这种情况下，AFAIU的无锁版本可能会比锁定版本表现得更好；这大致是真的吗？

然而，在一台2核机器上拥有50个线程对于性能来说并不是一个好主意；所以我想，在至少有50个内核的机器上，一个更相关的问题也是一样的。

2-线程版本一次将使用2个内核，我预计结果将大致相同；为同一个锁而竞争的50个内核怎么办？锁定的影响似乎比2线程版本的影响更大(只有一个线程可以在50个线程中完成工作，而不是在2个线程中完成；因此利用率将不是很高的AFAIU)。那么，在这种情况下，无锁版本的性能是否也优于锁定版本(尽管它仍然是50种中的1种)？

粗略地说，我试图理解“争用下更可伸缩”的概念；我假设在超额订阅情况下，无锁可能会开始优于锁定；

我想问的是，随着HW线程数量的增加，无锁版本的性能是否会超过锁。

P.S.：我知道测量是最重要的，这都是挥手，但也许有一些一般性的想法围绕这.

Answer 1

似乎有一种想法，即在竞争情况下，无锁算法更具有可伸缩性。

这非常依赖用例/上下文，因此它并不总是正确的。一个常见的例子是，与基于锁的实现相比，没有锁的代码使用CAS指令.当存在某些争用时，线程只是试图强行强制访问缓存行，这是效率低下的，因为一次只有一个线程将成功地修改缓存行(假设没有SMT)，而且这使得争用更加糟糕。解决此问题的一个常规方法是使用暂停指令，但这远远解决不了这个问题。实际上，核心运行暂停指令仍然占用处理资源(频率通常保持不变，并且线程调度在硬件线程上，防止其他线程在这段时间内运行)。当线程数大于硬件线程数时，CAS旋转会导致调度问题，因为它们会阻止其他线程进行进度，从而导致不需要的上下文切换具有相当长的量程(通常为5-20ms)。上下文切换是昂贵的，但是操作系统调度程序只在需要时才唤醒任务，并且它们只在准备好的任务上运行。只要就绪任务的数量不太大，延迟也不重要，调度开销就会很好(通常情况下，没有太多的乒乓通信，或者像实时应用程序那样的低延迟要求)。

在实践中，除了用例之外，这些方法的性能非常依赖于硬件和软件栈，例如：

• 原子操作(和缓存访问)的延迟对争用产生了强烈的影响，更不用说内存排序对不同处理器体系结构上原子操作的开销产生了不同的影响(例如。x86对ARM和POWER)；
• ，目标处理器和缓存可以显著影响上下文切换开销(例如。最近的安全漏洞缓解严重影响了这类overheads);
• the调度算法(例如。基本循环对CFS的影响很大。

在这种情况下，

可能比锁定版本执行得更好；这大致是正确的吗？

它取决于调度程序和确切的访问模式。在实践中，调度程序(如Linux上的CFS )可以将两个线程安排在同一个核心上，以减少由于缓存行失效而导致的缓存丢失(尽管稍后并行执行线程时会出现一些延迟开销，就像缓存丢失一样)。访问的粒度对整体性能有很大的影响。对于许多需要乒乓执行的细粒度访问，基于锁的实现将是缓慢的，因为在这种情况下，与原子访问的小成本相比，上下文切换是慢的。对于许多不需要类似乒乓执行的细粒度访问，锁的成本基本上是一个原子访问的成本，没有缓存行无效或任何类型的争用(比x86-64平台上的非原子指令便宜得多，但仍然慢得多)，任务可以排在一个相当大的量程内，因此由于避免了争用，总的执行速度可以快于无锁实现。在实践中，无锁算法往往以较小的粒度影响间接费用(例如.锁定整个函数与多个原子操作)。

对于50线程用例，我同意所提供的解释，因为与上下文交换机的开销相比，CAS的开销应该很小，只有两个核，前提是它们经常进行(见上文)。

，如果50个线程为同一个锁而竞争呢？

这句话让我很困惑:之前的例子不应该是这样的。一个只有一个锁的队列)？

粗略地说，我正试图理解“争用下更可伸缩”的概念；我假设在超额订阅情况下，无锁可能会开始优于锁定；

我认为要记住的关键一点是，争用可以使线程在N核系统上运行一个高度基于原子的无锁代码>N个时间慢，而在最坏的情况下，基于锁的代码可以连续执行。在这种情况下，基于锁的代码速度更快，尽管两者的规模都很差。

这有点像两个开发人员试图同时处理同一个文件，而一个正在等待另一个在修改代码之前完成其任务。在实践中，如果开发人员同时修改文件的相同部分，第二个部分通常会更好(没有提前安排以减少冲突)。有很多线程和很少核心就像有许多任务和很少开发人员一样。好的任务调度可以避免开发人员同时在相同的代码部分上工作，如果任务不需要经常挂起(需要长时间的咖啡休息时间和一些时间来提醒以前的任务)，就可以获得良好的可伸缩性。

和我都在问，随着HW线程数的增加，无锁版本的性能是否会超过锁？

对于在属于同一核心的硬件线程上执行的线程之间的乒乓访问，原子操作可以大大加快。这是因为在主流处理器上由两个硬件线程共享的L1缓存中已经可以使用缓存行。尽管如此，即使在大多数处理器上，原子操作也并不便宜(因为延迟以确保核间原子操作的一致性)。