Dictionary + Locking 与 ConcurrentDictionary 对比

• 下载示例 - 49.4 KB

引言

在 .Net 4.0 之前，我们没有选择。如果我们要从多个线程使用字典，就必须处理同步问题。

我敢肯定我们中的许多人创建了自己的线程安全实现，无论是通过创建完整的字典类型（可能性较小）还是仅仅通过创建一个包含字典并将所有方法用锁包装起来的类。

但是现在我们有了 ConcurrentDictionary。在 MSDN - Dictionary 文档 的线程安全部分中指出，如果您需要线程安全的替代方案，请参阅 ConcurrentDictionary。

所以，现在有一个已经线程安全的字典替代品，我们可以停止自己的实现了。这很棒！

是吗？

我想我只真正尝试过一次使用 ConcurrentDictionary。在我最初的速度测试中，它表现出色，所以我立即在一个类中替换了它，进行了一些测试……然后我开始收到异常。

那么，出了什么问题？它不是已经线程安全了吗？

在我的测试中，我发现了问题所在，但是 MSDN 文档中接收委托的 GetOrAdd 方法在框架 版本 4 中没有“备注”部分。但是，请查看 版本 4.5 的文档。它有一个“备注”部分，其中指出

“如果您在不同的线程上同时调用 GetOrAdd，addValueFactory 可能会被调用多次，但其键/值对可能不会每次调用都添加到字典中。”

这就是我的问题所在。当时我不得不进行多次测试才能弄清楚，因为当时没有这样的文档。我使用这种方法的困扰是，我通常使用字典来缓存数据，这些数据

1. 创建速度非常慢；
2. 不能创建两次，要么是因为第二次创建会抛出异常，要么是因为创建两次或更多次会导致资源泄露。

第二种情况是问题所在。如果两个线程都看到值不存在，则它们都首先创建值，但只有一个结果会被真正存储和返回。那另一个呢？

如果创建抛出异常，您可以使用 try-catch 解决问题（这不优雅，但有效），但如果创建了资源却从未被回收呢？

您可能会说，没有任何引用的对象总是会被回收。但是，请再想一想，因为以下情况之一可能正在发生：

• 您正在生成代码。我在我的远程处理框架中这样做，并且我使用一个不可回收的程序集来处理所有实现。如果我创建了两种类型而不是一种，那么它们都会永远存在，即使其中一种从未使用过。
• 您正在直接或间接地创建另一个线程。您可能会创建一个具有自己的专用线程来异步处理消息的组件，但它们会按接收顺序进行处理。所以，您创建了组件，它创建了一个线程。您处置了组件，它终止了线程。但是组件丢失了，并且由于它创建的线程引用了它，所以线程不会死亡，组件也不会死亡。
• 您正在进行 P/Invoke 并接收必须关闭与打开次数相同句柄；
• 我很确定还有很多其他可能的情况。也许字典只是用来保存特定服务器上请求服务的引用，并且您绝不应该在同一服务器上请求两个相同的服务，否则它会记录您正在做坏事（我曾在一家公司工作，这种情况下可能会产生法律惩罚）。

所以，很容易看出，您不能盲目地用 ConcurrentDictionary 替换 dictionary + 锁，即使文档说它是线程安全的等价物。

不确定吗？

您不确定我们是否不会遇到普通字典同样的问题。好吧，根据实现方式，这也可能发生，但让我们看看最简单的策略之一：

TValue result;
lock(dictionary)
{
  if (!dictionary.TryGetValue(key, out result))
  {
    result = createValue(key);
    dictionary.Add(key, result);
  }
}
return result;

在这种情况下，我们在执行搜索时持有完全锁。如果搜索的项目不存在，我们创建它，同时仍然持有完全锁，将其添加到字典中，最后释放锁并返回结果。如果两个线程同时搜索相同的值，一个线程将获胜并完成整个工作，而另一个线程将简单地等待。然后另一个线程获取刚刚创建的结果，并且永远不会尝试创建新结果。

