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

34 浏览
0 Comments

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

请问有人能帮我理解为什么使用线性递增的索引访问数组大约比使用随机索引快3-4倍？有没有办法使随机索引的访问速度更快？\n请考虑以下测试代码，线性访问大约需要3秒，随机访问需要约9-10秒：\n

    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("线性访问时间：" + timeSum + " 毫秒");
        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("随机访问时间：" + timeSum + " 毫秒");
    }

0

1 答案

0 Comments

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

在性能测试中，你所看到的差异（4到5倍）不能仅仅通过缓存行和顺序访问数组来解释。尽管顺序可预测访问会更快，但除非你管理大型数组，否则我会对性能提升的数字感到惊讶。

编辑：根据你的性能测试中数组的大小（64x 1024x1024），差异令人震惊，远远超出我所期望的。所以我的第一印象完全错误！

问题出在你的性能测试上。你正在进行微小的测量，你不可能用System.Diagnostics.Stopwatch来有信心地测量单个查找。

试图设计一个公平的性能测试实际上是非常棘手的，因为没有简单的方法来将随机生成与查找分离。我没有仔细考虑过，但至少以下方法试图进行了苹果与苹果的比较：关键是预先生成随机和顺序数组，然后对双重查找进行性能测试：

static void Main(string[] args)
{
    lookUpArray(1, new[] { 0 }, new[] { 0 }); //预热JITTER
    var r = new Random();
    const int arraySize = 10000;
    const int repetitions = 10000;
    var lookupArray = new int[arraySize]; //值无关紧要
    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]];
        }
    }
}

我不是性能测试专家，所以这个方法可能在很多方面都很糟糕，但我认为它是一个更公正的比较。

是的，我是第一个没有预料到这种差异的人。你的性能测试仍然给出了错误的结果，但它偏向于我预期的相反方向。

很抱歉删除了我的之前的评论，在你编辑之前我发布了它。我相信你的性能测试更好，因为它真正展示了差异。我发现修复查找数组会使差异变得不那么明显，但我不想在我的应用程序中使用不安全的代码。而且，事实上，这个问题只在最近处理的数据量增加之后才出现。

0