为什么在C#中有些迭代器比其他迭代器更快?
为什么在C#中有些迭代器比其他迭代器更快?
有些迭代器更快。我发现这一点是因为我从Bob Tabor在Channel 9上听说永远不要复制粘贴。\n我过去习惯于这样设置数组值:\n
testArray[0] = 0; testArray[1] = 1;
\n这只是一个简化的例子,但为了不复制粘贴或者不再次输入,我应该使用循环。但我总觉得循环会比简单列出命令慢,而且看起来我是对的:列出命令要快得多。在我大部分的试验中,速度(从最快到最慢)是列表、do循环、for循环,然后是while循环。\n为什么列出命令比使用迭代器快,为什么迭代器的速度不同?\n如果我没有以最高效的方式使用这些迭代器,请帮我解答。\n这是我的结果(对于一个包含2个整数的数组),下面是我的代码(对于一个包含4个整数的数组)。我在我的Windows 7 64位系统上试验了几次。\n\n要么我不擅长迭代,要么使用迭代器并不像它被宣传的那么好。请告诉我是哪一种情况。非常感谢。\n
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; // 列出命令 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循环 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循环 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++;
\n当我尝试一个包含4个元素的数组时,结果似乎更加明显。\n我觉得如果我像其他试验一样,将listThem组的值赋给一个变量,结果会更公平。这确实使得listThem组稍微慢了一些,但它仍然是最快的。以下是几次尝试后的结果:\n\n这是我实现列表的方式:\n
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; }
\n我知道这些结果可能是与实现相关的,但你会觉得微软会警告我们每种循环的优缺点,特别是在速度方面。你怎么看?谢谢。\n更新: 根据评论的建议,我发布了代码,列表仍然比循环更快,但循环的表现更接近。循环的速度从快到慢分别是:for、while、然后do。这有点不同,所以我猜do和while的速度基本相同,而for循环比do和while循环快大约0.5%,至少在我的机器上是这样。以下是几次试验的结果:
C#中为什么有些迭代器比其他迭代器快?
有人通过使用ILDASM查看了for循环与直接赋值的IL代码,发现它们之间存在差异。直接赋值的IL代码很简单,而for循环的IL代码则较为复杂。在for循环中,首先需要判断循环变量是否在范围内,然后进行赋值操作,并递增循环计数器。这就导致了for循环比直接赋值要花费更多的时间。
此外,JIT编译器对代码进行了优化,这也会对性能产生影响。在微基准测试中,像CPU缓存和分支操作这样的因素可能会对性能产生明显的影响,因为测试的数据量非常小。
如果循环结构本身比循环内部的操作更加耗时,且循环带来的微小性能开销实际上是有意义的,那么可能需要考虑循环展开。但更有可能的情况是需要优化设计。
解决这个问题的方法就是优化循环结构,减少循环带来的开销,或者完全避免使用循环。
为什么C#中的某些迭代器比其他迭代器快?
当然,一些迭代器做不同的事情。不同的代码做不同的事情会以不同的速度运行。
首先,这真的是你需要节省的时间吗?从你的测量结果来看(如果是调试构建,则无意义),你的额外代码可以节省大约10纳秒的时间。如果世界上的每个人都使用了你的应用程序一次,你为所有用户节省的总时间仍然少于刚刚花费在键盘上的额外时间。在任何时候,他们都不会想“好吧,这是我永远无法找回的十纳秒”。
不,我真的不会这样想。特别是当你进一步概括时。首先,对于更大的循环,等效的展开代码可能会更慢,因为循环可能适应指令行缓存,而展开的代码则不会。
其次,迭代和枚举(平均而言通常比迭代更慢,但差别不大)更加灵活。它们将导致更小、更符合习惯的代码。它们适用于很多情况,而你所做的展开要么不适用,要么不容易适用(所以你失去了你期望的任何节省,因为你必须做一些费解的事情)。它们的错误范围更小,仅仅因为它们有一个更小的范围。
所以首先,微软或其他人不能建议始终填充你的代码以节省几个纳秒的重复复制的语句,因为它不总是最快的方法,而且第二他们不会这样做,因为其他代码的其他方面更优越。
现在,确实有一些情况下节省几个纳秒真的很重要,比如当我们做某件事情几十亿次时。如果芯片制造商减少了基本指令所需的时间几个纳秒,就会获得真正的优势。
就我们在C#中可能做的代码而言,我们可能会进行一种展开的优化,尽管这很少是我们关心运行时间的地方。
假设我需要做一些事情x次。
首先,我做了显而易见的事情:
for(int i = 0; i != x; ++i) DoSomething();
首先,我考虑一下我需要多快的时间,因为除非这是为了好玩而编码(嘿,为了追求速度而做出荒谬的努力可能是有趣的),这是我想知道的第一件事。我得到了一个答案,或者更可能是几个答案(最低可接受的、最低目标、理想和营销人员可以吹嘘的速度可能是不同的级别)。
然后我找出实际代码中花费时间的部分。如果应用程序的某个部分在应用程序的生命周期中花费了10纳秒的时间,而另一个部分在用户每次点击按钮时被外部循环调用1,000次,并导致4秒的延迟,那么优化花费10纳秒的东西是没有意义的。
然后,我重新考虑整个方法——“做这个x次”(这在时间复杂度上本质上是O(x)),是实现我实际目标的唯一方法,还是我可以完全不同的方式,比如O(ln x)(即,与X成比例的时间消耗与X的对数成比例)。我可以缓存一些结果,以便在更大的初始运行时间上节省几毫秒,多次重复。
然后,我将看看是否可以提高DoSomething()
的速度。99.9%的时间,我会在那里做得更好,而不是改变循环,因为它很可能比循环本身花费的几个纳秒时间更多。
我可能会在DoSomething()
中做一些非常糟糕的非习惯性和令人困惑的事情,我通常认为这是糟糕的代码,因为我知道这是值得的地方(而且我会评论解释这个更令人困惑的代码如何工作,以及为什么要这样做)。我会测量这些变化,可能几年后我会再次测量它们,因为目前框架上的最快方法在.NET 6.5上可能不是最快的方法,现在我们将应用程序移植到了2017年英特尔最新芯片的最新服务器上。
很可能我会将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++
对应)并且它是为了让其他代码快速执行而设计的代码的情况下,我才会这样做,整个代码路径是我在大多数情况下避免进入的,更多的工作是花在确定何时更好地使用或避免它上,而不是使该部分尽可能快。
其他时间,要么展开不会节省太多(如果有的话),要么节省的地方并不重要,要么在考虑之前还有其他更重要的优化要做。
当然,我不会从这样的代码开始;这将是过早优化的定义。
作为一条规则,迭代是快速的。其他程序员知道这一点。JIT编译器知道这一点(在某些情况下可以应用一些优化)。它是可以理解的。它很短。它很灵活。同样,在大多数情况下使用foreach
也很快,虽然不如迭代快,但它更加灵活(有各种各样的方式可以使用IEnumerable
实现高效)。
重复的代码更加脆弱,更有可能隐藏一个愚蠢的错误(我们都会写出让我们想“那太愚蠢了,几乎不够好来算作一个错误”的错误,这些错误很容易修复,只要你能找到它们)。它更难维护,而且随着项目的进行,更有可能变得更难维护。它更难以看到大局,并且在大局中可以进行最大的性能改进。
总之,Channel 9上的那个人没有警告你,某些东西可能会使你的程序变慢,特定情况下可能会慢10纳秒,是因为他会被嘲笑。
感谢您的答案。绝对有很多值得思考的东西。
+1,至少教会了我goto case
是有效的C#。没想到这么多年后还能学到新的语法!
在C#中禁止case穿透会导致问题的少数情况下,这就是我们绕过它的方式。当然,有些人对goto
会产生迷信,但或许这不完全是件坏事,因为95%的时间还是要避免使用它(我知道我在说95%而不是99.999%时有争议)。很高兴他们让case
充当标签,就好像在C或C++中在switch
块内部需要goto
一样,你必须添加另一个标签,而这种方式更具自描述性,告诉你跳转到哪里。
并且你会高兴地知道编译器不会添加任何跳转,只允许穿透(假设它不是将switch
重写为一组if...else if...
的情况,尽管在这个示例中不太可能这样做)。