好多了，你不觉得吗？

不完全是。如果创建了两个并行实例，只要只使用一个，我就没有问题。

好的。我所提出的情况并非总是问题。您可以简单地并行创建两个实例并丢弃一个。那么，ConcurrentDictionary 与普通字典 + 锁相比，性能如何呢？

答案是：这取决于锁定策略和您对字典的使用情况。

首先，即使您可以创建相同的值两次，两个线程真正尝试同时创建相同值的几率有多大？

其次，它们在创建这些值时会浪费多少时间？

我很容易就能构建一个例子，其中创建值需要10秒。在创建值5秒后，另一个线程尝试 GetOrAdd 相同的项，也开始创建值。

在这种情况下，我们将有 2 个 CPU 并行工作 5 秒，然后第一个线程完成，第二个线程继续创建它的值再用 5 秒……然后发现那里已经有一个值并使用它，简单地丢弃了它创建的值。

如果第二个线程只是等待，它将让第二个 CPU 执行其他操作（有利于其他不相关的线程、应用程序或电池消耗），它将在 5 秒后而不是 10 秒后获得好的结果。

所以，在这种情况下，赢家是普通字典 + 完全锁。

那是一种虚假情况

好吧，那是一个刻意设计的例子。这并非真正的虚假情况，但对于普通字典的使用来说过于极端。那么，如果第一个线程正在创建一项（10秒），而另一个线程决定读取一个已存在的、不相关的项，会发生什么呢？

嗯，使用 ConcurrentDictionary 是可以实现的，因为它没有持有读取器的锁。而使用普通字典和完全锁，读取器必须等待，仅仅因为锁是独占的，即使它想读取一个完全不相关的桶。

所以，ConcurrentDictionary 在这里胜出。

注意： 我假设您已经了解字典桶、节点/条目。如果您不了解，我建议您阅读 Ofir Makmal 的文章 深入理解泛型字典，他解释得很好，我真的不想偏离本文的重点来重新解释。

多读单写锁

但是，如果使用多读单写锁而不是对普通字典使用完全锁呢？

嗯，如果创建值的线程持有可升级锁，直到值最终存在以将锁类型升级为写入锁，那么读取可以并行进行。

我们将解决读者白白等待10秒的问题。但是，如果您的读取次数远多于写入次数，您会发现 ConcurrentDictionary 仍然更快，因为它实现为使用无锁读取，而 ReaderWriterLockSlim 对于字典读取来说性能很差。通常，对于读取字典来说，使用完全锁比使用 ReaderWriterLockSlim 更可取。

所以，ConcurrentDictionary 又赢了。

注意： 我已经在文章 托管线程同步 中介绍了 YieldReaderWriterLock 和 YieldReaderWriterLockSlim 类。通过使用该读写锁，我在锁本身上获得了显著的速度提升（现在我将其演变为 SpinReaderWriterLockSlim），允许许多读取并行进行而几乎没有影响。我个人仍然使用它，但 ConcurrentDictionary 的无锁仍然更快。

向不同桶的多次写入

故事并未就此结束。如果我们有很多项要添加，所有这些项都具有不同且不冲突的键和桶，会发生什么？

这最初让我感到惊讶，但我做了一个糟糕的例子。我正在使用 int, int 字典，我的工厂立即返回 -key（负键）作为结果。

我期望 ConcurrentDictionary 在这里是最快的，但它是最差的。任何普通字典 + 任何锁都做得更好。那么，为什么呢？？？

嗯，ConcurrentDictionary 分配节点并将其放入其桶中的方式是不同的。它经过优化以实现无锁读取。但是，当添加项时，分配这样的节点成本很高。

即使它可以并行添加许多项，分配这些节点所花费的时间也比使用完全锁要多。

回到主要问题：为什么要使用字典？

老实说，如果我们有创建值的委托，并且它是瞬时完成的，我们就不需要字典，对吧？我们可以直接调用委托，对吧？

