ConcurrentDictionary<> 在单线程下的性能误解?

26

相关简要信息:

据我所知,并发堆栈、队列和袋类都是使用内部链接列表实现的。
而且我知道由于每个线程负责自己的链接列表,争用要少得多。 无论如何,我的问题是关于ConcurrentDictionary<,>

但是我正在测试这段代码:(单线程)

Stopwatch sw = new Stopwatch();
sw.Start();

    var d = new ConcurrentDictionary < int,  int > ();
    for(int i = 0; i < 1000000; i++) d[i] = 123;
    for(int i = 1000000; i < 2000000; i++) d[i] = 123;
    for(int i = 2000000; i < 3000000; i++) d[i] = 123;
    Console.WriteLine("baseline = " + sw.Elapsed);

sw.Restart();

    var d2 = new Dictionary < int, int > ();
    for(int i = 0; i < 1000000; i++)         lock (d2) d2[i] = 123;
    for(int i = 1000000; i < 2000000; i++)   lock (d2) d2[i] = 123;
    for(int i = 2000000; i < 3000000; i++)   lock (d2) d2[i] = 123;
    Console.WriteLine("baseline = " + sw.Elapsed);

sw.Stop();

结果:

结果:(测试了多次,数值相同(+/-)。

baseline = 00:00:01.2604656
baseline = 00:00:00.3229741

问题:

什么使得ConcurrentDictionary<,>在单线程环境下变得更加缓慢?

我的第一反应是lock(){}总是会更慢。但显然并不是这样。


4
首先,您是否在“无调试运行”模式下以发布模式运行测试?其次,“每个线程负责其自己的链接列表”是不正确的。如果您想查看这些内容是如何实现的,请从http://referencesource.microsoft.com/netframework.aspx下载库源代码。 - Jim Mischel
7
我很惊讶你会感到惊讶。确保所有操作都是原子级的,需要付出特定代价。在Dictionary的情况下,这个操作本身非常简单(只涉及设置一个数组的值,几乎不包含其他任何东西),但相应的代价却可能很高。与复杂操作相比,这个代价可能是微不足道的。 - Servy
3
这只适用于ConcurrentBag,它与您提到的其他集合有很大区别。例如,不能用相同的方式实现ConcurrentQueue,因为那样它就不会是FIFO了。而ConcurrentStack也不会是LIFO。 - Jim Mischel
好的Jim,谢谢你澄清了这个问题。 - Royi Namir
1
我想你的推理是:“我可以使用锁定或使用由专家编写的ConcurrentDictionary来完成这项工作。既然专家也有使用锁定的选项,那么他们的实现肯定会等于或优于我的。”令人惊讶的是,很多高级方法(例如无锁算法)实际上比标准锁定更耗费资源,但在重负载下,它们的吞吐量更高,因为它们更好地处理争用。另请参见Reed Copsey对另一个问题的回答。 - Brian
显示剩余6条评论
9个回答

32

嗯,ConcurrentDictionary 允许被多个线程使用的 可能性。对我来说,这似乎是完全合理的,因为它需要比那些假设不必担心多个线程访问的东西更多的内部维护。如果安全版本总是比不安全版本更快,为什么你会使用不安全版本呢?如果结果相反,我会非常惊讶。


2
也许这种差异的程度让他感到惊讶? - Servy
6
更好的比较是坦克和跑车之间。坦克更加坚固,但通常速度较慢。 - Jon Skeet
7
@JonSkeet 我不太确定。谁会拒绝开坦克而选择跑车呢!? - Servy
1
我不明白,如果字典锁定起来可以更快地运行,那么为什么还要使用ConcurrentDictionary呢?从像我这样的业余角度(非学术角度),我会简单地在所有可访问的方法上锁定SyncRoot。否则,它可能会变得不安全,或者如何使其更加安全?我不理解。 - M.kazem Akhgary
2
@M.kazemAkhgary:我没有看到任何数字表明,在多个线程上锁定字典比使用“ConcurrentDictionary”更快。这当然不是问题所示的。值得注意的是,除了这里显示的操作之外,还有更多的操作 - 例如迭代字典,您不希望在整个迭代时间内获取锁定。 - Jon Skeet
显示剩余5条评论

30
最有可能的原因是,对于相同的操作,ConcurrentDictionaryDictionary 有更多的开销。如果您深入挖掘源代码,这是可以证明的。
  • 它为索引器使用锁。
  • 它使用易失性写入。
  • 它必须进行非 .Net 原子化值的原子写入。
  • 在核心添加例程中有额外的分支(是否获取锁,进行原子写入)。

所有这些成本都不受使用线程数的影响。这些成本可能单独很小,但并非免费,并随时间累积。


1
@RoyiNamir 不,通常情况下写入默认是原子操作(除了结构体类型 > 指针大小)。 - JaredPar
我在这里阅读(http://igoro.com/archive/volatile-keyword-in-c-memory-model-explained/)得知——在C#中,所有的写操作都是volatile的(不像Java),无论你是写入一个volatile还是非volatile字段。 - Royi Namir
@RoyiNamir 那篇特定的博客文章已经过时,而且如果我没记错的话,对于ARM也不正确。博客作者Igor和我在同一个团队工作。今天他到达后我会亲自询问他这个问题。 - JaredPar
2
@RoyiNamir 我和Igor聊过,他说那行代码在ARM方面确实是不正确的。他最近为MSDN杂志写了两篇文章,据他说这些文章更加更新且考虑到了ARM。http://msdn.microsoft.com/en-us/magazine/jj863136.aspx http://msdn.microsoft.com/en-us/magazine/jj883956.aspx - JaredPar
1
@RoyiNamir 它是一种特定的处理器类型,类似于x86和amd64 / x64。大多数平板电脑都运行在ARM处理器上(iPad,Surface等...) - JaredPar
显示剩余2条评论

14

.NET 5 更新: 我将保留之前的答案,因为它仍然适用于旧版运行时,但是 .NET 5 显然已经进一步改进了ConcurrentDictionary,以至于通过 TryGetValue() 进行读取的速度甚至比普通的 Dictionary 还要快,如下所示的结果(COW 是我下面详细介绍的 CopyOnWriteDictionary)。这是你所能看到的结果:)

|          Method |        Mean |     Error |    StdDev |    Gen 0 |    Gen 1 |    Gen 2 | Allocated |
|---------------- |------------:|----------:|----------:|---------:|---------:|---------:|----------:|
| ConcurrentWrite | 1,372.32 us | 12.752 us | 11.304 us | 226.5625 |  89.8438 |  44.9219 | 1398736 B |
|        COWWrite | 1,077.39 us | 21.435 us | 31.419 us |  56.6406 |  19.5313 |  11.7188 |  868629 B |
|       DictWrite |   347.19 us |  5.875 us |  5.208 us | 124.5117 | 124.5117 | 124.5117 |  673064 B |
|  ConcurrentRead |    63.53 us |  0.486 us |  0.431 us |        - |        - |        - |         - |
|         COWRead |    81.55 us |  0.908 us |  0.805 us |        - |        - |        - |         - |
|        DictRead |    70.71 us |  0.471 us |  0.393 us |        - |        - |        - |         - |

之前的回答仍然适用于 .NET 5 以下版本:

ConcurrentDictionary 的最新版本已经有了显著改进,不再在读取时进行锁定,因此几乎提供与我的 CopyOnWriteDictionary 实现相同的性能特征,并具有更多功能,因此我建议您在大多数情况下使用它。相比于 DictionaryCopyOnWriteDictionaryConcurrentDictionary 仍然有20-30%的额外开销,因此对性能敏感的应用程序仍然可以从使用它中受益。

您可以在此处阅读有关我的无锁线程安全写时复制字典实现的介绍:

http://www.singulink.com/CodeIndex/post/fastest-thread-safe-lock-free-dictionary

目前它是只能追加的(但可以替换值),因为它旨在用作永久缓存。如果您需要删除,则建议使用 ConcurrentDictionary,因为将其添加到 CopyOnWriteDictionary 中会消除所有性能增益,因为会增加锁定。

CopyOnWriteDictionary 写入量短暂时非常快,并且查找通常以几乎标准的 Dictionary 速度运行而无需锁定。如果您偶尔进行写入并经常进行读取,则这是最快的选择。

我的实现通过在正常情况下不需要任何读取锁来提供最大的读取性能,前提是在对字典进行更新时没有进行更新。代价是字典需要被复制和交换(在后台线程上完成),但是如果您不经常进行写入或仅在初始化期间进行一次写入,则这种权衡绝对值得。


1
请注意,最新的ConcurrentDictionary在读取操作时是无锁的。如果您很少写入或更新,它没有太多开销。https://learn.microsoft.com/en-us/dotnet/api/system.collections.concurrent.concurrentdictionary-2?view=netcore-3.0 - Mani Gandham
@ManiGandham 你有对其进行与标准的Dictionary比较的基准测试吗?或者在其他地方找到了基准测试数据吗? - Mike Marynowski
粗略的基准测试对我们来说没有显著的影响。你可能需要自己进行基准测试,但是你可以在代码中看到读取路径:https://github.com/dotnet/corefx/blob/master/src/System.Collections.Concurrent/src/System/Collections/Concurrent/ConcurrentDictionary.cs - Mani Gandham
1
@ManiGandham 很棒 - 相比之前的版本有很大的改进。我刚刚进行了基准测试,它的读取和单线程写入速度基本上与我的相同,所以现在没有使用我的理由了。感谢您提供的信息! - Mike Marynowski
截至.NET Core 3.1的最新更新,经过我实现的一些优化后:在调用TryGetValue时,CopyOnWriteDictionaryConcurrentDictionary快20-30%,具体取决于测试的方式。 - Mike Marynowski

3
ConcurrentDictionary vs. Dictionary
一般情况下,当你需要从多个线程并发地添加和更新键或值时,请使用System.Collections.Concurrent.ConcurrentDictionary。在涉及频繁更新和相对较少读取的情况下,ConcurrentDictionary通常会带来适度的好处。在涉及许多读取和许多更新的情况下,ConcurrentDictionary通常在任何核心数量的计算机上都更快。
在涉及频繁更新的情况下,您可以增加ConcurrentDictionary的并发度,并测量性能是否在具有更多核心的计算机上提高。如果更改并发级别,请尽可能避免全局操作。
如果您只读取键或值,则Dictionary更快,因为如果字典未被任何线程修改,则不需要同步。
链接:https://msdn.microsoft.com/en-us/library/dd997373%28v=vs.110%29.aspx

2
ConcurrentDictionary<> 在创建时会创建一组内部的锁对象(这取决于 concurrencyLevel 等因素),这组锁对象用于通过一系列细粒度的锁来控制对内部桶结构的访问。
在单线程场景下,不需要使用这些锁,因此获取和释放这些锁的额外开销可能是你看到的差异的原因。

2

如果在单个线程中执行所有操作,使用ConcurrentDictionary或同步访问没有意义。当然,字典会胜过ConcurrentDictionary。

很大程度上取决于使用模式和线程数。以下是一个测试,显示随着线程数的增加,ConcurrentDictionary优于字典和锁定。

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading;

namespace ConsoleApp
{

    class Program
    {

        static void Main(string[] args)
        {
            Run(1, 100000, 10);
            Run(10, 100000, 10);
            Run(100, 100000, 10);
            Run(1000, 100000, 10);
            Console.ReadKey();
        }

        static void Run(int threads, int count, int cycles)
        {
            Console.WriteLine("");
            Console.WriteLine($"Threads: {threads}, items: {count}, cycles:{cycles}");

            var semaphore = new SemaphoreSlim(0, threads);

            var concurrentDictionary = new ConcurrentDictionary<int, string>();

            for (int i = 0; i < threads; i++)
            {
                Thread t = new Thread(() => Run(concurrentDictionary, count, cycles,  semaphore));
                t.Start();
            }

            Thread.Sleep(1000);

            var w = Stopwatch.StartNew();

            semaphore.Release(threads);

            for (int i = 0; i < threads; i++)
                semaphore.Wait();

            Console.WriteLine($"ConcurrentDictionary: {w.Elapsed}");

            var dictionary = new Dictionary<int, string>();
            for (int i = 0; i < threads; i++)
            {
                Thread t = new Thread(() => Run(dictionary, count, cycles, semaphore));
                t.Start();
            }

            Thread.Sleep(1000);

            w.Restart();

            semaphore.Release(threads);


            for (int i = 0; i < threads; i++)
                semaphore.Wait();

            Console.WriteLine($"Dictionary: {w.Elapsed}");

        }

        static void Run(ConcurrentDictionary<int, string> dic, int elements, int cycles, SemaphoreSlim semaphore)
        {
            semaphore.Wait();
            try
            {
                for (int i = 0; i < cycles; i++)
                    for (int j = 0; j < elements; j++)
                    {
                        var x = dic.GetOrAdd(i, x => x.ToString());
                    }
            }
            finally
            {
                semaphore.Release();
            }
        }

        static void Run(Dictionary<int, string> dic, int elements, int cycles, SemaphoreSlim semaphore)
        {
            semaphore.Wait();
            try
            {
                for (int i = 0; i < cycles; i++)
                    for (int j = 0; j < elements; j++)
                        lock (dic)
                        {
                            if (!dic.TryGetValue(i, out string value))
                                dic[i] = i.ToString();
                        }
            }
            finally
            {
                semaphore.Release();
            }
        }
    }
}

线程数:1,项目数:100000,循环次数:10 ConcurrentDictionary: 00:00:00.0000499 Dictionary: 00:00:00.0000137

线程数:10,项目数:100000,循环次数:10 ConcurrentDictionary: 00:00:00.0497413 Dictionary: 00:00:00.2638265

线程数:100,项目数:100000,循环次数:10 ConcurrentDictionary: 00:00:00.2408781 Dictionary: 00:00:02.2257736

线程数:1000,项目数:100000,循环次数:10 ConcurrentDictionary: 00:00:01.8196668 Dictionary: 00:00:25.5717232


0

ConcurrentDictionary<,> 在单线程环境下为什么会变得更慢呢?

这是因为在多线程环境下,需要进行额外的机制来提高其速度,而这些机制会增加额外的开销。

我的第一反应是 lock(){} 会一直比较慢。但显然并不是这样。

当没有竞争时,lock 的成本非常低。如果您从单个线程中执行它,每秒可以执行一百万次 lock,您的 CPU 甚至都不会注意到。在多线程程序中影响性能的是锁的争用。当多个线程激烈地竞争同一个锁时,几乎所有线程都必须等待持有锁的幸运者释放它。这就是 ConcurrentDictionary 的优势所在,它采用了细粒度的锁实现。并发性越高(处理器/核心越多),它的优势就越明显。


0
在 .Net 4 中,ConcurrentDictionary 使用了非常糟糕的锁定管理和争用解决方案,使其变得极其缓慢。使用自定义锁定的字典,甚至使用 TestAndSet 来 COW 整个字典都更快。

-7

你的测试有误:在此之前必须停止秒表!

        Stopwatch sw = new Stopwatch();      
        sw.Start();
        var d = new ConcurrentDictionary<int, int>();
        for (int i = 0; i < 1000000; i++) d[i] = 123;
        for (int i = 1000000; i < 2000000; i++) d[i] = 123;
        for (int i = 2000000; i < 3000000; i++) d[i] = 123;
        sw.Stop();
        Console.WriteLine("baseline = " + sw.Elapsed);



        sw.Start();
        var d2 = new Dictionary<int, int>();
        for (int i = 0; i < 1000000; i++) lock (d2) d2[i] = 123;
        for (int i = 1000000; i < 2000000; i++) lock (d2) d2[i] = 123;
        for (int i = 2000000; i < 3000000; i++) lock (d2) d2[i] = 123;
        sw.Stop();
        Console.WriteLine("baseline = " + sw.Elapsed);

        sw.Stop();

--输出:


1
来自 MSDN: "使用 Stop 命令停止当前间隔测量并保留累计经过的时间值。使用 Restart 命令停止当前间隔测量并开始新的间隔测量。" 而且你不需要停止计时器来获取经过的时间,所以他的代码是正确的。 - masimplo

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接