31

我编写了一个非常简单的“字数统计”程序，它读取文件并计算文件中每个单词的出现次数。这是代码的一部分：

class Alaki
{
    private static List<string> input = new List<string>();

    private static void exec(int threadcount)
    {
        ParallelOptions options = new ParallelOptions();
        options.MaxDegreeOfParallelism = threadcount;
        Parallel.ForEach(Partitioner.Create(0, input.Count),options, (range) =>
        {
            var dic = new Dictionary<string, List<int>>();
            for (int i = range.Item1; i < range.Item2; i++)
            {
                //make some delay!
                //for (int x = 0; x < 400000; x++) ;                    

                var tokens = input[i].Split();
                foreach (var token in tokens)
                {
                    if (!dic.ContainsKey(token))
                        dic[token] = new List<int>();
                    dic[token].Add(1);
                }
            }
        });

    }

    public static void Main(String[] args)
    {            
        StreamReader reader=new StreamReader((@"c:\txt-set\agg.txt"));
        while(true)
        {
            var line=reader.ReadLine();
            if(line==null)
                break;
            input.Add(line);
        }

        DateTime t0 = DateTime.Now;
        exec(Environment.ProcessorCount);
        Console.WriteLine("Parallel:  " + (DateTime.Now - t0));
        t0 = DateTime.Now;
        exec(1);
        Console.WriteLine("Serial:  " + (DateTime.Now - t0));
    }
}

它简单明了。我使用字典来计算每个单词的出现次数。风格大致基于MapReduce编程模型。如您所见，每个任务都使用自己的私有字典。所以，没有共享变量；只是一堆自己计算单词的任务。以下是代码在四核 i7 CPU 上运行时的输出：

并行：00:00:01.6220927
串行：00:00:02.0471171

加速比约为 1.25，这意味着悲剧！但是当我在处理每一行时添加一些延迟时，我可以达到大约 4 的加速值。

在没有延迟的原始并行执行中，CPU 的利用率几乎没有达到 30%，因此加速不乐观。但是，当我们增加一些延迟时，CPU 的利用率达到了 97%。

首先，我认为原因是程序的 IO 绑定性质（但我认为插入字典在某种程度上是 CPU 密集型的），这似乎是合乎逻辑的，因为所有线程都从共享内存总线读取数据。然而，令人惊讶的是，当我同时运行 4 个串行程序实例（没有延迟）时，CPU 的利用率达到了大约提高，所有四个实例都在大约 2.3 秒内完成！

这意味着当代码在多处理配置中运行时，它达到了大约 3.5 的加速值，但是当它在多线程配置中运行时，加速值约为 1.25。

你有什么想法？我的代码有什么问题吗？因为我认为根本没有共享数据，而且我认为代码不会遇到任何争用。.NET 的运行时是否存在缺陷？

提前致谢。

4

3 回答 3

55

Parallel.For不将输入分成n块（其中n是MaxDegreeOfParallelism）；相反，它会创建许多小批量，并确保最多n正在同时处理。（这样如果一个批次需要很长时间来处理，Parallel.For仍然可以在其他线程上运行工作。有关更多详细信息，请参阅.NET 中的并行性 - 第 5 部分，工作分区。）

由于这种设计，您的代码会创建并丢弃数十个 Dictionary 对象、数百个 List 对象和数千个 String 对象。这给垃圾收集器带来了巨大的压力。

在我的计算机上运行PerfMonitor报告总运行时间的 43% 用于 GC。如果您重写代码以使用更少的临时对象，您应该会看到所需的 4 倍加速。PerfMonitor 报告的部分摘录如下：

超过 10% 的总 CPU 时间花在垃圾收集器上。大多数经过良好调整的应用都在 0-10% 范围内。这通常是由一种分配模式引起的，该模式允许对象的生存时间刚好足以需要昂贵的 Gen 2 集合。

该程序的峰值 GC 堆分配率超过 10 MB/秒。这是相当高的。这只是一个性能错误并不少见。

编辑：根据您的评论，我将尝试解释您报告的时间。在我的计算机上，使用 PerfMonitor，我测量了 43% 到 52% 的时间花在 GC 上。为简单起见，我们假设 50% 的 CPU 时间用于工作，50% 用于 GC。因此，如果我们使工作速度提高 4 倍（通过多线程），但保持 GC 的数量相同（这会发生，因为在并行和串行配置中处理的批次数量恰好相同），最好的我们可以获得的改进是原始时间的 62.5%，即 1.6 倍。

然而，我们只看到了 1.25 倍的加速，因为默认情况下 GC 不是多线程的（在工作站 GC 中）。根据垃圾回收基础，所有托管线程在 Gen 0 或 Gen 1 回收期间暂停。（在 .NET 4 和 .NET 4.5 中，并发和后台 GC 可以在后台线程上收集第 2 代。）您的程序只经历了 1.25 倍的加速（并且您看到总体 CPU 使用率为 30%），因为线程花费了它们的大部分时间GC 暂停的时间（因为这个测试程序的内存分配模式很差）。

如果启用服务器 GC，它将在多个线程上执行垃圾收集。如果我这样做，程序运行速度会快 2 倍（几乎 100% 的 CPU 使用率）。

当您同时运行程序的四个实例时，每个实例都有自己的托管堆，并且四个进程的垃圾收集可以并行执行。这就是为什么您会看到 100% 的 CPU 使用率（每个进程都在使用 100% 的一个 CPU）。总时间稍长（全部为 2.3 秒，一个为 2.05 秒）可能是由于测量不准确、磁盘争用、加载文件所需的时间、必须初始化线程池、上下文切换的开销或其他原因环境因素。

于 2012-12-02T17:11:10.460 回答
9

试图解释结果：

  • 在 VS 分析器中快速运行表明它几乎没有达到 40% 的 CPU 利用率。
  • String.Split 是主要的热点。
  • 所以共享的东西一定会阻塞CPU。
  • 那很可能是内存分配。你的瓶颈是
var dic = new Dictionary<string, List<int>>();
...
   dic[token].Add(1);

我将其替换为

var dic = new Dictionary<string, int>();
...
... else dic[token] += 1;

结果更接近 2 倍的加速。

但我的反问是：这有关系吗？您的代码非常人为且不完整。并行版本最终创建多个字典而不合并它们。这甚至不接近真实情况。正如你所看到的，小细节很重要。

您的示例代码非常复杂，无法对Parallel.ForEach().
解决/分析一个真正的问题太简单了。

于 2012-12-02T17:09:28.760 回答
0

只是为了好玩，这里有一个较短的 PLINQ 版本：

File.ReadAllText("big.txt").Split().AsParallel().GroupBy(t => t)
                                                .ToDictionary(g => g.Key, g => g.Count());
于 2016-05-11T17:03:12.353 回答