嗯……答案，一如既往，是视情况而定。

想象一下，您的键是一个包含您 Web 服务器页面路径的字符串，而值是一种类型，它包含页面上的实际用户数量 + 自服务器启动以来的总访问次数。

创建这样一个计数为零的对象几乎是瞬间完成的。之后，您不会创建一个新的对象，而是在其中更改值。它可以创建两次，只要只使用一个实例。但是，由于 ConcurrentDictionary 的节点分配较慢，您使用普通字典 + 锁可能会获得更好的创建时间。

所以，通过另一个刻意设计的例子，我展示了普通字典是如何更好的……但只是很短的时间。

即使 ConcurrentDictionary 节点分配较慢，我们也不会在几秒钟内尝试将 1 亿个项目放入字典中。这自然需要时间才能发生。

另外，项目创建后总是会被读取。其内容如何更改是另一回事。所以，创建项目多花了几微秒并不重要。它在读取时会更快（好吧，也快了几微秒），但这会更频繁地发生。所以，ConcurrentDictionary 又赢了。

那那些需要时间来创建的不同项目呢？

ConcurrentDictionary 最强的一点。创建许多耗时不同的项并同时添加它们。

ConcurrentDictionary 使用许多不同的锁来允许并发添加项，但决定使用哪个锁的逻辑 + 在调整桶大小时需要获取许多锁并没有真正起到太大作用。将数据放入桶中速度极快。它之所以获胜，真正的原因是它能够并行创建这些值。

但是，等等，我们也可以这样做。如果我们不介意值并行创建并丢失一些，我们可以锁定，检查项是否存在，释放锁，创建值，再次锁定，再次检查，如果需要，添加项。代码如下：

int result;
lock(_dictionary)
  if (_dictionary.TryGetValue(i, out result))
    return result;

int createdResult = _createValue(i);
lock(_dictionary)
{
  if (_dictionary.TryGetValue(i, out result))
    return result;

  _dictionary.Add(i, createdResult);
  return createdResult;
}

* 请记住，我正在使用 int, int 字典。

通过这种简单的结构，当并行添加创建缓慢的项时，普通字典的性能几乎与 ConcurrentDictionary 一样好。但同样存在一些值可能被生成但从未使用过的问题。

结论

那么，有什么结论吗？

嗯，此刻，我有一些想法。

1. 所有字典都很快。我正在创建数百万个项目，它仍然很快。我们通常只会创建少量项目并间隔读取它们，所以我们不会察觉到读取它们所花费的时间；
2. 如果您不能创建相同的值两次，请忘记使用 ConcurrentDictionary；
3. 如果您确实关心最终性能，那么使用普通字典 + 完全锁可能仍然会获得更好的性能。在这种情况下，重要的因素是添加和删除操作的数量。遗憾的是，读取速度会比使用 ConcurrentDictionary 慢；
4. 尽管我没有展示，但使用字典和锁，您拥有更大的自由度。您可以一次性锁定并添加多个项目，删除多个项目，执行多次搜索，然后才释放锁；
5. 如果您通常读取次数远多于写入次数，请避免使用 ReaderWriterLockSlim。字典速度非常快，以至于完全锁比读取锁更快。在这种情况下，这取决于您在锁内创建值花费了多少时间（如果您这样做）。

所以，我认为即使我的例子比较极端，它们也向我们展示了 ConcurrentDictionary 并非总是最佳解决方案。

理解差异

嗯，开始写这篇文章的主要原因是我一直在寻找更好的解决方案。

我能说什么呢，我试图深入理解字典的工作原理（我想我现在确实理解了它们）。

我可以说 ConcurrentDictionary 的桶和节点更简单。当我第一次尝试创建字典时，我做了一些非常相似的事情。看起来更简单的普通字典类实际上更复杂。

