C# 中快速和不那么快的循环

• 下载缓存测试 - 92.15 KB

引言

在完成了关于 QS 的第一篇文章后，我决定使用该工具进行一些实验，以研究 CPU 缓存如何影响性能。在这些实验中，我获得了一些关于各种 C# 结构性能的见解，我将在本文中与您分享。

背景

您的 PC 的内存系统很可能由大但慢的主内存和更小但更快的 CPU 缓存组成，用于指令、数据和虚拟内存管理。我最初要进行的实验是关于数据缓存，特别是关于读取性能，所以这里简要而简化地描述一下内存读取是如何工作的。

当访问内存地址时，CPU 会将其请求发送到最近的缓存（L1），如果缓存包含该地址的值，它会简单地返回该值。事实上，缓存不会只返回该值，而是准备好包含该地址的整个行（在我的系统上是 64 字节）。诀窍在于，查找行并准备好它很慢（在我机器上需要 3 个时钟周期），而获取数据很快（每周期 1 字），所以如果 CPU 在接下来的几个周期中请求该行中的其他数据，那么这些数据将比第一个数据快得多。CPU 会尽最大努力预测下一个内存访问，以便在 CPU 处理第一行数据时，缓存可以准备好下一行。

那么，如果 L1 缓存不包含我们要查找的数据会怎样？L1 缓存会查找 L2 缓存，如果找到了，会发生与上述相同的情况，但这次的延迟更高（在我机器上需要 17 个时钟周期）。如果 L2 中也没有呢？然后会访问主内存（或者 L3，如果存在这样的缓存），同样会增加延迟，这次在我系统上高达 290 个周期！

如果您想了解更多关于缓存工作原理的信息，请参阅 Wikipedia 上的文章 http://en.wikipedia.org/wiki/CPU_cache，或查看位于 http://www.unilim.fr/sci/wiki/_media/cali/cpumemory.pdf 的文档“程序员应该了解的关于内存的一切”。

如果您对自己的系统感到好奇，可以使用基准测试工具来查找其特性。我在本文中使用了来自 http://www.sisoftware.net/ 的 SiSoft Sandra。

测量缓存效果

如何测量缓存的效果？这需要分配不同大小的缓冲区，并在读取这些缓冲区时计时；如果缓存适合 L1，我们应该期望快速的访问时间，而如果数据在 L2 或主内存中，则时间会变慢。实际上，情况更复杂，由于行大小、关联性、预取和 CPU 内部流水线等因素，不同的访问模式会产生不同的结果，但第一步是找出 C# / .NET 是否足够快以揭示任何缓存效果。这个问题是本文其余部分的重点。

在开始之前，这是我系统的一些信息

CPU: Intel T9600 dual core CPU @ 2.8GHz
L1i & L1d caches each 16KB
L2 cache 6MB shared between cores
Main memory: 4 GB dual channel PC6400 DDR2 RAM
Max theoretical transfer rate (MTTR) = 12.8 GB/s.

由于我使用的是 32 位操作系统，我假设单个线程的 CPU 每周期最多可以从内存系统（即 L1d 缓存）读取一个 32 位字。在 2.8 GHz 下，这产生了从 L1d 到核心的最大理论传输速率为 11.2 GB/s。

测量

我最初打算进行的实验是看看我能接近 L1d->Core 传输速率 11.2 GB/s 的程度。这涉及到创建许多具有不同循环结构并使用不同数据类型的函数。所有实验都有一个内循环和一个外循环，在外循环的许多实验中，循环已被展开。内循环顺序读取并累加一个 4KB 缓冲区的内容到一个局部变量（累加是为了防止编译器消除循环体），而外循环重复进行，直到读取了总共 64MB 的数据。4KB 缓冲区适合 L1d 缓存，确保了尽可能快的内存访问，因此任何性能差异都与循环结构有关。

关于测量，所有测量都至少重复了 100 次，并选择了最佳执行时间。

下表显示了结果，正如您所见，最快的循环和最慢的循环之间有近 10 倍的差距。周期数是基于 11.2 GB/s 的最大传输速率假设计算的。

