在总结数组时缺少预期的缓存效果

Question

我希望以下程序在性能方面完全受内存限制（阵列比L3缓存大）。

因此，我预计long数组的总和几乎是int数组总和的两倍。

但它们几乎同时采取：

 int sum took 81 ms, result = 4999999950000000
long sum took 87 ms, result = 4999999950000000

任何人都能解释一下吗？

using System;
using System.Diagnostics;
using System.Linq;

namespace MemoryPerformance
{
    class Program
    {
        static void Main(string[] args)
        {
            const int count = 100_000_000;
            int[] intArray = Enumerable.Range(0, count).ToArray();
            long[] longArray = intArray.Select(x => (long)x).ToArray();
            Measure(() => intSum(intArray), " int sum");
            Measure(() => longSum(longArray), "long sum");
        }

        static long intSum(int[] array)
        {
            long sum = 0;
            for (int i = 0; i < array.Length; i++) sum += array[i];
            return sum;
        }

        static long longSum(long[] array)
        {
            long sum = 0;
            for (int i = 0; i < array.Length; i++) sum += array[i];
            return sum;
        }

        static void Measure(Func<long> calc, string description)
        {
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            long sum = calc();
            stopwatch.Stop();
            Console.WriteLine($"{description} took {stopwatch.ElapsedMilliseconds} ms, result = {sum}");
        }
    }
}

Answer 1

如果我多次运行，我会得到相同的结果，但更糟糕的是:(打印结果以防万一）

 int sum took 84 ms (4999999950000000)
long sum took 77 ms (4999999950000000)
 int sum took 84 ms (4999999950000000)
long sum took 76 ms (4999999950000000)
 int sum took 84 ms (4999999950000000)
long sum took 77 ms (4999999950000000)
 int sum took 83 ms (4999999950000000)
long sum took 76 ms (4999999950000000)

所以多头更快？其中一个就是int版本没有这样做，是符号扩展。可能就是这样。其实我不知道它还能是什么。

但这就是添加数组的所有元素时会发生的情况。如果我只采用每个第8个元素（第8个，因为缓存行是64个字节，长整数是8，所以8个适合缓存行），会发生这种情况：

 int sum took 25 ms (624999950000000)
long sum took 49 ms (624999950000000)
 int sum took 23 ms (624999950000000)
long sum took 49 ms (624999950000000)
 int sum took 23 ms (624999950000000)
long sum took 48 ms (624999950000000)
 int sum took 23 ms (624999950000000)
long sum took 48 ms (624999950000000)

这是非常不同的，实际上int版本的速度是long版本的两倍，与两个版本预期的缓存未命中数相对应。

因此，我可以从中得出结论，在“完整”版本中，显然足够的算术（或者至少“不是内存访问的东西”，包括循环开销）碰巧隐藏了大部分缓存未命中惩罚，并且实际上做得更少在long版本工作。

另外我认为我们应该记住，因为这是一个完全线性的访问模式，所以应该期望硬件预取做得很好。自动预取的吞吐量可能或者可能不足够，但它不应该是一个不好的情况 - 进行一些计算允许预取“赶上”是不合理的。

---

仅使用每第8个元素的相关代码：

    static long intSum(int[] array)
    {
        long sum = 0;
        for (int i = 0; i < array.Length; i += 8) sum += array[i];
        return sum;
    }

    static long longSum(long[] array)
    {
        long sum = 0;
        for (int i = 0; i < array.Length; i += 8) sum += array[i];
        return sum;
    }

时间在ideone

Answer 2

您测量的时间主要是“仅CPU时间”。如果你只是总结数字并省略整个内存访问，就像在this fork of Harolds answer中那样，你会发现在循环中简单地加上所有数字所需的时间几乎相同，而无需从数组/内存中读取它们：

static long noSum(long[] array)
{
        long sum = 0;
        for (int i = 0; i < array.Length; i ++) sum += i;
        return sum;
}

这意味着即使CPU必须从内存中获取数据并且不能将其全部保存在缓存中，它也可以非常有效地执行此操作，因为您没有使用随机数组访问：在循环的情况下，它有足够的时间在仍然执行计算时预取下一个缓存行。这导致几乎没有等待时间（投机执行任何人？！;-)）。因此，在您的情况下并不重要。在那些你需要更快地访问大量内存的情况下，就像Harold“稀疏”测试用例一样，显然。