在 ConcurrentDictionary 中，每个节点都是一个完整的类。在普通的 Dictionary 中，节点由值类型实现，所有这些节点都在一个巨大的数组中，而桶是指向该数组中查找这些节点的索引。此外，下一个节点不再是对另一个节点的简单引用，而是该数组中的一个引用（毕竟，结构体节点不能将结构体节点作为成员）。

在添加和删除时，普通字典不能简单地创建一个新节点，它必须检查是否存在已删除节点的索引以取代其位置，否则它将使用“Count”作为新节点在节点数组中的位置。实际上，当所有节点都填满时，普通字典强制进行大小调整。

使用 ConcurrentDictionary，节点只是一个新对象。删除节点只是失去其引用。添加节点只是创建新的节点实例并指向它。大小调整仅用于避免冲突，但它们不是强制性的。

那么，如果 Dictionary 使用更复杂的算法（有意为之），ConcurrentDictionary 如何才能更好地实现多线程呢？

事实是：将所有节点放在一个数组中，分配和读取速度都快得多，即使我们需要另一个数组来指示在哪里找到这些项。它最初为相同数量的桶使用了更多的内存，但是新项不需要新的分配，不需要新的对象同步，也不强制进行新的垃圾回收。它们已经存在了。

但是，替换节点内容不是“原子”操作，这是使其线程不安全的事实之一。对于作为对象的节点，首先创建整个节点，然后只需要更新单个引用以指向它（这是一个原子操作）。因此，读取线程可以在没有锁的情况下读取字典。它们将读取旧值或新值。没有读取不完整值的可能性。

所以，真相是：普通字典读取速度更快，只要你不需要加锁。正是读取时的锁使得它们在读取时变慢。

做得更好

做得更好有点问题。每个字典都有一个有效的方法，有优点也有缺点。它们只是不同的优点和缺点。

我想要的是兼得两者的优点，但这根本不可能。所以我必须选择……并验证我选择的方案是否可以做得更好。

或者，两者都尝试。

为了更好地理解，我做了一个完整的字典实现，使用了与普通字典相同的方法。我实际上得到了相同的速度。然后我尝试使其线程安全，将锁精确地放置在它们应该在的地方，并避免重复读取。

解释一下，对于普通字典，我可以使用读锁，尝试查找一个项，如果它不在那里，我进入一个可升级锁，但我必须再次搜索（因为在转换期间，其他线程可能已经创建了值）。

在我自己的实现中，我将桶和版本保存在内存中。如果版本没有改变，我不需要进行第二次搜索，我可以直接创建值，然后升级到写锁。

嗯，它的性能很好，但仍然，我的通常情况是少量写入和大量读取。所以，最好是进行完全避免锁定的读取。

所以，我做了另一个实现。现在，每个节点都是一个普通引用。创建项目更慢，但读取更快。

我使用我自己的 SpinReaderWriterLockSlim（在大多数情况下比 ReaderWriterLockSlim 快得多）来处理需要锁定的情况，但大多数读取都是无锁的。在我的测试中，它运行良好，但我仍然存在两个不相关的值无法一次性写入的问题。

我决定更进一步，让每个桶都有自己的锁。因此，在添加一个项时，我获取了桶的读锁（表示：不要调整桶的大小），并获取了桶本身的写锁。这让我能够并行创建两个值，而不会产生重复。

结果呢？嗯，添加项目变慢了，因为现在我有两个锁而不是一个。好吧，在许多写入不同节点的情况下，它更快，甚至比 ConcurrentDictionary 还要快，但这并非我的主要目标。我通常有大量的读取和一些写入，需要“以防万一”发生冲突而进行保护。

所以，我移除了那些次要锁。然而，读取的无锁特性允许在有写入操作时进行读取。这比“多次读取”或“单次写入”要好得多。读取器永远不必等待。在 10 个线程读取，一个线程创建值长达 10 秒的情况下，我可以自由读取，而不是让 10 个线程等待。

我能做些什么来使其更好？

在许多情况下，使用单个读写锁已经比 ConcurrentDictionary 更好，因为调整大小更快。