方法	时间 (毫秒)	传输速率 (GB/s)	% 最大	每个读取的周期数	每次迭代的读取次数	每次迭代的周期数
验证 64 位读取（long）不会增加传输速率
For4_Unroll4_Long	17,36	3,87	35%	2,90	4	11,59
索引缓冲区和展开次数不同的方法
For4_Unroll4 For-循环，展开 16 次，前缀++	6,23	10,76	96%	1,04	16	16,65
For4_Unroll3 For-循环，展开 4 次，前缀++	7,52	8,93	80%	1,25	4	5,02
For4_Unroll2 For-循环，展开 4 次，后缀++	14,76	4,55	41%	2,46	4	9,85
For4_Unroll1 For-循环，展开 4 次，索引 + 偏移	8,91	7,53	67%	1,49	4	5,95
For4_Foreach Foreach 循环	8,92	7,52	67%	1,49	1	1,49
设置循环的不同方法
For1_For1 循环变量在循环中声明，循环中读取自定义属性。	17,71	3,79	34%	2,96	1	2,96
For1_For2 循环变量在循环中声明，循环中读取array.length 属性。	11,84	5,67	51%	1,98	1	1,98
For3_For3 循环变量在循环中声明，循环前读取array.length 属性。	11,87	5,65	50%	1,98	1	1,98
For4_For4 循环变量在循环外声明，循环前读取array.length 属性。	11,91	5,64	50%	1,99	1	1,99
BORDER-TOP: #f0f0f0; BORDER-RIGHT: windowtext 1pt solid; PADDING-TOP: 0cm"> For4_For5 循环变量在循环外声明，循环前读取array.length 属性，在循环体内递增索引	11,82	5,68	51%	1,97	1	1,97
For4_While 内循环使用while	11,82	5,68	51%	1,97	1	1,97
For4_DoWhile 内循环使用do-while	11,80	5,69	51%	1,97	1	1,97
使用通用 List<int> 而不是数组 int[]
For4_Unroll4_List	23,82	2,82	25%	3,98	16	63,60
For4_Foreach_List	59,04	1,14	10%	9,85	1	9,85

建立基线

最快的循环 “For4_Unroll4” 非常接近最大理论速度，实现如下：

int unused = 0, i, j;
int imax = b.spec.CountIterations;
int jmax = b.spec.CountItems;
TestContext.Current.Timer.Start();
for (i = 0; i != imax; ++i)
{
  for (j = 0; j != jmax; )
  {
    unused += b.intArray[j]; ++j;
    // repeated 16 times
  }
}
TestContext.Current.Timer.Stop();

For4_Unroll3 完全相同，但只展开了四次，而 Unshared_For4_For5 具有相同的结构，没有展开。从 For4_For5 到 For4_Unroll3，展开将内循环的迭代次数从 1600 万减少到 400 万，减少了 75%；从 For4_Unroll3 到 For4_Unroll4，又减少了 75%，降至 100 万次迭代。由于所有方法执行相同的累加 1600 万个整数的工作，唯一的区别是内循环重复的次数，我们可以比较每个迭代的周期数，这表明循环本身（即比较和分支）大约需要 1 个周期，而读取整数、将其添加到局部变量和递增索引需要另一个周期。

后缀递增被视为有害

后缀运算符（例如 i++）通常被认为是不好的风格，因为它们容易出错，但它们仍然可以为懒惰的程序员节省一些按键次数。考虑方法 For4_Unroll2 的内循环：

for (j = 0; j != jmax; )
{
  unused += b.intArray[j++];
  unused += b.intArray[j++];
  unused += b.intArray[j++];
  unused += b.intArray[j++];
}

它确实比 For4_Unroll4 的代码更短、更简洁，但有趣的是，您不仅会受到代码警察的惩罚，而且在性能上也会遭受严重打击。此代码的执行时间是使用前缀递增的展开版本的两倍！

后缀递增会产生开销，因为在递增之前必须制作原始值的临时副本，而且我们显然不能依赖编译器来意识到这个副本是不必要的。

数组的 Foreach 效果相当好

最后一个展开的循环 “For4_Unroll1” 看起来像这样：

for (j = 0; j != jmax; j += 4)
{
  unused += b.intArray[j];
  unused += b.intArray[j + 1];
  unused += b.intArray[j + 2];
  unused += b.intArray[j + 3];
}

它的运行时间为 8.9 毫秒，比使用后缀递增的循环（7.5 毫秒）慢约 20%，额外时间对应内循环每次迭代一个额外的周期。有趣的是将此结果与循环 For4_Foreach 进行比较，其中内循环已替换为 foreach 循环：

