0

我很好奇一维数组是否比锯齿状数组快，我测量了以下代码块的性能：

测试 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%。

4

3 回答 3

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

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

副作用是您更有可能有效地使用 CPU 缓存，因为您处理的内存要少得多。有很大的不同，RAM 非常慢。

于 2013-08-10T19:49:14.747 回答
0

也许是因为“锯齿状数组”是指针数组（指向数组）...在您的示例中，您有 4 个间接级别：

jagged[i][j][k][l]
  • 从“锯齿状”中获得偏移量
  • 从上一个结果中获取偏移量 j
  • 从上一个结果中获取偏移量 k
  • 从上一个结果中获取偏移量 l
于 2013-08-10T19:12:48.570 回答
0

性能的一个主要因素是数据缓存未命中的数量。内存被分成称为缓存线的块，根据机器的不同，缓存线可能在 16-256 字节左右。访问高速缓存行中的任何数据字节的成本与访问其中的所有内容一样多。最近访问的高速缓存行保存在 CPU 内核中的一个小高速缓存中，并且可以非常快速地再次访问。最近没有访问到足以进入一级缓存的行将在二级缓存中查找，二级缓存更大但访问速度不快。在那里找不到的行可能会在三级缓存中寻找（理论上，第四、第五、第六等，尽管我认为任何机器都不会走那么远）。一条指令需要的数据是'

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

我建议您尝试改变循环的顺序并监控性能。在“发布”模式下构建并在没有附加调试器的情况下运行以获得准确的时序结果。我猜想交换你的两个内部循环会减慢两个版本的代码大致相同（大多数数据请求可能不会被一级缓存满足，但对内部引用的请求会），带来他们的相对时间更接近。交换所有循环会稍微损害线性数组版本的性能，但可能会导致嵌套锯齿状数组的性能很糟糕（您的外部数组可能会停留在一级缓存中，但嵌套引用可能不会，

对于占用超过 85,000 字节的数组，在 .NET 中存在性能损失，特别是如果它们是短暂的，因此在许多情况下，两级锯齿状数组可能是最佳的。例如，如果数据项是 64 字节，那么在 64 位系统上的两级嵌套将允许一个有 10,000 个数组，每个数组包含 1,024 个项，而任何项都不会超过 85K。如果您需要超过 10,000,000 个项目，访问模式将决定您是使用更大的数组还是使用第三级嵌套更好，但是有多种数组大小，上述方法是最好的。

于 2013-08-10T19:47:13.490 回答