并行计算

项目
07/09/2015

数据处理：并行和性能

Johnson M.Hart

处理数据集合是一项基本的计算任务，许多实际问题本质上是并行问题，因此有可能在多核系统上实现更高的性能和吞吐量。我将比较几种截然不同的 Windows 方法，通过高度的数据并行来解决问题。

我用于此项比较的基准测试是搜索问题 (Geonames)，该问题来自 Troy Magennis 所著书籍《LINQ to Objects Using C# 4.0》（Addison-Wesley，2010）的第 9 章。备选解决方案包括：

并行语言集成查询 (PLINQ) 和 C# 4.0，无论是否增强原始代码。
使用 C 编写的 Windows 本机代码、Windows API、线程和内存映射文件。
Windows C#/Microsoft .NET Framework 多线程代码。

可以从我的网站 (jmhartsoftware.com) 获得所有解决方案的源代码。没有直接比较其他并行技术，例如 Windows 任务并行库 (TPL)，尽管 PLINQ 是构建在 TPL 基础上的。

比较和评估备选解决方案

按照重要性排列，解决方案评估标准包括：

按照完成任务所需时间计算的总性能。
在并行度（任务数）、内核数和数据集合规模方面的可扩展性。
代码简单性、优美性、易维护性和类似的无形因素。

结果摘要

本文将展示有代表性的基准测试搜索问题的测试结果：

您可以成功利用多核 64 位系统来提高许多数据处理问题中的性能，并且可以在解决方案中采用 PLINQ。
要获得有竞争力的、可扩展的 PLINQ 性能，需要使用带索引的数据集合对象；仅仅支持 IEnumerable 接口是不够的。
C#/.NET 和本机代码解决方案速度最快。
原始 PLINQ 解决方案的速度几乎要慢 10 倍，并且不能扩展到两个任务以上，而其他解决方案可以在六核系统（测试的最多内核数）上成功地扩展到 6 个任务。但是，增强代码可明显改进原始解决方案。
无论从哪方面来说，PLINQ 代码都是最简单、最优美的，因为 LINQ 为驻留在内存中的数据和外部数据提供了声明性查询功能。本机代码非常笨拙；C#/.NET 代码比 PLINQ 要好得多，但是不如后者简单。
所有方法在文件大小方面都能很好地扩展到测试系统物理内存的上限。

基准测试问题：Geonames

本文的想法来自 Magennis 所著的 LINQ 书籍的第 9 章。该章节通过在包含超过 725 万个地名（即，每 1,000 人就会有 1 个以上的位置）、文件大小达到 825MB 的地理数据库中进行搜索，从而演示了 PLINQ。每个地名都通过一条 UTF-8 (en.wikipedia.org/wiki/UTF-8) 文本行记录（可变长度）来表示，其中包含超过 15 个用制表符分隔的数据列。注意：UTF-8 编码确保了制表符 (0x9) 或换行符 (0xA) 的值不会成为多字节序列的一部分；这对于部分实施方案极其重要。

Magennis 的 Geonames 程序通过硬编码的查询来识别海拔（第 15 列）超过 8,000 米的所有位置，然后显示地名、国家/地区和海拔（按海拔的降序排列）。如果您想知道，一共有 16 个这样的地点，其中珠穆朗玛峰最高，达到 8,848 米。

Magennis 报告所用的时间为 22.3 秒（单核）和 14.1 秒（双核）。以前的经验（例如，请参见我的文章“Windows Parallelism, Fast File Searching and Speculative Processing”，网址为 informit.com/articles/article.aspx?p=1606242）表明，这种大小的文件可以在几秒钟内处理完毕，而且性能可随着内核数量的增加而相应提高。因此，我决定尝试再现这种经验，并且还尝试增强 Magennis 的 PLINQ 代码，以便获得更好的性能。最初的 PLINQ 功能增强几乎使性能翻了一番，但并没有提高可扩展性；但是经过进一步增强后，性能几乎与本机代码和 C# 多线程代码一样出色。

由于某些原因，此基准测试非常有趣：

主题（地理位置和特性）本身就饶有趣味，而且很容易推广此查询。
数据并行度很高；从原理上讲，每条记录都可以并发处理。
按照今天的标准，文件大小很普通，但只需将 Geonames allCountries.txt 文件本身反复连接几次，就可以测试更大的文件。
处理是有状态的；有必要确定行和字段边界，以便对文件进行分区，而且必须处理行，以便识别各个字段。