foreach (int x in b.intArray)
{
  unused += x;
}

此循环的运行时间也为 8.9 毫秒，就像 For4_Unroll1 一样，并且比任何 for、while 或 do-while 变体快 25%，这些变体尚未展开。

循环就是循环，但属性有成本

变量的声明位置是否重要？索引的递增位置是否重要？在循环条件中引用数组的长度是否重要？为了回答这些问题，我尝试了 for-循环的几种变体：

For1_For2

for (int i = 0; i != b.spec.CountIterations; ++i)
{
  for (int j = 0; j != b.intArray.Length; ++j)
  {
    unused += b.intArray[j];
  }
}

For3_For3

for (int i = 0; i != imax; ++i)
{
  for (int j = 0; j != jmax; ++j)
  {
    unused += b.intArray[j];
  }
}

For4_For4

for (i = 0; i != imax; ++i)
{
  for (j = 0; j != jmax; ++j)
  {
    unused += b.intArray[j];
  }
}

For4_For5

for (i = 0; i != imax; ++i)
{
  for (j = 0; j != jmax; )
  {
    unused += b.intArray[j]; ++j;
  }
}

For4_While

for (i = 0; i != imax; ++i)
{
  j = 0;
  while (j != jmax)
  {
    unused += b.intArray[j];
    ++j;
  }
}

For4_DoWhile

for (i = 0; i != imax; ++i)
{
  j = 0;
  do
  {
    unused += b.intArray[j];
    ++j;
  } while (j != jmax);
}

正如您从结果中可以看到的，它们都执行完全相同的操作（11.8 毫秒或每次迭代 2 个周期），while 和 do-while 的变体也是如此。唯一表现不佳的是 For1_For1，耗时 17.7 毫秒或每次迭代 3 个周期：

for (int i = 0; i != b.spec.CountIterations; ++i)
{
  for (int j = 0; j != b.spec.CountItems; ++j)
  {
    unused += b.intArray[j];
  }
}

public int CountItems { get { return countItems; } }
private int countItems;

我认为这意味着在循环条件中读取属性会使每次迭代增加一个额外的周期。但请注意，在循环条件中读取属性或创建局部副本的语义并不相同。在多线程程序中，属性在两次调用之间可能会发生变化，但局部副本不会。将其与 For1_For2 进行比较，其循环条件依赖于数组的 Length 属性，而 For3_For3 则在循环前读取长度。这两个循环执行相同的操作，这符合预期，因为数组长度无法改变（数组无法调整大小）。

List<int> 的性能

我对 foreach 在数组上的性能感到惊喜，因此我寄希望于 List<int> 也能表现良好，但正如您所见，它并没有：对于展开 16 次的循环（通过列表的索引器读取），每次读取需要 4 个周期，而使用 foreach 则需要 10 个周期！

通过 IList<int> 访问

测试 C# 循环的下一步是想出一种模拟不同访问模式的方法。我的方法是填充一个整数列表，其中包含下一个要读取的位置的索引，然后我只需用我想要测试的访问模式填充列表，并为我提出的所有模式使用相同的代码。之前的实验表明，循环展开带来了显著的性能提升，因此我将采用单循环展开 16 次。代码如下：

int[] list = b.intArray;
for (; i != max; ++i)
{
  j = list[j];
  // repeat 16 times
}

此时，很明显我应该使用 int[] 作为数据结构，但我仍然对 C# 的通用性能感兴趣，所以我决定进行另一项实验，在其中我将使用 int[]、List<int>，看看直接访问它们或通过通用的 Ilist<int> 接口会发生什么。结果如下表所示：

方法	时间（毫秒）	传输速率（GB/s）	% 最大	每个读取的周期数	每次迭代的读取次数	每次迭代的周期数
List<int>	23,80	2,82	25,2%	3,97	16	63,5
int[]	17,56	3,82	34,1%	2,93	16	46,9
List<Int> 上的 Ilist<int>	92,33	0,73	6,5%	15,41	16	246,5
int[] 上的 Ilist<int>	86,90	0,77	6,9%	14,50	16	232,0

