我能做些什么来使这个循环运行得更快

本文关键字：运行 循环 做些什么 | 更新日期: 2023-09-27 18:35:21

我有一个简单的循环：

int[] array = new int[100000000];
int sum = 0;
for (int i = 0; i < array.Length; i++)
    sum += array[i];

我将它的性能与C++版本进行了比较。我认为性能应该接近相同，因为它是非常简单的代码，在这种情况下省略了范围检查。但事实证明，C++版本的速度几乎快了三倍。所以我实现了 C# 不安全版本，但性能更差。Resharper 建议将循环转换为 linq 表达式，如下所示：

sum = array.Sum();

该代码比 C# 中的原始循环慢很多倍

有人可以告诉我是否可以做更多的事情来提高这个循环的性能（无需将其编译为 64 位版本 - 快两倍）。

所有测试都是在 32 位发布版本上进行的，无需调试器即可运行。

编辑：小修正。64 位版本比 ints

我能做些什么来使这个循环运行得更快

class="answers" 快两倍> 
var watch = new Stopwatch();
int[] array = new int[100000000];
for (int i = 0; i < array.Length; i++)
{
    array[i] = 1;
}
watch.Restart();
int sum = 0;
for (int i = 0; i < array.Length; i++)
    sum += array[i];
Console.WriteLine("for loop:" + watch.ElapsedMilliseconds + "ms, result:" + sum);
sum = 0;
watch.Restart();
sum = array.Sum();
Console.WriteLine("linq sum:" + watch.ElapsedMilliseconds + "ms, result:" + sum);
sum = 0;
watch.Restart();
int length = array.Length;
for (int i = 0; i < length; i++)
    sum += array[i];
Console.WriteLine("for loop fixed:" + watch.ElapsedMilliseconds + "ms, result:" + sum);
sum = 0;
watch.Restart();
foreach (int i in array)
{
    sum += i;
}
Console.WriteLine("foreach sum:" + watch.ElapsedMilliseconds + "ms, result:" + sum);
sum = 0;
watch.Restart();
sum = array.AsParallel().Sum();
Console.WriteLine("linq parallel sum:" + watch.ElapsedMilliseconds + "ms, result:" + sum);

Linq Parallel 似乎至少在我的机器上被禁食了。

固定长度并不重要，但可以提高~10%

您实际上可以做的不多，非托管 C 代码总是会更快。

我的电脑上的结果是：

for loop:      241ms, result:100000000
linq sum:      559ms, result:100000000
for loop fixed:237ms, result:100000000
foreach sum:   295ms, result:100000000
linq parallel: 205ms, result:100000000

展开循环 2-8 次。衡量哪一个是最好的。.NET JIT 的优化效果很差，因此您必须完成其一些工作。

您可能还必须添加unsafe因为 JIT 现在无法优化数组边界检查。

您还可以尝试聚合为多个 sum 变量：

int sum1 = 0, sum2 = 0;
for (int i = 0; i < array.Length; i+=2) {
    sum1 += array[i+0];
    sum2 += array[i+1];
}

这可能会增加指令级并行性，因为所有add指令现在都是独立的。

i+0经过优化，可自动i。

我测试了它，它剃掉了大约 30%。

重复时，时间是稳定的。法典：

        Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
        var watch = new Stopwatch();
        int[] array = new int[500000000];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = 1;
        }
        //warmup
        {
            watch.Restart();
            int sum = 0;
            for (int i = 0; i < array.Length; i++)
                sum += array[i];
        }
        for (int i2 = 0; i2 < 5; i2++)
        {
            {
                watch.Restart();
                int sum = 0;
                for (int i = 0; i < array.Length; i++)
                    sum += array[i];
                Console.WriteLine("for loop:" + watch.ElapsedMilliseconds + "ms, result:" + sum);
            }
            {
                watch.Restart();
                fixed (int* ptr = array)
                {
                    int sum = 0;
                    var length = array.Length;
                    for (int i = 0; i < length; i++)
                        sum += ptr[i];
                    Console.WriteLine("for loop:" + watch.ElapsedMilliseconds + "ms, result:" + sum);
                }
            }
            {
                watch.Restart();
                fixed (int* ptr = array)
                {
                    int sum1 = 0;
                    int sum2 = 0;
                    int sum3 = 0;
                    int sum4 = 0;
                    var length = array.Length;
                    for (int i = 0; i < length; i += 4)
                    {
                        sum1 += ptr[i + 0];
                        sum2 += ptr[i + 1];
                        sum3 += ptr[i + 2];
                        sum4 += ptr[i + 3];
                    }
                    Console.WriteLine("for loop:" + watch.ElapsedMilliseconds + "ms, result:" + (sum1 + sum2 + sum3 + sum4));
                }
            }
            Console.WriteLine("===");
        }

