在什么情况下无锁数据结构比基于锁的数据结构更快？
In what circumstances lock free data structures are faster than lock based ones?
我目前正在阅读 C++ Concurrency in Action 作者 Anthony Williams 的书，其中有几种无锁数据结构实现。在 Anthony 正在写的书中关于无锁数据结构的章节的前面：
This brings us to another downside of lock-free and wait-free code: although it can increase the potential for concurrency of operations on a data structure and reduce the time an individual thread spends waiting, it may well decrease overall performance.
事实上，我测试了书中描述的所有无锁堆栈实现与前面一章中基于锁的实现的对比。而且似乎无锁代码的性能总是低于基于锁的堆栈。
在什么情况下无锁数据结构更优并且必须首选？
无锁结构的一个好处是它们不需要上下文切换。然而，在现代系统中，无竞争锁也是无上下文切换的。要从无锁算法中受益（性能方面），必须满足几个条件：
- 竞争必须很高
- 应该有足够的 CPU 核心，以便旋转线程可以 运行 不间断（理想情况下，应该固定到它自己的核心）
互斥设计很少会执行无锁设计。
所以接下来的问题是为什么有人会使用互斥锁而不是无锁设计？
问题是无锁设计很难做到，需要大量的设计才能可靠；虽然互斥量非常微不足道（相比之下），但在调试时可能会更加困难。出于这个原因，人们通常更喜欢先使用互斥锁，然后在争用被证明是瓶颈后迁移到自由锁。
我几年前做过性能研究。当线程数较少时，无锁数据结构和基于锁的数据结构具有可比性。但是随着线程数量的增加，基于锁的数据结构在某些时候会表现出急剧的性能下降，而无锁数据结构可以扩展到数千个线程。
这取决于发生碰撞的概率。
如果很可能发生冲突，那么互斥锁是最佳解决方案。
比如：2个线程不断的往一个容器的尾部推送数据。
使用无锁只有 1 个线程会成功。另一个将需要重试。在这种情况下，阻塞和等待会更好。
但是如果你有一个大容器，并且 2 个线程将在不同的区域访问容器，很可能不会发生冲突。
例如：一个线程修改容器的第一个元素，另一个线程修改最后一个元素。
在这种情况下，重试的概率很小，所以这里最好是无锁。
无锁的其他问题是自旋锁（大量内存使用）、原子变量的整体性能和对变量的一些限制。
例如，如果您有约束 x == y 需要为真，则不能对 x 和 y 使用原子变量，因为您不能同时更改两个变量，而 lock() 将满足约束
我认为这些答案中缺少的一件事是锁定期。如果你的锁定周期很短，即在获得锁定后，如果你在很短的时间内执行任务（比如递增一个变量），那么使用基于锁定的数据结构会带来不必要的上下文切换，cpu 调度等。在这种情况下，无锁是一个不错的选择，因为线程会旋转很短的时间。
了解哪个更好的唯一方法是对每个进行分析。从用例到用例，从一个 cpu 到另一个，从一个拱门到另一个拱门，从一年到另一年，结果将发生巨大变化。今天可能是最好的，明天可能就不是最好的了。所以总是测量并继续测量。
话虽如此，让我谈谈我对此的一些私人想法：
第一：如果没有争论，你做什么都不重要。 no-collision 案例应该总是很快的。如果不是，那么您需要针对无争用情况调整不同的实现。一种实现可能比另一种使用更少或更快的机器指令并获胜，但差异应该很小。测试，但我希望得到几乎相同的结果。
接下来让我们看一下具有（高）争用的案例：
同样，您可能需要针对争用情况调整实施。一种锁定机制不同于另一种 lock-free 方法。
- 线程 <= 核心数
假设所有线程都运行正在工作是合理的。线程被中断时可能会有小的停顿，但这确实是例外。这显然只有在您只有一个应用程序执行此操作时才适用。所有 cpu 繁重应用程序的线程加起来适用于此场景。
现在有了锁，一个线程将获得锁并开始工作。其他线程可以等待锁可用，并在锁释放时立即做出反应。他们可以忙于循环或更长时间的睡眠，这无关紧要。锁将您限制为 1 个线程进行工作，并且在切换锁时几乎不会浪费任何 cpu 个周期。
另一方面，无锁数据结构都陷入了一些 try&repeat 循环。他们会做工作，在某些关键点他们会尝试提交该工作，如果有争用，他们会失败并重试。经常重复很多昂贵的操作。争论越多，浪费的工作就越多。更糟糕的是，所有对缓存和内存的访问都会减慢最终实际设法提交工作的线程。所以你不仅没有更快地取得进步，你还在放慢进步。
我总是会在任何工作负载上使用锁，这些工作负载比锁指令与无锁实现所需的 CAS（或类似）指令需要更多 cpu 周期。对于 lock-free 方法，它真的不需要太多工作，只剩下微不足道的情况。内置原子类型就是这种情况，通常 CPU 有操作码来在硬件中用一条（相对）快的指令在硬件中执行这些原子操作 lock-free。最后，锁本身将使用这样的指令，并且永远不会比这种微不足道的情况更快。
- 线程 >> 内核
如果您的线程比内核多得多，那么在任何时候都只有一小部分可以 运行。休眠的线程很可能会持有锁。所有其他需要锁的线程也将不得不进入休眠状态，直到持有锁的线程再次醒来。这可能是锁定数据结构的最坏情况。没有人可以做任何工作。
现在有锁的实现（在操作系统的帮助下），其中一个试图获取锁的线程将导致持有锁的线程接管，直到它释放锁。在这样的系统中，浪费被减少为线程之间的上下文切换。
还有一个锁的问题叫雷群问题。如果您有 100 个线程在等待锁并且锁被释放，那么根据您的锁实现和 OS 支持，将唤醒 100 个线程。一个将获得锁，而 99 个将浪费时间尝试获取锁，失败并返回休眠状态。您真的不希望锁实现遭受雷鸣般的攻击。
无锁数据结构在这里开始大放异彩。如果一个线程被取消调度，那么另一个线程将继续其工作并成功提交结果。该线程将在某个时候再次醒来，并且无法提交它的工作并重试。浪费在一个取消调度的线程所做的工作中。
- 核心 < 线程 < 2 * 核心
当线程数接近核心数时，那里有一个灰色区域。阻塞线程 运行ning 的可能性仍然很高。但这是一个非常混乱的地区。那里的结果是什么方法更好是相当随机的。我的结论：如果您没有大量线程，那么请非常努力地保持 <= 核心数。
一些想法：
有时工作一旦开始，就需要按照特定的顺序进行。如果一个线程被取消安排，你不能跳过它。您会在某些数据结构中看到这一点，其中代码将检测到冲突，并且一个线程实际上完成了另一个线程启动的工作，然后它才能提交自己的结果。如果其他的话，这真的很棒线程被取消调度。但是，如果它实际上是 运行ning，那么将工作做两次就太浪费了。所以这个方案的数据结构真正针对上面的场景2。
随着当今移动计算量的增加，考虑代码的功耗变得越来越重要。您可以通过多种方式优化代码以更改电源使用情况。但真正让您的代码使用更少功率的唯一方法是休眠。你听到的越来越多的是“争分夺秒”。如果您可以使您的代码 运行 更快，以便它可以更早休眠，那么您就可以节省电量。但这里强调的是早点睡，或者我应该说多睡。如果你有 2 个线程 运行ning 75% 的时间他们可能会在 75 秒内解决你的问题。但是，如果你可以用 2 个线程 运行ning 50% 的时间解决同样的问题，交替使用锁，那么它们需要 100 秒。但第一个也使用 150% cpu 功率。对于更短的时间，正确，但 75 * 150% = 112.5 > 100 * 100%。在功率方面，较慢的解决方案获胜。有锁让你安然入睡，而无锁则以力量换取速度。
记住这一点，平衡您对速度的需求和为 phone 笔记本电脑充电的需求。
我目前正在阅读 C++ Concurrency in Action 作者 Anthony Williams 的书，其中有几种无锁数据结构实现。在 Anthony 正在写的书中关于无锁数据结构的章节的前面：
This brings us to another downside of lock-free and wait-free code: although it can increase the potential for concurrency of operations on a data structure and reduce the time an individual thread spends waiting, it may well decrease overall performance.
事实上，我测试了书中描述的所有无锁堆栈实现与前面一章中基于锁的实现的对比。而且似乎无锁代码的性能总是低于基于锁的堆栈。
在什么情况下无锁数据结构更优并且必须首选？
无锁结构的一个好处是它们不需要上下文切换。然而，在现代系统中，无竞争锁也是无上下文切换的。要从无锁算法中受益（性能方面），必须满足几个条件：
- 竞争必须很高
- 应该有足够的 CPU 核心，以便旋转线程可以 运行 不间断（理想情况下，应该固定到它自己的核心）
互斥设计很少会执行无锁设计。 所以接下来的问题是为什么有人会使用互斥锁而不是无锁设计？
问题是无锁设计很难做到，需要大量的设计才能可靠；虽然互斥量非常微不足道（相比之下），但在调试时可能会更加困难。出于这个原因，人们通常更喜欢先使用互斥锁，然后在争用被证明是瓶颈后迁移到自由锁。
我几年前做过性能研究。当线程数较少时，无锁数据结构和基于锁的数据结构具有可比性。但是随着线程数量的增加，基于锁的数据结构在某些时候会表现出急剧的性能下降，而无锁数据结构可以扩展到数千个线程。
这取决于发生碰撞的概率。
如果很可能发生冲突，那么互斥锁是最佳解决方案。 比如：2个线程不断的往一个容器的尾部推送数据。 使用无锁只有 1 个线程会成功。另一个将需要重试。在这种情况下，阻塞和等待会更好。
但是如果你有一个大容器，并且 2 个线程将在不同的区域访问容器，很可能不会发生冲突。 例如：一个线程修改容器的第一个元素，另一个线程修改最后一个元素。 在这种情况下，重试的概率很小，所以这里最好是无锁。
无锁的其他问题是自旋锁（大量内存使用）、原子变量的整体性能和对变量的一些限制。
例如，如果您有约束 x == y 需要为真，则不能对 x 和 y 使用原子变量，因为您不能同时更改两个变量，而 lock() 将满足约束
我认为这些答案中缺少的一件事是锁定期。如果你的锁定周期很短，即在获得锁定后，如果你在很短的时间内执行任务（比如递增一个变量），那么使用基于锁定的数据结构会带来不必要的上下文切换，cpu 调度等。在这种情况下，无锁是一个不错的选择，因为线程会旋转很短的时间。
了解哪个更好的唯一方法是对每个进行分析。从用例到用例，从一个 cpu 到另一个，从一个拱门到另一个拱门，从一年到另一年，结果将发生巨大变化。今天可能是最好的，明天可能就不是最好的了。所以总是测量并继续测量。
话虽如此，让我谈谈我对此的一些私人想法：
第一：如果没有争论，你做什么都不重要。 no-collision 案例应该总是很快的。如果不是，那么您需要针对无争用情况调整不同的实现。一种实现可能比另一种使用更少或更快的机器指令并获胜，但差异应该很小。测试，但我希望得到几乎相同的结果。
接下来让我们看一下具有（高）争用的案例：
同样，您可能需要针对争用情况调整实施。一种锁定机制不同于另一种 lock-free 方法。
- 线程 <= 核心数
假设所有线程都运行正在工作是合理的。线程被中断时可能会有小的停顿，但这确实是例外。这显然只有在您只有一个应用程序执行此操作时才适用。所有 cpu 繁重应用程序的线程加起来适用于此场景。
现在有了锁，一个线程将获得锁并开始工作。其他线程可以等待锁可用，并在锁释放时立即做出反应。他们可以忙于循环或更长时间的睡眠，这无关紧要。锁将您限制为 1 个线程进行工作，并且在切换锁时几乎不会浪费任何 cpu 个周期。
另一方面，无锁数据结构都陷入了一些 try&repeat 循环。他们会做工作，在某些关键点他们会尝试提交该工作，如果有争用，他们会失败并重试。经常重复很多昂贵的操作。争论越多，浪费的工作就越多。更糟糕的是，所有对缓存和内存的访问都会减慢最终实际设法提交工作的线程。所以你不仅没有更快地取得进步，你还在放慢进步。
我总是会在任何工作负载上使用锁，这些工作负载比锁指令与无锁实现所需的 CAS（或类似）指令需要更多 cpu 周期。对于 lock-free 方法，它真的不需要太多工作，只剩下微不足道的情况。内置原子类型就是这种情况，通常 CPU 有操作码来在硬件中用一条（相对）快的指令在硬件中执行这些原子操作 lock-free。最后，锁本身将使用这样的指令，并且永远不会比这种微不足道的情况更快。
- 线程 >> 内核
如果您的线程比内核多得多，那么在任何时候都只有一小部分可以 运行。休眠的线程很可能会持有锁。所有其他需要锁的线程也将不得不进入休眠状态，直到持有锁的线程再次醒来。这可能是锁定数据结构的最坏情况。没有人可以做任何工作。
现在有锁的实现（在操作系统的帮助下），其中一个试图获取锁的线程将导致持有锁的线程接管，直到它释放锁。在这样的系统中，浪费被减少为线程之间的上下文切换。
还有一个锁的问题叫雷群问题。如果您有 100 个线程在等待锁并且锁被释放，那么根据您的锁实现和 OS 支持，将唤醒 100 个线程。一个将获得锁，而 99 个将浪费时间尝试获取锁，失败并返回休眠状态。您真的不希望锁实现遭受雷鸣般的攻击。
无锁数据结构在这里开始大放异彩。如果一个线程被取消调度，那么另一个线程将继续其工作并成功提交结果。该线程将在某个时候再次醒来，并且无法提交它的工作并重试。浪费在一个取消调度的线程所做的工作中。
- 核心 < 线程 < 2 * 核心
当线程数接近核心数时，那里有一个灰色区域。阻塞线程 运行ning 的可能性仍然很高。但这是一个非常混乱的地区。那里的结果是什么方法更好是相当随机的。我的结论：如果您没有大量线程，那么请非常努力地保持 <= 核心数。
一些想法：
有时工作一旦开始，就需要按照特定的顺序进行。如果一个线程被取消安排，你不能跳过它。您会在某些数据结构中看到这一点，其中代码将检测到冲突，并且一个线程实际上完成了另一个线程启动的工作，然后它才能提交自己的结果。如果其他的话，这真的很棒线程被取消调度。但是，如果它实际上是 运行ning，那么将工作做两次就太浪费了。所以这个方案的数据结构真正针对上面的场景2。
随着当今移动计算量的增加，考虑代码的功耗变得越来越重要。您可以通过多种方式优化代码以更改电源使用情况。但真正让您的代码使用更少功率的唯一方法是休眠。你听到的越来越多的是“争分夺秒”。如果您可以使您的代码 运行 更快，以便它可以更早休眠，那么您就可以节省电量。但这里强调的是早点睡，或者我应该说多睡。如果你有 2 个线程 运行ning 75% 的时间他们可能会在 75 秒内解决你的问题。但是，如果你可以用 2 个线程 运行ning 50% 的时间解决同样的问题，交替使用锁，那么它们需要 100 秒。但第一个也使用 150% cpu 功率。对于更短的时间，正确，但 75 * 150% = 112.5 > 100 * 100%。在功率方面，较慢的解决方案获胜。有锁让你安然入睡，而无锁则以力量换取速度。
记住这一点，平衡您对速度的需求和为 phone 笔记本电脑充电的需求。