为什么在C#中有些迭代器比其他迭代器更快?

6

一些迭代器更快。我知道这是因为我从Channel 9的Bob Tabor那里听说过永远不要复制和粘贴。

我习惯于这样设置数组值:

testArray[0] = 0;
testArray[1] = 1;

这只是一个简单的示例,但为了不复制粘贴或重新输入,我想我应该使用循环。但我有这种感觉,循环比仅列出命令要慢,而且看起来我是对的:列出事物要快得多。在我的大多数试验中,速度从最快到最慢依次为列表、do循环、for循环和while循环。
为什么列出事物比使用迭代器快?为什么迭代器的速度不同?
如果我没有以最有效的方式使用这些迭代器,请帮助我。
以下是我的结果(对于2个int数组),我的代码如下(对于4个int数组)。我在Windows 7 64位上尝试过几次。
无论是我不擅长迭代,还是使用迭代器并不像它所说的那样好。请告诉我哪一个是。非常感谢。
int trials = 0;

TimeSpan listTimer = new TimeSpan(0, 0, 0, 0);
TimeSpan forTimer = new TimeSpan(0, 0, 0, 0);
TimeSpan doTimer = new TimeSpan(0, 0, 0, 0);
TimeSpan whileTimer = new TimeSpan(0, 0, 0, 0);
Stopwatch stopWatch = new Stopwatch();
long numberOfIterations = 100000000;

int numElements = 4;
int[] testArray = new int[numElements];
testArray[0] = 0;
testArray[1] = 1;
testArray[2] = 2;
testArray[3] = 3;

// List them
stopWatch.Start();
for (int x = 0; x < numberOfIterations; x++)
{
    testArray[0] = 0;
    testArray[1] = 1;
    testArray[2] = 2;
    testArray[3] = 3;
}
stopWatch.Stop();
listTimer += stopWatch.Elapsed;
Console.WriteLine(stopWatch.Elapsed);
stopWatch.Reset();

// for them
stopWatch.Start();
int q;
for (int x = 0; x < numberOfIterations; x++)
{
    for (q = 0; q < numElements; q++)
        testArray[q] = q;
}
stopWatch.Stop();
forTimer += stopWatch.Elapsed;
Console.WriteLine(stopWatch.Elapsed);
stopWatch.Reset();

// do them
stopWatch.Start();
int r;
for (int x = 0; x < numberOfIterations; x++)
{
    r = 0;
    do
    {
        testArray[r] = r;
        r++;
    } while (r < numElements);
}
stopWatch.Stop();
doTimer += stopWatch.Elapsed;
Console.WriteLine(stopWatch.Elapsed);
stopWatch.Reset();

// while
stopWatch.Start();
int s;
for (int x = 0; x < numberOfIterations; x++)
{
    s = 0;
    while (s < numElements)
    {
        testArray[s] = s;
        s++;
    }
}
stopWatch.Stop();
whileTimer += stopWatch.Elapsed;
Console.WriteLine(stopWatch.Elapsed);
stopWatch.Reset();
Console.WriteLine("listTimer");
Console.WriteLine(listTimer);
Console.WriteLine("forTimer");
Console.WriteLine(forTimer);
Console.WriteLine("doTimer");
Console.WriteLine(doTimer);
Console.WriteLine("whileTimer");
Console.WriteLine(whileTimer);

Console.WriteLine("Enter any key to try again the program");
Console.ReadLine();
trials++;

当我尝试了一个四个元素的数组后,结果似乎更加明显了。
我认为如果像其他实验一样通过变量分配值给listThem组将是公平的。这确实使listThem组变慢了一点,但它仍然是最快的。在几次尝试后,以下是结果: enter image description here 这是我如何实现列表的方式:
int w = 0;
for (int x = 0; x < numberOfIterations; x++)
{
    testArray[w] = w;
    w++;
    testArray[w] = w;
    w++;
    testArray[w] = w;
    w++;
    testArray[w] = w;
    w = 0;
}

我知道这些结果可能是具体实现相关的,但你会认为微软应该警告我们每种循环的优劣之处,尤其是在速度方面。你怎么看?谢谢。

更新: 根据评论,我发布了代码,发现列表仍然比循环更快,但循环的性能更接近。循环的速度从快到慢依次为: for、while、do...while。这有点不同,所以我的猜测是do和while的速度基本相同,而for循环比do和while循环快约0.5%,至少在我的机器上是如此。以下是几次试验的结果: enter image description here


