为什么 C# 中的一维数组比交错数组快

本文关键字:数组 一维数组 为什么 | 更新日期: 2023-09-27 18:27:21

我很好奇一维数组是否比交错数组快,我测量了以下代码块的性能:

测试 1:交错数组

double[][][][] jagged = ArrayExtensions.Get4DMatrix<double>(100, 100, 50, 50, 0);
for (int iter = 0; iter < 5; iter++)
{
    sw.Restart();
    for (i = 0; i < 100; i++)
    {
        for (j = 0; j < 100; j++)
        {
            for (k = 0; k < 50; k++)
            {
                for (l = 0; l < 50; l++)
                {
                    test = jagged[i][j][k][l];
                    jagged[i][j][k][l] = test;
                }
            }
        }
    }
    Console.WriteLine("Jagged Arrays, Test {0}: {1} ms", iter, sw.ElapsedMilliseconds);
}

测试 2:一维数组

double[] single = ArrayExtensions.Get1DArray<double>(25000000);
for (int iter = 0; iter < 5; iter++)
{
    sw.Restart();
    for (i = 0; i < 100; i++)
    {
        for (j = 0; j < 100; j++)
        {
            for (k = 0; k < 50; k++)
            {
                for (l = 0; l < 50; l++)
                {
                    test = single[i * 100 + j * 100 + k * 50 + l];
                    single[i * 100 + j * 100 + k * 50 + l] = test;
                }
            }
        }
    }
    Console.WriteLine("Single Arrays, Test {0}: {1} ms", iter, sw.ElapsedMilliseconds);
}

运行测试将产生:

Jagged Arrays, Test 0: 1447 m
Jagged Arrays, Test 1: 1429 m
Jagged Arrays, Test 2: 1431 m
Jagged Arrays, Test 3: 1430 m
Jagged Arrays, Test 4: 1429 m
Single Arrays, Test 0: 386 ms
Single Arrays, Test 1: 387 ms
Single Arrays, Test 2: 386 ms
Single Arrays, Test 3: 387 ms
Single Arrays, Test 4: 387 ms

此外,我只在分配给数组的情况下运行测试,然后只从数组中读取,结果具有相同的比率。

我原本以为一维数组比交错数组快,但是当我看到最后一个块的执行时间仅为第一个块的 27% 时,我感到非常惊讶。

有人可以解释为什么会发生这种巨大的差异吗?使用一维数组是否有任何缺点(除了代码可读性之外,它显然变得更加困难,并且可能增加了出错的风险(?

代码是在未优化的版本中执行的。在优化版本中,两个测试在每次迭代中都在 100 毫秒内执行,但我认为这必须与循环内执行的代码做更多的事情。尽管如此,一维数组比交错数组快 50%。

为什么 C# 中的一维数组比交错数组快

   test = single[i * 100 + j * 100 + k * 50 + l];

一位聪明的程序员曾经说过:"永远不要相信你没有伪造自己的基准"。 可能是无意的,这是代码中一个非常讨厌的错误,它会让你比较苹果和橙子。 乘数是完全错误的。 i指数必须乘以 100*50*50,j指数必须乘以 50*50。

副作用是,您更有可能有效地使用 CPU 缓存,因为您寻址的内存要少得多。 产生巨大的差异,RAM非常慢。

影响性能的一个主要因素是数据缓存未命中的数量。 内存分为称为缓存行的块,根据计算机的不同,这些块可能在 16-256 字节左右之间。 访问缓存行中的任何数据字节的成本与访问其中的所有内容的成本大致相同。 最近访问的高速缓存行保存在 CPU 内核内的小型高速缓存中,可以非常快速地再次访问。 最近未访问到足以位于第一级缓存中的行将在第二级缓存中查找,该缓存更大,但访问速度不快。 在第三级缓存中找不到的行可能会被查找(理论上,第四级、第五级、第六级等,尽管我认为没有任何机器能走得那么远(。 指令需要的数据在任何缓存中都找不到,执行时间可能比使用 1 级缓存可以满足的数据长几十倍。

您的程序可能不是线性与交错数组相对性能的最佳指标,因为您使用的是完全顺序访问。 这意味着大多数访问将由最快的(1 级(缓存处理。 正如 pspet 所指出的,取消引用四个嵌套对象比计算单个 offeset 并使用它需要更多的工作。 如果所有内容都来自 1 级缓存,那么实际数据访问便宜的事实意味着这种额外的努力将占主导地位。

我建议您尝试改变循环的顺序并监控性能。 在"发布"模式下构建并在没有附加调试器的情况下运行,以获得准确的计时结果。 我猜想交换两个内部循环会同样减慢两个版本的代码(第一级缓存可能无法满足大多数数据请求,但对内部引用的请求会满足(,使它们的相对时间更近。 交换所有循环会进一步损害线性数组版本的性能,但可能会导致嵌套交错数组的性能很糟糕(您的外部数组可能会保留在第一级缓存中,但嵌套引用可能不会,结果许多元素访问会导致两到三个完整缓存未命中(。

对于占用超过 85,000 字节的数组,.NET 中会降低性能,尤其是在它们生存期较短的情况下,因此在许多情况下,两级交错数组可能是最佳的。 例如,如果每个数据项为 64 字节,则 64 位系统上的两个嵌套级别将允许一个 10,000 个数组,每个数组包含 1,024 个项目,而没有任何项目增长超过 85K。 如果您需要超过 10,000,000 个项目,访问模式将决定使用更大的数组还是第三级嵌套更好,但有各种各样的数组大小,上述方法是最好的。

也许是因为"交错数组"是指针数组(指向数组(...在您的示例中,您有 4 个间接级别:

jagged[i][j][k][l]
  • 从"锯齿状"获取偏移量 i
  • 获取与上一个结果的偏移量 J
  • 获取与上一个结果的偏移量 k
  • 获取与上一个结果的偏移量 l