直接访问 List<int> 时，我仍然得到每次读取 4 个周期，但对 int 数组的工作量从每次读取 1 个周期增加到 3 个周期。这没关系，因为我已经完成了顺序读取（这些主要是为了 L1 缓存和预读，一旦出现缓存未命中，L1 访问时间无论如何都是 3 个或更多周期）。

另一点是，顺序累加整数列表不是典型的任务。用于测试访问模式的循环也不是，但其增加的复杂性更接近实际程序所做的事情，而且有趣的是，在这种情况下，执行时间增加了 33%，而不是顺序累加示例中的 300%。这使得通用列表的便利性与较慢的执行之间的权衡更加可接受。

通过 IList<int> 接口访问比直接使用 List<int> 慢 4 倍，比 int[] 慢 5 倍。我猜原因在于接口阻止了编译器执行依赖于具体实现的优化。例如，编译器无法知道整数数组的长度是恒定的，或者内存布局是顺序的，这迫使 C# 编译器和 JIT 编译器发出不断重新评估循环条件和内存访问所有方面的代码。

Using the Code

附加的存档包含一个 VS 2008 项目，用于获取上述结果的循环和控制结构。要运行测试，您需要下载工具 Quality Gate One Studio。存档包含该工具的项目，以及几个用于文章中提到的实验的测试集。只需运行测试集并生成报告，即可在您的系统上获得结果。

结论

本文涵盖了一个旨在测量实际缓存性能的实验的先驱，目的是确定是否有可能编写执行速度足够快的 C# 代码来揭示缓存效果。对这个问题的总体结论是，只要稍加注意并进行一些循环展开，这是可能的。事实上，对于简单的结构和简单的数据（int 数组），并进行一些循环展开，C# 的性能非常好，能够以平均每时钟周期一个整数的速度从内存中累加整数。

有些事情比其他事情表现更好，并且发现了以下注意事项：

• 后缀递增（例如 i++）代价高昂，平均增加 1.25 个周期，吞吐量降低 65%。
• 读取属性，例如在循环条件中，可能会损害性能，因为在多线程环境中无法进行某些优化。真正的常量属性（如数组长度）可以进行优化，但如果不确定，最安全的方法是在进入循环之前读取属性值。
• 在这种特殊情况下，通用列表比数组慢得多（慢 4 倍），但证据表明，在更典型的情况下，性能成本要小得多。本文展示了一个示例，其中执行时间仅增加了 33%。
• 使用接口而不是具体类型会带来额外的性能损失。在这种情况下，观察到 4 到 5 倍的损失。一个合理的猜测是，接口阻止了编译器执行在使用具体类型时可用的优化。

从积极的方面来看，证据表明：

• 循环结构（for、while 或 do-while）的选择不影响性能。
• 标准的 foreach 结构可能比简单的 for 循环（每个步骤 2 个周期）更快（每个步骤 1.5 个周期），除非循环已展开（每个步骤 1.0 个周期）。因此，对于日常代码，性能不是使用更复杂的 for、while 或 do-while 结构的理由。

并非所有代码都对性能至关重要，但当事情必须快速执行时，您可能必须为了性能而牺牲良好的编程实践。

• 优先使用具体类型而不是接口
• 优先使用简单的数组而不是 List<>
• 将常量手动提升到循环之外，如果这些常量涉及属性或变量/成员，除非您绝对确定编译器会将它们识别为常量 - 即使在多线程环境中也是如此。
• 手动展开循环

总的来说，不要使用后缀运算符：它们既容易出错，性能又差。

关于编译器/平台版本，我尝试为 .NET 2.0（VS 2008）和 .NET 4.0（VS 2010）进行编译，但未发现两者之间有任何显著差异。

最后，本文是关于 C# 中的快速迭代，但背景是我试图测量缓存效果的尝试。我认为本文本身已经够长了，但我在此过程中做了一些观察：首先，在顺序读取时使用 For4_Unroll4，每周期一步的比率保持不变，与缓冲区大小无关，这基本上意味着流水线和预取在尽可能快地将数据从主内存获取到 CPU 方面做得很好。当将访问模式更改为使用随机访问或大于 4 字节的步长时，缓存效果变得可见，因为硬件无法足够快地预测和预取。

如果您想在自己的系统上进行尝试，附加的代码已为上述实验做好准备，但如果您只想了解您系统的确切事实，您可以从 SiSoft Sandra 等基准测试工具中获取。