考虑到我的乐观锁在没有并发时也表现出色，因此在没有真正的同时写入时它会更好，但如果发生这种情况，它也会受到保护。

那么唯一缺少的就是专用方法。正如我所说，使用字典 + 锁，我们可以一次性添加许多项。那么，为什么我的字典中不能有这个选项呢？

我就是这样做的。我尝试在字典中放置许多“多操作方法”，这些方法在执行这些操作时只进行一次锁定。

因此，您拥有 GetOrCreateValue（它是 ConcurrentDictionary's GetOrAdd 的安全等价物，但在普通字典中没有等价物）、TryGetValueAndRemove 和其他方法，例如 RemoveMany，它可以接受一个委托来检查所有项目并告知应该删除哪些（避免多次搜索），或者可以接收一个键集合以在单个锁中删除（因为获取和释放锁是耗时的）。

此外，考虑到 ConcurrentDictionary 的 GetOrAdd 方法（即使会丢弃一些值，也可以并行创建两个或更多值）具有其优势，我决定提供 GetOrCreateDiscardableValue。如果需要创建值，它会在锁之外创建，但如果在 meantime 其他线程放置了一个值，则会使用该其他值。但我的版本有一个优势，您可以提供一个委托来正确地丢弃生成的值。

毕竟，谁知道呢？你并行调用了一些函数，这没问题，但如果其中一个生成的值不会被使用，你必须正确地丢弃它（例如，许多 P/Invoke 返回的句柄必须与打开的次数相同地关闭）。

最后，我决定向字典添加一个 Lock() 方法，该方法返回一个可处置的 LockedDictionary。有了它，您可以在仍然持有锁的情况下执行许多自己的操作，而无需任何方法尝试获取额外的锁，然后您处置该锁定的字典以释放锁。

我真的认为，有了所有这些额外的方法，这样的实现在许多性能和线程安全同样重要的不同场景中更为完整。

我还决定让我的字典更符合《单一职责原则》，因此它不实现普通的 IDictionary 接口，因为我认为它包含 SyncRoot、Keys 作为 ICollection 而不是 IEnumerable 等成员过于臃肿。此外，它不实现序列化特定任务（如果您想序列化它，请使用允许注册序列化程序的框架），但同时它作为字典更完整，并且还具有列表和哈希集可用的 TrimExcess() 方法。

示例

正如我常对这类文章所做的那样，示例是一个程序，它简单地比较了文章中讨论的许多技术和情况的性能。

它没有比较我的字典实现的所有额外方法，但您已经可以看到锁定技术的不同，而且我的字典在普通方法下已经表现出色，额外方法正是为了进一步提高性能而提供的。

您将找到我的字典以及我的 SpinReaderWriterLockSlim 的完整源代码，该锁被我的字典使用。

关注点

对我来说，其中一个有趣的点是，MSDN 文档如何让人认为 ConcurrentDictionary 只是在需要多线程时替换字典的简单替代品，而这并非总是如此。

此外，我自己实现代码也让我有机会创建不同类型的字典。例如，ThreadSafeDictionary 更像 ConcurrentDictionary，WeakDictionary（本文未提及）更像普通 Dictionary（因为项目经常被回收和移除），而且我还在创建一个 BigDictionary，它允许我创建非常大的字典（如果内存足够，可以包含超过 30 亿个项目）。

谁知道呢，也许我现在知道如何以不同方式处理节点和哈希码后，我可以考虑创建自己的支持索引的数据库。

Thread.MemoryBarrier

我已经结束了关于一种字典与另一种字典的讨论。现在我将谈谈我在 ThreadSafeDictionary 中做出的一个决定。

我从不使用 Thread.MemoryBarrier()。无论是在写入还是读取时。

如果我们查看互联网上的 ConcurrentDictionary 源代码（或者如果我们对其进行反编译），我们会看到读取方法首先从桶中读取节点，然后执行内存屏障，最后开始读取节点内容并获取新节点。