**一项假设：**假设识别出来的记录（在本例中为海拔高于 8,000 米的位置）非常少，因此排序和显示时间与整个处理（需要检查每个字节）时间相比非常少。

**另一项假设：**性能结果显示了处理驻留在内存中的数据集合（例如由前一个程序步骤生成的数据）所需的时间。基准测试程序将读取文件，但是测试程序将运行几次，以确保该文件驻留在内存中。但是，我将提到初次加载文件所需的时间，此时间对所有解决方案几乎都是一样的。

性能比较

第一套测试系统是一台六核台式机系统，其上运行了 Windows 7（AMD Phenom II、2.80 GHz、4GB 内存）。随后，我将展示其他三套系统的结果，这三套系统具有超线程 (en.wikipedia.org/wiki/Hyper-threading) 和不同的内核数。

图 1 以所用时间（以秒为单位）和“并行度”（并行任务数，此值可以大于处理器的数量）之间的关系，显示了六种不同 Geonames 解决方案的结果；测试系统具有六个内核，但实施方案控制的是并行度。六项任务时可达到最优性能；超过六项任务，会导致性能降低。所有测试都使用了原始 Geonames 825MB allCountries.txt 数据文件。

图 1 Geonames 性能与并行度之间的关系

实施方案如下（将在后面进行更全面的解释）：

Geonames 原始方案。这是 Magennis 的原始 PLINQ 解决方案。性能不佳，并且不能随处理器数量进行扩展。
Geonames Helper 方案。这是 Geonames 原始方案 的性能增强版。
Geonames MMChar 方案。此方案尝试利用类似于 Geonames 线程方案 中所用的内存映射文件类来增强 Geonames Helper 方案，但并不成功。注意：内存映射使文件可以像在内存中一样引用，而无需明显的 I/O 操作；它也可以提供性能优势。
Geonames MMByte 方案。此解决方案修改了 MMChar 方案，以便处理输入文件的各个字节，而前三种解决方案将 UTF-8 字符转换为 Unicode（每个为 2 字节）。此方案是前四种解决方案中性能最佳的一种方案，其性能超过了 Geonames 原始方案 的两倍。
Geonames 线程方案 不使用 PLINQ。这是一种 C#/.NET 实施方案，使用了线程和内存映射文件。其性能高于索引方案（下一种方案），与本机代码方案 大致持平。此解决方案与 Geonames 本机代码方案 提供的并行度可扩展性最佳。
Geonames 索引方案。此 PLINQ 解决方案对数据文件进行预处理（大约需要 9 秒钟），创建驻留在内存中的 List<byte[]> 对象，以供后续 PLINQ 处理使用。预处理的代价可被多次查询分摊，因此其性能仅仅比 Geonames 本机代码方案 和 Geonames 线程方案 稍差。
Geonames 本机代码方案（图 1 中未显示）不使用 PLINQ。这是 C Windows API 实施方案，使用了线程和内存映射文件，如我写的书籍《Windows System Programming》（Addison-Wesley，2010）中第 10 章所述。全面的编译器优化对这些结果很重要；默认的优化方式只能实现大约一半的性能。

所有实施方案都是 64 位版的。32 位版在大多数情况下能够正常使用，但是当文件更大时就会失败（请参见图 2）。图 2 显示了并行度为 4 和文件更大时的性能。

图 2 Geonames 性能与文件大小之间的关系

本例中的测试系统具有四个内核（AMD Phenom 四核、2.40 GHz、8GB 内存）。通过连接原始文件的多个副本创建了更大的文件。图 2 仅显示了三种最快的解决方案，包括Geonames 索引方案—最快的 PLINQ 解决方案（不考虑文件预处理）；其文件大小方面的性能可扩展到统物理内存的上限。

我现在将介绍第二种到第七种解决方案，并且深入讨论 PLINQ 技术。在此之后，我将讨论其他测试系统上的结果，并且总结我的发现。

增强的 PLINQ 解决方案：Geonames Helper 方案

图 3 显示了我在 Geonames Helper 方案 中对 Geonames 原始方案 代码的更改（显示为粗体）。