2
你正在展开你的List循环,而不是其他的循环。这是一种非常基本的优化技术,在各个地方都被广泛使用。当然,并不是微软在隐藏什么! - Cory Nelson
1
你能否尝试将numElements的使用更改为硬编码数字(或将其更改为const)?编译器可能会决定展开内部循环。 - sinelaw
7
只是为了明确,你说的是在 一亿次 的迭代中速度差异为 1.709秒。这意味着每个元素的差异为 0.00001709121毫秒。换句话说,“谁在乎”。一个方法与另一个方法在实际上没有任何区别。 - Sam Axe
4
@Dan-o,这只是一个玩具程序 - 但是像这样的紧密循环可能深藏在某些真正的算法代码中,该代码迭代一些巨大的数据结构。在这种情况下,秒数会快速累加。 - sinelaw
2
@sinelaw:当然可以...但你只是在谈论变量赋值。并没有实际处理变量。所以我们必须跳到一个用C#编写的真实应用程序,对数组进行了超过1亿次赋值..现在你已经进入了非常遥远的领域,你有比这更大的问题。在这种情况下,.NET框架确实是错误的工具。 - Sam Axe
显示剩余17条评论
2个回答

8
有些迭代器更快一些。
当然,有些迭代器执行不同的操作。执行不同操作的代码将以不同的速度运行。
我过去习惯这样设置数组值:
首先,这真的是节省时间的最佳时机吗?从您的测量结果来看(如果它是一个调试版本,则没有意义),似乎您的额外代码可以节省约10纳秒的时间。如果全世界的人都使用您的应用程序一次,那么您为所有用户节省的总时间仍然小于额外输入的时间。他们永远不会想“好吧,有十个纳秒我永远拿不回来”。
但你会认为微软会警告我们每个循环的优缺点,特别是在涉及速度方面的时候?
不,我真的不会。
特别是当你进一步概括时。首先,对于较大的循环,等效展开的代码可能相当慢,因为循环可能适合指令行缓存,而展开的代码则不适合。
另外,迭代和枚举(平均而言比迭代要慢,但差距不大)更加灵活。它们将导致更小、更符合惯例的代码。它们适用于许多情况,其中您所拥有的展开方式要么不适用,要么不容易适用(因此,您由于必须执行某些复杂操作而失去任何预期的节省)。它们的错误范围更小,只是因为它们的范围更小。
首先,MS或其他人不能建议始终填充代码以节省几个纳秒的时间,因为它并不总是最快的方法,而且其次,他们不会这样做,因为其他代码的优越性。
现在,确实有一些情况下,节省几个纳秒真的很重要,这是当我们做某件事情数十亿次时。如果芯片制造商将基本指令所需的时间缩短几个纳秒,它将增加真正的胜利。
就我们在C#中可能做的代码而言,我们可能会进行展开优化,尽管这很少是我们关心运行时间的地方。
假设我需要做x次某件事。
首先,我做了显而易见的事情:
for(int i = 0; i != x; ++i)
  DoSomething();

假设我的应用程序整体速度不够快,我首先需要考虑的是"足够快"的具体意义,因为如果不是出于娱乐目的(嘿,为了追求速度而做出荒谬的努力可能会很有趣),这就是我想知道的第一件事情。我会得到一个答案,或者更可能得到几个答案(最低可接受、最低目标、理想状态和营销宣传时可以炫耀速度有多快等级可能不同)。
然后我找出实际代码中花费时间的部分。如果另一个片段被外部循环调用1000次,每当用户点击按钮会导致4秒的延迟,而这段代码仅占应用程序寿命的10ns,那么优化它是没有意义的。
然后我重新考虑我的整体方法-是否执行"这样做X次"(本质上是O(x)时间复杂度)是达到我的实际目标的唯一方法,还是我能做一些完全不同的事情,例如O(ln x) (即,它所需的时间与 X 的对数成比例)。我能否缓存一些结果,以便在更长的初始运行时间内,我可以节省数千次的几毫秒?
然后我会尝试提高DoSomething()的速度。99.9%的时间,我在那里做得比更改循环要好,因为它可能花费的时间比循环本身花费的几纳秒还要长。
然后我可能会在DoSomething()中做一些非常可怕、不符合惯例和令人困惑的事情,但我知道这是值得的地方(我会注释说明这种更混乱的代码是如何工作的,以及为什么要使用这种方式)。然后我会测量这些变化,并可能在几年后再次测量它们,因为当前框架和当前CPU上最快的方法可能不是在.NET 6.5上最快的方法,现在我们已经将应用程序移动到一个具有最新Intel芯片的酷炫新服务器上。
很可能我会将DoSomething()手动插入循环中,因为调用函数的成本几乎肯定比循环的方法更大(但并不完全确定,只要JIT可以内联什么就有可能出现意外的情况以及会产生什么影响)。
也许,也许我会将实际的循环替换为类似于以下内容的东西:
if(x > 0)
  switch(x & 7)
  {
    case 0:
      DoSomething();
      goto case 7;
    case 7:
      DoSomething();
      goto case 6;
    case 6:
      DoSomething();
      goto case 5;
    case 5:
      DoSomething();
      goto case 4;
    case 4:
      DoSomething();
      goto case 3;
    case 3:
      DoSomething();
      goto case 2;
    case 2:
      DoSomething();
      goto case 1;
    case 1:
      DoSomething();
      if((x -= 8) > 0)
        goto case 0;
      break;
  }

