使用字典时.NET 4并发性能较差

Question

我试图将一些带有字符串键的数据存储到字典中。数据非常大，例如数以千万计的字符串。因此，我决定开发一个并发版本，以实现更快的执行。然而，并发版本的性能却很差。

我使用了两种策略：

1-将输入分成两个块，并使用两个并发线程将每个块插入两个不同的字典中。

2-使用ConcurrentDictionary调用将整个数据插入到Parallel.ForEach中。

但不幸的是，这两种策略的表现并不乐观。第一种策略是20%~30%更好，这还不够，因为任务之间没有共享数据。并且，并发集合大约是100%慢的！

现在我想知道problem??????？是什么这是否意味着在这个问题上没有机会并行加速？如果有人能帮我，我将感激不尽:)

下面我附上了一个示例代码。

在我的双核AMD Turion系统上，一个示例结果是(毫秒)：

初始化: 542

系列: 294

平行: 234

并发Dic: 666

    static void Main(string[] args)
    {
        System.Diagnostics.Stopwatch watch = new System.Diagnostics.Stopwatch();
        watch.Start();
        Random r = new Random();
        int count=1000000;
        string[] list = new string[count];
        for (int i = 0; i < count; i++)
        {
            list[i] = r.Next(10000).ToString();
        }

        watch.Stop();
        Console.WriteLine("Initialization: "+watch.ElapsedMilliseconds);
        watch.Reset();
        watch.Start();

        Dictionary<string, byte> dic1 = new Dictionary<string, byte>();
        Dictionary<string, byte> dic2 = new Dictionary<string, byte>();
        foreach (var s in list)
            dic1[s] = 0;

        watch.Stop();
        Console.WriteLine("Serial: " + watch.ElapsedMilliseconds);
        watch.Reset();
        watch.Start();


        dic1.Clear();

        Task t1 = new Task(
            () =>
            {
                for (int i = 0; i < list.Length / 2; i++)
                    dic1[list[i]] = 1;
            }
            );
        Task t2 = new Task(
            () =>
            {
                for (int i = list.Length / 2; i < list.Length; i++)
                    dic2[list[i]] = 1;
            }
            );

        t1.Start();
        t2.Start();
        Task.WaitAll(t1, t2);

        watch.Stop();
        Console.WriteLine("Parallel: " + watch.ElapsedMilliseconds);
        watch.Reset();
        watch.Start();

        ConcurrentDictionary<string, byte> dicp = new ConcurrentDictionary<string, byte>();
        Parallel.ForEach(list, s =>
            {
                dicp.AddOrUpdate(s, 1, (k, v) => v);
            }
        );

        watch.Stop();
        Console.WriteLine("Concurrent Dic: " + watch.ElapsedMilliseconds);
        watch.Reset();
        watch.Start();

        Console.ReadKey();

        return;

    }

Answer 1

ConcurrentDictionary速度慢很容易解释:访问任何条目都需要一个锁。它不是为重载而制造的。

很难解释为什么第一个Task-based基准没有看到显著的加速。应该是的。您在几乎没有同步的情况下正确地划分了工作。

也许任务的一次性启动成本约为100毫秒？尝试在一个循环中重复基准测试10次。最后一轮的结果是一样的吗？

尝试创建新的字典。重用一个旧的将从旧的测试中继承状态:一个预先大小的内部数组。

HansPassant在注释中提到，您可能受到内存带宽的限制。我不认为是这样的。字典在内部做了一些不那么便宜的计算，而现代系统没有那么多带宽限制。它们可能是延迟限制的，但不是带宽。

Answer 2

几乎没有什么优化可以实现。1.由于您已经提到了大量的数据，所以尝试将字典的初始大小指定为一个大的数字(大约是您期望存储在其中的数量)。2.在这种情况下尽量避免多线程--我认为这是没有好处的，如果是关于插入的话。

Answer 3

字典的设计并不是为了保存像你这样的史诗般的条目(数千万)。事实上，有一个对ASP.NET的攻击，它完全依赖于asp.net字典很早就开始发生哈希冲突这一事实。

这意味着has必须依赖于它的避碰机制，它通常不是O(1)而是O (n ) (n是碰撞的键数)。正如这次攻击所显示的那样，这可以使字典的速度降低很多。

将哈希冲突与锁定机制结合在一起，您就会有一个显著的减速。

同时，请记住，并行任务是用于需要一段时间且彼此之间不共享大量数据的例程的，比如处理照片。即使有冲突，在字典中添加条目也是非常快的，而且锁定和适口化功能也要慢得多。这再加上一个需要创建的字典(这是并行处理中的一个瓶颈)，并解释了为什么初始化字典需要更长的并行时间。

我希望这是合理的。