进一步尝试，事实证明多个聚合变量什么都不做。不过，展开循环确实取得了重大改进。不安全什么也没做（除了在几乎需要它的展开的情况下）。展开 2 次与 4 次一样好。

在酷睿i7上运行它。

首先，关于像这样的微观基准测试的一些一般性评论：

  • 这里的时序非常短，JIT 时间可能很长。这很重要，因为并行ForEach循环包含一个匿名委托，该委托仅在首次调用时被 JITted，因此 JIT 时间包含在首次运行基准测试的计时中。
  • 代码的上下文也很重要。JITter可以更好地优化小函数。将基准代码隔离在其自己的函数中可能会对性能产生重大影响。

有四种基本技术可以加速代码（如果我们保持纯CLR）：

  1. 并行化它。这是显而易见的。
  2. 展开循环。这通过仅每 2 次或更多次迭代进行比较来减少指令数量。
  3. 使用不安全的代码。在这种情况下，这并没有多大好处，因为主要问题（阵列上的范围检查）被优化了。
  4. 允许更好地优化代码。我们可以通过将实际的基准代码放在单独的方法中来做到这一点。

这是并行代码：

var syncObj = new object();
Parallel.ForEach(Partitioner.Create(0, array.Length),
    () => 0,
    (src, state, partialSum) => {
        int end = src.Item2;
        for (int i = src.Item1; i < end; i++)
            partialSum += array[i];
        return partialSum;
    },
    partialSum => { lock (syncObj) { s += partialSum; } });

Partitioner类位于 System.Collections.Concurrent 命名空间中。

在我的机器（i7 950，8 个逻辑内核）上，我得到的时间是：

For loop: 196.786 ms
For loop (separate method): 72.319 ms
Unrolled for loop: 196.167 ms
Unrolled for loop (separate method): 67.961 ms
Parallel.Foreach (1st time): 48.243 ms
Parallel.Foreach (2nd time): 26.356 ms

32 位和 64 位代码之间没有显著差异。

我在@Ela的答案中添加了以下内容：

            sum = 0;
        watch.Restart();
        var _lock = new object();
        var stepsize = array.Length / 16;
        Parallel.For(0, 16,
            (x, y) =>
            {
                var sumPartial = 0;
                for (var i = x * stepsize; i != (x + 1) * stepsize; ++i)
                    sumPartial += array[i];
                lock (_lock)
                    sum += sumPartial;
            });
        Console.Write("Parallel.For:" +  watch.ElapsedMilliseconds + " ms, result:" + sum);

然后打印结果，以便获得参考值：

for loop:893ms, result:100000000
linq sum:1535ms, result:100000000
for loop fixed:720ms, result:100000000
foreach sum:772ms, result:100000000
Parallel.For:195 ms, result:100000000

如您所见，嘟嘟:)更快对于Stepsize，我尝试了arr.Length / 8，arr.Length / 16，arr.Length / 32（我得到了i7 CPU（4核* 2线程= 8个线程同时）），它们都几乎相同，所以这是你的选择

编辑：我也尝试了stepsize = arr.length / 100，它在@ 250ms的某个地方，所以有点慢。

使用即时操作数将在一定程度上提高性能，

int[] array = new int[100000000];
int sum = 0;
for (int i = 0; i < array.Length; i++)
    sum += array[i];

上面的代码需要访问两个内存位置，即int i和array.length;

而是使用，

int[] array = new int[100000000];
int sum = 0;
int arrayLength=array.length;
for (int i = arrayLength-1; i >0; i--)
    sum += array[i];

经常被忽视的简单且有时很重要的 C# for 循环优化是将循环计数器变量类型从 int 切换到 uint 。这导致具有数百万次迭代的标准i++（增量）循环的平均加速约为 12%。如果您的循环迭代少于此值，则可能不会对性能产生太大影响。

请注意，数组可以按uint进行索引，而无需强制转换为int因此在循环内编制索引时不会失去任何好处。不使用此方法的唯一常见原因是，如果需要负循环计数器值，或者需要强制转换循环计数器变量以int循环内的其他函数调用等。只要你需要选角，这可能不值得。

相关文章：