由于这是一种将循环的性能优势与手动展开循环带来的短循环性能优势相结合的方式,因此不会占用大量指令内存,它基本上使用了您的方法来处理8个项目组,并循环遍历8个项目的块。
为什么是8? 因为这是一个合理的起点; 如果这是我代码中如此重要的热点,我实际上会测量不同的大小。 我在真正的(而不仅仅是为了好玩).NET代码中做到这一点的唯一时间是我最终做了16个块。
那仅仅是因为每次迭代调用的指令非常短(12个IL指令,对应于C#代码* x ++ = * y ++),而且它的设计目的是让其他代码快速执行某些操作,整个代码路径我在大多数情况下都可以避免碰撞,更多的工作是在计算何时最好使用或避免它,而不是让那一位尽可能快地打出来。
其余的时间,要么展开不节省太多(如果有任何东西),要么不节省在重要的地方,要么在甚至考虑展开之前,有其他更加紧迫的优化事项要处理。
我肯定不会从这样的代码开始; 那将是过早优化的明确定义。
总的来说,迭代很快。 其他编码人员都知道它。 跳动(jitter)也知道它(在某些情况下可以应用一些优化)。 它易于理解。 它很简短。 它很灵活。 通常使用foreach也很快,尽管不如迭代快,但更加灵活(可以使用各种方式使用IEnumerable实现高效率)。
重复的代码更加脆弱,更有可能隐藏一个愚蠢的错误(我们都会写出让我们想“那太傻了,几乎不能算作一个错误”的漏洞,只要你能找到它们,就很容易修复)。 它更难维护,并且更有可能随着项目的推进而变得更加难以维护。 它更难以看到整体情况,并且在整体情况下可以进行最大的性能改进。
总之,频道9的家伙没有警告您某些情况下程序可能会变慢10ns的原因是他会被笑话。

2
谢谢回答。确实值得深思。 - Eric Martin
+1,如果没有其他的话,至少教会了我goto case是有效的C#。没想到这么多年后还能学到新的语法! - JulianR
在 C# 中禁止 fall-through 在一些情况下会导致问题,这是我们绕过它的方法。当然,有些人对 goto 会变得迷信,但也许这并不完全是坏事,因为它仍然在95%的时间内应该避免使用(我知道我在说95%而不是99.999%时有争议)。很好的一点是,他们使 case 行为像标签一样,如果你需要在 C 或 C++ 的 switch 块中使用 goto,你必须添加另一个标签,而这种方式更加自我说明,你要跳到哪里。 - Jon Hanna
@JulianR,你会很高兴知道编译器不会添加任何跳转,只是允许一种顺序执行(假设它不是重写switch为一组if...else if...的情况,尽管使用这样的示例减少了这种可能性)。 - Jon Hanna

2
我使用ILDASM查看了for循环和直接赋值的IL代码。
不使用循环的直接赋值IL代码如下,每个赋值操作都重复了3次:
IL_0007:  ldloc.0
IL_0008:  ldc.i4.0
IL_0009:  ldc.i4.0
IL_000a:  stelem.i4

for循环的IL代码如下:

IL_0017:  ldc.i4.0
IL_0018:  stloc.1
IL_0019:  br.s       IL_0023
IL_001b:  ldloc.0
IL_001c:  ldloc.1
IL_001d:  ldloc.1
IL_001e:  stelem.i4
IL_001f:  ldloc.1
IL_0020:  ldc.i4.1
IL_0021:  add
IL_0022:  stloc.1
IL_0023:  ldloc.1
IL_0024:  ldc.i4.4
IL_0025:  blt.s      IL_001b
IL_0027:  ret

数组的赋值在IL_001bIL_001e行完成。除此之外,还有很多其他操作。
循环中第一步并不是赋值,而是检查循环变量是否在范围内。所以它会跳转到IL_0023,然后返回到IL_001b开始赋值。
在赋值之后,需要增加循环计数器(IL_001fIL_0022)。然后再次检查循环变量并分支。
因此,您可以看到循环比简单的赋值要复杂得多。正如其他人所说,这就是循环展开的好处——尽可能减少或完全避免运行此循环的开销。
Jon关于JIT进行优化的观点也很重要。在微基准测试中,诸如CPU缓存和分支(这是for循环在做什么)等内容可能对性能产生严重影响,因为您正在测量非常小的数字。
最终,如果循环的结构比循环中的操作更昂贵来自循环的微小开销实际上具有重大意义,则可以考虑循环展开。但更有可能的是,您有一个可以改进的设计。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接