图 3 Geonames Helper 方案，其中突出显示了对原始 PLINQ 代码的更改

class Program
{
  static void Main(string[] args)
  {
    const int nameColumn = 1;
    const int countryColumn = 8;
    const int elevationColumn = 15;

    String inFile = "Data/AllCountries.txt";
    if (args.Length >= 1) inFile = args[0];
        
    int degreeOfParallelism = 1;
    if (args.Length >= 2) degreeOfParallelism = int.Parse(args[1]);
    Console.WriteLine("Geographical data file: {0}.
Degree of Parallelism: {1}.", inFile, degreeOfParallelism);

    var lines = File.ReadLines(Path.Combine(
      Environment.CurrentDirectory, inFile));

    var q = from line in 
      lines.AsParallel().WithDegreeOfParallelism(degreeOfParallelism)
        let elevation = 
          Helper.ExtractIntegerField(line, elevationColumn)
        where elevation > 8000 // elevation in meters
        orderby elevation descending
        select new
        {
          elevation = elevation,
          thisLine = line
         };

    foreach (var x in q)
    {
      if (x != null)
      {
        String[] fields = x.thisLine.Split(new char[] { '\t' });
        Console.WriteLine("{0} ({1}m) - located in {2}",
          fields[nameColumn], fields[elevationColumn], 
          fields[countryColumn]);
      }
    }
  }
}

很多读者可能对 PLINQ 和 C# 4.0 并不熟悉，因此我将对图 3 稍作说明，简单介绍增强功能：

第 9-14 行允许用户在命令行中指定输入文件名和并行度（最大并发任务数）；这些值在原始方案中是硬编码的。
第 16-17 行开始以异步方式读取文件行，并且隐式将行的类型设置为 C# String 数组。这些行的值直到第 19-27 行才会用到。 Geonames MMByte 方案 等其他解决方案使用不同的类，这样的类自己就有 ReadLines 方法，因此只需要修改这些代码行。
第 19-27 行是 LINQ 代码以及 PLINQ AsParallel 扩展。这段代码与 SQL 相似，变量“q”的隐含类型为对象数组，其中的对象由一个整数海拔和一个 String 组成。请注意，PLINQ 执行所有的线程管理工作；AsParallel 方法是将串行 LINQ 代码转变成 PLINQ 代码唯一需要的方法。
第 20 行。 图 4 显示了 Helper.ExtractIntegerField 方法。原始程序在第 33 行中，以类似于用来显示结果的方式使用 String.Split 方法（图 3）。这是 Geonames Helper 方案 与 Geonames 原始方案 相比，能够提高性能的关键，因为它不再需要为每一行中的每个字段分配 String 对象。

图 4 Geonames Helper 类与 ExtractIntegerField 方法

class Helper
{
  public static int ExtractIntegerField(String line, int fieldNumber)
  {
    int value = 0, iField = 0;
    byte digit;

    // Skip to the specified field number and extract the decimal value.
foreach (char ch in line)
    {
      if (ch == '\t') { iField++; if (iField > fieldNumber) break; }
      else
      {
        if (iField == fieldNumber)
        {
          digit = (byte)(ch - 0x30);  // 0x30 is the character '0'
          if (digit >= 0 && digit <= 9) 
            { value = 10 * value + digit; }
          else // Character not in [0-9].
Reset the value and quit.
{ value = 0; break; }
        }
      }
    }
    return value;
  }
}

请注意，第 19 行中使用的 AsParallel 方法可以处理任何 IEnumerable 对象。正如我前面所述，图 4 显示了 Helper 类的 ExtractIntegerField 方法。它只是提取并评估指定的字段（本例中为海拔），避免调用库方法影响性能。从图 1 中可以看出，这种增强使并行度为 1 时的性能翻了一倍。

Geonames MMChar 方案和 Geonames MMByte 方案

Geonames MMChar 方案 使用自定义类 FileMmChar 对输入文件执行内存映射，试图提高性能，但这种尝试并不成功。而 Geonames MMByte 方案 则确实带来了很大的好处，因为输入文件的字节无需扩展为 Unicode。

MMChar 方案 需要一个新的类 FileMmChar，该类支持 IEnumerable<String> 接口。 FileMmByte 类与 FileMmChar 类相似，但处理的是 byte[] 对象，而不是 String 对象。对图 3 所做的唯一重要的代码更改是第 16-17 行，这两行现在为：

var lines = FileMmByte.ReadLines(Path.Combine(
    Environment.CurrentDirectory, inFile));

代码

public static IEnumerable<byte[]> ReadLines(String path)

在 FileMmByte 中支持 IEnumerable<byte[]> 接口，将构造一个 FileMmByte 对象和一个 IEnumerator<byte[]> 对象，后者用于从映射的文件中扫描各个行。

请注意，FileMmChar 和 FileMmByte 类都是“不安全”的，因为它们会创建和使用指针来访问文件，而且它们会交互使用 C#/本机代码。但是，所有的指针使用都隔离在单独的程序集中，并且代码中使用数组而不是指针解除引用。.NET Framework 4 MemoryMappedFile 类在此毫无帮助，因为它必须使用访问器函数，才能从映射的内存中移动数据。

Geonames 本机代码方案

Geonames 本机代码方案 使用了 Windows API、线程和文件内存映射。《Windows System Programming》中的第 10 章介绍了基本代码模式。该程序必须直接管理线程，还必须小心地将文件映射到内存。其性能大大高于所有 PLINQ 实施方案，但 Geonames 索引方案 除外。

但是，在 Geonames 问题与简单的无状态文件搜索或变换之间有一个重要区别。面临的挑战是如何确定对输入数据进行分区的正确方法，以便为不同的任务分配不同的分区。没有什么显而易见的方法可以在不用扫描整个文件的情况下确定行边界，因此为每个任务分配固定大小的分区并不可行。但是，在并行度为 4 时，该解决方案非常直观：

将输入文件分成四个相等的分区，并且将分区的开始位置作为线程函数的参数通知每个线程。
然后，让每个线程处理在该分区中开始的所有行（记录）。这意味着线程可能会扫描到下一个分区中，以便完成对该分区中开始的最后一行的处理。

Geonames 线程方案

Geonames 线程方案 使用的逻辑与 Geonames 本机代码方案 相同；事实上，有些代码完全相同或基本一样。但是，lambda 表达式、扩展方法、容器和其他 C#/.NET 功能则大大简化了代码的编写。

就像 MMByte 方案 和 MMChar 方案 一样，文件内存映射需要使用“不安全”的类，并且需要交互使用 C#/本机代码，以便使用指向映射内存的指针。但所做的工作是值得的，因为 Geonames 线程方案 的性能与 Geonames 本机代码方案 相同，而代码要简单得多。

Geonames 索引方案

与本机代码方案 和 .NET 线程方案 的结果相比，PLINQ 结果（原始方案、Helper 方案、MMChar 方案和 MMByte 方案）均不能让人满意。那有没有办法，既利用 PLINQ 的简单性和优美性，又不至于牺牲性能？

尽管不可能准确知道 PLINQ 如何处理查询（图 3 中的第 16-27 行），但是 PLINQ 很可能没有什么好办法对输入行进行分区，以供各个任务并行处理。认为分区可能是 PLINQ 性能问题的起因，这是一种可行的假设。

从 Magennis 所著的书籍中（第276-279 页），行的 String 数组支持 IEnumerable<String> 接口（另请参见 John Sharp 所著的书籍《Microsoft Visual C# 2010 Step by Step》[Microsoft Press，2010]，第 19 章）。但是，行没有编制索引，因此 PLINQ 可能使用“大块分区”方法。而且，FileMmChar 和 FileMmByte 类的 IEnumerator.MoveNext 方法速度很慢，因为它们需要扫描每个字符，直到下一行所在的位置为止。

如果为行的 String 数组编制索引会发生什么情况呢？我们是不是能提高 PLINQ 的性能，尤其是在通过对输入文件执行内存映射之后？Geonames 索引方案 将此技术产生的结果与本机代码相比，表明此技术确实能提高性能。但是，一般来说，这种技术要么需要先付出代价将各个行移到内存中的列表或数组中，而列表或数组则已经编制索引（这种代价可分摊到随后执行的多个查询）；要么文件或其他数据源已经编制好索引（可能是在前一个程序步骤中生成的），从而消除了预处理代价。

先期的编制索引操作非常简单；只需要依次访问每一行，然后将其添加到列表中即可。在第 16-17 行中使用列表对象（如图 3 所示），并且在以下代码段中也使用列表对象，该代码段演示了预处理：

// Preprocess the file to create a list of byte[] lines
List<byte[]> lineListByte = new List<byte[]>();
var lines = 
    FileMmByte.ReadLines(Path.Combine(Environment.CurrentDirectory, inFile));
// ...
Multiple queries can use lineListByte
// ....
foreach (byte[] line in lines) { lineListByte.Add(line); }
// ....
var q = from line in lineListByte.AsParallel().
WithDegreeOfParallelism(degreeOfParallelism)

请注意，将列表转换为数组，能够稍稍提高数据处理速度，但会增加预处理时间。

最后的性能增强

Geonames 索引方案 的性能还可以进一步提高，只需为每一行中的各个字段编制索引即可。因为这样可使 ExtractIntegerField 方法不需要扫描一行中的所有字符，就能找出指定的字段。

Geonames IndexFields 实施方案修改了 ReadLines 方法，使其返回的行为一个对象，而该对象包含一个 byte[] 数组以及一个包含每个字段的位置信息的 uint[] 数组。此方案与 Geonames 索引方案 相比，性能大约能提高 33%，此性能已经相当接近本机代码和 C#/.NET 解决方案的水平。（Geonames IndexFields 方案 包含在代码下载中。）而且现在也更容易构建更通用的查询，因为各个字段都已经可以直接使用。

局限性

有效的解决方案都要求数据驻留在内存中，而性能优势并不能扩展到超大型的数据集合。本例中的“超大型”是指接近系统物理内存大小的数据规模。在 Geonames 示例中，拥有 8GB 内存的测试系统可以处理 3,302MB 大小的文件（原始文件的四个副本）。我对接起来的八个原始文件副本进行了测试，但所有解决方案的速度都非常慢。

正如前文所述，如果数据文件处于“活动”状态，也就是说数据文件最近被访问过并且很可能在内存中，性能也会达到最佳。在初次运行过程中对数据文件进行分页可能需要 10 秒或更长时间，与上述代码段中的编制索引操作大致相当。

总而言之，本文中的结果适用于驻留在内存中的数据结构，而今天的内存大小和价格也允许非常大的数据对象（例如包含 725 万个地名的文件）驻留在内存中。

其他测试系统结果

图 5 显示了其他系统（Intel i7 860、2.80GHz、四核、八线程、Windows 7、4GB 内存）上的测试结果。处理器支持超线程，因此测试的并行度值为 1、2、……、8。图 1 基于六核 AMD 测试系统；此系统不支持超线程。

图 5 Intel i7 860、2.80GHz、四核、八线程、Windows 7、4GB 内存

其他两种测试配置产生的结果都差不多（我的网站上提供了全面的数据）：

Intel i7 720、1.60GHz、四核、八线程、Windows 7、8GB 内存
Intel i3 530、2.93GHz、双核、四线程、Windows XP64、4GB 内存

有趣的性能特征包括：

Geonames 线程方案 和 Geonames 本机代码方案 提供的性能总是最佳的。
Geonames 索引方案 是最快的 PLINQ 解决方案，其性能接近 Geonames 线程方案。注意：GeonamesIndexFields 方案要稍微快一点，但未显示在图 5中。
除了 Geonames 索引方案 以外，当并行度大于 2 时，所有 PLINQ 解决方案的性能都会随着并行度的提高而降低；也就是说，性能会随着并行任务数量的增加而降低。通过这个例子可以看出，PLINQ 只能对已编制索引的对象产生不错的性能。
超线程对性能的贡献微不足道。因此，对于并行度大于 4 的情况，Geonames 线程方案 和 Geonames 索引方案 的性能并没有明显提高。这种较差的超线程扩展性的起因可能是由于将两个线程安排在同一个内核的逻辑处理器上，而不能确保这两个线程尽可能运行在不同的内核上。但是，这种解释似乎说不通，因为 Mark E.Russinovich、David A.Solomon 和 Alex Ionescu 在他们所著的书籍《Windows Internals, Fifth Edition》（Microsoft Press，2009）的第40 页上说道：在安排计划时，物理处理器优先于逻辑处理器。对于线程方案、本机代码方案 和索引方案，当并行度超过 4 时，与并行度为 1 时的结果相比，不具备超线程功能的 AMD 系统（图 1）提供的性能可达到三到四倍。图 1 表明当并行度与内核数量相同时，性能最佳，此时多线程性能可达到并行度为 1 时的 4.2 倍。

结果摘要

PLINQ 提供了一种优秀的模型，用于处理内存中的数据结构，并且只需实现一些很小的改动（例如 Helper 方案）或更先进的技巧（如 MMByte 方案 所示），就能提高现有代码的性能。但是，任何一种简单的增强都不可能达到与本机代码或多线程 C#/.NET 代码相当的性能。而且，这样的增强不能与内核数量和并行度同步提升。

PLINQ 可以实现与本机代码和 C#/.NET 代码接近的性能，但它需要使用编制好索引的数据对象。

使用代码和数据

我的网站 (jmhartsoftware.com/SequentialFileProcessingSupport.html) 上提供了所有代码，请按照下面的说明进行操作：

访问下载页面，下载包含 PLINQ 代码和 Geonames 线程方案 代码的 ZIP 文件。所有 PLINQ 变化形式均包含在 GeonamesPLINQ 项目中（Visual Studio 2010；Visual Studio 2010 Express 就够用了）。Geonames线程方案 包含在 GeonamesThreads Visual Studio 2010 项目中。这些项目都是针对 64 位版进行配置的。该 ZIP 文件还包含一个电子表格，其中包含图 1、2 和 5 中使用的原始性能数据。该文件的开头包含简单的“用法”说明，解释了用于选择输入文件、并行度和实施方案的命令行选项。
访问 Windows System Programming 支持页 (jmhartsoftware.com/comments_updates.html)，以下载 Geonames 本机代码方案 的代码和项目（一个 ZIP 文件），您可以在此找到 Geonames 项目。ReadMe.txt 文件解释了其结构。
从 download.geonames.org/export/dump/allCountries.zip 下载 GeoNames 数据库。

未探讨的问题

本文比较了几种备用技术的性能，这些技术均用于解决同样的问题。具体的方法是按照说明使用这些技术的标准接口，并且假设处理器和线程采用一种简单的共享内存模式。但是，深入研究底层实施方案或测试计算机的特定功能没有什么明显的效果，而且有大量问题都可以在未来进行探讨。示例如下：

如果缓存未命中，会有何影响？有办法降低其影响吗？
固态磁盘有何影响？
有办法缩小 PLINQ 索引方案 与线程方案 和本机代码方案 之间的性能差距吗？减少 FileMmByte IEnumerator.MoveNext 和 Current 方法中复制的数据量，这样的实验并未显示出任何明显的好处。
性能是否已经接近由内存带宽、CPU 速度和其他体系结构特征所决定的最大值？
有办法让超线程系统（请参见图 5）像不具备超线程的系统（图 1）一样实现可扩展的性能吗？
您可以使用分析工具和 Visual Studio 2010 工具来识别和去除性能瓶颈吗？

我希望您能够深入研究。

Johnson (John) M. Hart 是一位顾问，专门从事 Microsoft Windows、Microsoft .NET Framework 应用程序体系结构和开发、技术培训以及技术写作。他在 Cilk Arts Inc.（自从被 Intel Corp. 收购以来）、Sierra Atlantic Inc.、Hewlett-Packard Co. 和 Apollo Computer 等公司拥有多年的软件工程师、工程经理和架构师经验。他成为计算机科学专家已经有很多年了，并且撰写了四个版本的《Windows System Programming》（Addison-Wesley，2010）。

衷心感谢以下技术专家对本文的审阅：Michael Bruestle、Andrew Greenwald、Troy Magennis 和 CK Park

并行计算

数据处理：并行和性能

Johnson M.Hart

比较和评估备选解决方案

结果摘要

基准测试问题：Geonames

性能比较

增强的 PLINQ 解决方案：Geonames Helper 方案

Geonames MMChar 方案和 Geonames MMByte 方案

Geonames 本机代码方案

Geonames 线程方案

Geonames 索引方案

最后的性能增强

局限性

其他测试系统结果

结果摘要

使用代码和数据

未探讨的问题

其他资源