3

我正在尝试将一些带有字符串键的数据存储到字典中。数据非常大，例如数千万个字符串。因此，我决定开发一个并发版本以实现更快的执行。但是并发版本的性能非常糟糕。

我使用了两种策略：
1- 将输入分成两个块，并使用两个并发线程将每个块插入两个不同的字典中。
2- 使用 Parallel.ForEach 调用将整个数据插入 ConcurrentDictionary。

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

现在我想知道这是什么问题？？？？？？这是否意味着在这个问题中没有机会并行加速？？？如果有人可以帮助我，我将不胜感激:)

我在下面附上了一个示例代码。
在我的双核 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;

    }
4

5 回答 5

2

ConcurrentDictionary慢很容易解释：访问任何条目都需要锁。它不是为重载而设计的。

很难解释为什么Task基于第一个基准的基准没有看到显着的加速。它应该有。您正确地对工作进行了分区，几乎没有同步。

也许任务的一次性启动成本约为 100 毫秒？尝试循环重复基准测试 10 次。上次运行的结果是否相同？

尝试创建新词典。重用旧的会继承旧测试的状态：预先确定大小的内部数组。

HansPassant 在评论中提到您可能受到内存带宽限制。我认为情况并非如此。Dictionary 在内部进行了一些不那么便宜的计算，而现代系统并没有那么大的带宽限制。它们可能受延迟限制，但不受带宽限制。

于 2012-08-12T22:59:03.643 回答
1

您可以提出一些优化。1.因为您提到数据量非常大，请尝试将字典的初始大小指定为较大的数字（大约是您希望在其中存储的数量） 2.在这种情况下尽量避免多线程- 我认为这里没有任何好处，如果它只是关于插入的话。

于 2012-08-12T22:47:03.753 回答
0

1) 说过。给字典构造函数一个初始大小。这迫使结构至少分配这么多条目/桶。

2）如果可能的话，看看你是否可以使用更短的字符串。

3) 毫无疑问，Dictionary 将在内部进行许多字符串比较。将您自己的字符串比较器传递给 Dictionary 构造函数。

new Dictionary<string, string>(StringComparer.Ordinal);
于 2012-08-12T23:11:42.557 回答
0

您为您的问题建议了 3 种解决方案，即串行、并行和ConcurrentDictionary.

首先，您的第二个解决方案（并行解决方案）是针对与第一个和第三个完全不同的问题的解决方案。它的结果不是单个字典，而其他 2 个解决方案产生单个字典。看起来并行性能更好的原因是它还没有完成。您还有一步要合并dic1和dic2。

无论如何，如果您希望将并行解决方案添加到同一个字典中，则必须添加 alock以避免竞争条件。加锁使您的并行解决方案就像第三种解决方案一样（由于 ConcurrentDictionary 可能有更好的使用锁实现，第三种可能会快一点）。

顺便说一句，当您有一个列表（或字典）要填充，并且所有输入数据都准备好时，瓶颈部分算法就是Add成本。即使你因为使用了多个线程进行添加lock，每个线程都应该等待其他线程完成他们的添加工作。因此，实际上您将有大量线程（任务）相互等待，使您的解决方案像顺序运行一样运行，加上上下文切换的开销。

最后，并行编程根本无法帮助您解决这种情况。要优化您的算法，您应该使添加部分更加优化。例如，您可以为字典设置一个初始大小（帮助 add 方法不运行列表扩展部分）。或者您可以定义一个更快的比较器（在您的字符串太大的情况下）。就个人而言，我认为设计一个优化的比较器会对这种情况下的性能产生很大影响。您可以在比较器算法中使用一些散列。

于 2012-12-07T09:08:00.393 回答
0

字典的设计目的并不是要像您似乎那样容纳大量条目（数千万）。事实上，对 ASP.NET 的攻击完全依赖于 asp.net 字典很早就开始出现哈希冲突这一事实。

这意味着必须依赖它的碰撞避免机制，该机制通常不是 O(1) 而是 O(n)（n 是发生碰撞的键的数量）。正如攻击所证明的那样，这会大大降低字典的速度。

将哈希冲突与锁定机制结合起来，您的速度就会明显下降。

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

我希望这是有道理的。

于 2012-08-12T22:42:44.683 回答