C# 性能 - 线性数组访问与随机访问

Question

谁能帮我理解为什么使用线性增量索引访问数组比使用随机索引快大约 3-4 倍？

有什么方法可以加快随机索引访问时间吗？

请考虑以下测试代码，线性返回 ~3 秒，随机返回 ~9-10s:

    public static void test()
    {
        var arr = new byte[64 * 1024 * 1024];
        byte b = 0;

        var sw = new Stopwatch();

        double timeSum = 0;

        for (var i = 0; i < arr.Length; i++)
        {

            sw.Restart();
            b = arr[i];
            sw.Stop();
            timeSum += sw.Elapsed.TotalMilliseconds;
        }


        Console.WriteLine("Linear access : " + timeSum + " ms");


        timeSum = 0;

        var rng = new Random();
        var rnum = 0;
        for (var i = 0; i < arr.Length; i++)
        {
            rnum = rng.Next(0, arr.Length - 1);
            sw.Restart();
            b = arr[rnum];
            sw.Stop();
            timeSum += sw.Elapsed.TotalMilliseconds;
        }

        sw.Stop();

        Console.WriteLine("Random access : " + timeSum + " ms");

    }

Answer 1

您在基准测试中看到的差异(4 到 5 倍)不能仅通过高速缓存行和对数组的顺序访问来解释。顺序可预测访问确实会更快，但除非您管理的是巨大的阵列，否则如果性能提升甚至接近这些数字，我会感到惊讶。

编辑 对于基准测试中的数组大小(64x 1024x1024)，差异是惊人的，老实说，远远超出我的预期。所以我的第一印象是完全错误的!

问题是您的基准。你是微观测量；您无法通过 System.Diagnostics.Stopwatch 的任何形式自信地进行个人查找。

试图提出一个公平的基准非常棘手，因为没有简单的方法将随机生成与查找隔离开来。我没有考虑太多，但下面至少尝试将苹果与苹果进行比较:诀窍是预生成随机和顺序数组，然后进行基准双查找:

static void Main(string[] args)
{
    lookUpArray(1, new[] { 0 }, new[] {0}); //warmup JITTER

    var r = new Random();
    const int arraySize = 10000;
    const int repetitions = 10000;

    var lookupArray = new int[arraySize]; //values dont matter
    var sequentialArray = Enumerable.Range(0, arraySize).ToArray();
    var randomArray = sequentialArray.Select(i => r.Next(0, arraySize)).ToArray();

    for (var i = 0; i < 10; i++)
    {
        var sw = Stopwatch.StartNew();
        lookUpArray(repetitions, lookupArray, randomArray);
        sw.Stop();
        Console.WriteLine($"Random: {sw.ElapsedMilliseconds} ms");

        sw.Reset();
        sw.Start();
        lookUpArray(repetitions, lookupArray, sequentialArray);
        sw.Stop();
        Console.WriteLine($"Sequential: {sw.ElapsedMilliseconds} ms");
    }
}

private static void lookUpArray(int repetitions, int[] lookupArray, int[] indexArray)
{
    for (var r = 0; r < repetitions; r++)
    {
        for (var i = 0; i < indexArray.Length; i++)
        {
            var _ = lookupArray[indexArray[i]];
        }
    }
}

无论如何我都不是基准测试专家，所以这在很多方面可能都很糟糕，但我认为这是一个更公平的比较。