另一方面，写入操作没有任何内存屏障。

我查看了许多地方，试图理解这个推理。理论上，Thread.MemoryBarrier() 调用应该在新对象可供其他线程使用之前（即，在填充属性后，我们执行 Thread.MemoryBarrier()，然后设置一个共享变量）以及从共享变量读取引用但读取其内容之前执行。

这与缓存读取和写入数据的方式有关。理论上，我们可能会创建一个对象，填充其内容（内容保留在 CPU 内存中），然后设置一个立即写入主内存的引用。也就是说，主内存有一个最新的引用，指向的内容仍然不是最新的（并且包含垃圾）。

但为什么 ConcurrentDictionary 不这样做，为什么它只在读取时使用 Thread.MemoryBarrier()？

嗯，显然，.Net 上所有对公共内存的写入都具有“释放”语义，这意味着当我这样做时

_globalVariable = x;

它将确保 x 的所有内容在将 x 放入 _globalVariable 之前被刷新到主内存。

那么，为什么在读取时有 Thread.MemoryBarrier() 呢？

从我看到的相同来源，写入保证具有“释放”语义，而读取不保证具有“获取”语义。

也就是说，如果 CPU 1 在一次操作中已经缓存了包含 x 内容的内存区域，CPU 2 可以更改这些内容，将 _globalVariable 更改为 x，然后 CPU 1 可以读取 _globalVariable，指向它已经缓存了错误值的内存区域。

所以，在获取 _globalVariable 引用之后立即设置一个读屏障是好的。在特定情况下，这发生在从桶数组中读取节点引用时。

但是.Net没有读屏障，它是一个全屏障，这会导致很大的性能损失，而且

1. 在 ConcurrentDictionary 中，屏障是在读取第一个节点后完成的，而不是在遍历后续节点时。我最初认为这是可以的，因为插入会替换第一个节点，但更新会替换任何节点，所以，如果需要屏障，则所有节点都需要屏障（或者在更新时，所有节点都应该被复制，然后替换整个桶，而不是桶中的单个项）；
2. 我就是无法在我的电脑上模拟这种情况。显然，这个问题只在 Itanium 处理器上可见，并且永远不会在我的电脑上发生。但是，由于我无法重现问题，我宁愿避免某些无故降低我代码速度的东西（毕竟，如果我仍然做错了什么，我将永远无法测试）；
3. 新节点在其构造函数内部填充。它不是：创建对象，填充它，将其显示给其他线程。或者更糟：创建对象，填充它，将其显示给其他线程，现在更改其内容，尝试再次显示它。真正的代码是：创建时填充它。现在它已完成，将其显示给其他线程和 CPU。在这里，我相信 .Net 框架绝不会让线程第一次看到引用并看到可能已经被 CPU 预取了垃圾的内容。那将是可怕的，特别是在处理窗口句柄和其他 P/Invoke 时；
4. 在这篇 MSDN 文章 中，技术 1 正是我所做的，没有任何内存屏障用于读取，考虑到文章的作者，我相信这是一种安全的技术。

所以，为了结束这个话题，我没有在我的实现中放置任何 Thread.MemoryBarrier()。如果我的实现在 Itanium 处理器上确实引起问题，我将考虑创建一个针对 Itanium 的特定编译，其中包含这样的内存屏障，就像我处理需要写入内存屏障的处理器或 .Net 实现一样。但是，目前，我可以让 CPU 缓存自由地进行读取工作。

版本历史

• 2013年3月7日。修正了 TryGetValueAndAddOrReplace() 的返回值，原先是反向的；在无类型字典接口中添加了 TypeOfKey 和 TypeOfValue 属性；并在 ThreadSafeDictionary 中添加了对使用不同锁的支持。在单 CPU 机器上，将使用 OptimisticReaderWriterLock 而不是 SpinReaderWriterLockSlim。
• 2013年2月18日。第一版。