缺少求和数组时的预期缓存效果

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 个字节，而 longs 是 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 版本的两倍，与两个版本的预期缓存未命中数相对应。

所以我可以由此得出结论，在 "full" 版本中显然有足够的算法（或至少 "stuff that isn't the memory access"，包括循环开销）恰好隐藏了大部分缓存未命中惩罚，结合实际在 long 版本中做更少的工作。

另外我认为我们应该牢记，因为这是一个完全线性的访问模式，所以应该期望硬件预取做得很好。自动预取的吞吐量可能足够也可能不够，但情况不应该那么糟糕——做一些计算允许预取到 "catch up".

并不是不合理的

只使用每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

你测的时间主要是"just the CPU time"。如果你像 this fork of Harolds answer 那样只对数字求和而忽略整个内存访问，你会发现在一个循环中简单地将所有数字相加所花费的时间几乎相同，没有从 array/memory 阅读它们：

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

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

缺少求和数组时的预期缓存效果

expected cache-effect when summing arrays is missing

c#

algorithm

performance

caching

cpu-cache