为什么多维数组的.NET比正常阵列慢？多维、数组、阵列、正常

2023-09-02 20:41:12 作者：隔壁的老王〆

编辑：我很抱歉大家。我用了交错数组当我真正的意思是说多维数组（可以看出在我下面的例子）。我使用了不正确的名称道歉。我居然发现交错数组会比多维得更快！我已经加入我的三围为锯齿形阵列。

I apologize everybody. I used the term "jagged array" when I actually meant to say "multi-dimensional array" (as can be seen in my example below). I apologize for using the incorrect name. I actually found jagged arrays to be faster than multi-dimensional ones! I have added my measurements for jagged arrays.

我想今天使用锯齿线多维数组，当我看到它的性能是不是因为我本来期望。使用一维阵列和手动计算指数快得多（几乎两倍）比使用2D阵列。我写了使用 1024 * 1024 阵列测试（初始化为随机值），1000次迭代，我得到了我的机器上，结果如下：

I was trying to use a jagged multi-dimensional array today, when I noticed that it's performance is not as I would have expected. Using a single-dimensional array and manually calculating indices was much faster (almost two times) than using a 2D array. I wrote a test using 1024*1024 arrays (initialized to random values), for 1000 iterations, and I got the following results on my machine:

sum(double[], int): 2738 ms (100%)
sum(double[,]):     5019 ms (183%)
sum(double[][]):    2540 ms ( 93%)

这是我的测试code：

This is my test code:

public static double sum(double[] d, int l1) {
    // assuming the array is rectangular
    double sum = 0;
    int l2 = d.Length / l1;
    for (int i = 0; i < l1; ++i)
        for (int j = 0; j < l2; ++j)
            sum += d[i * l2 + j];
    return sum;
}

public static double sum(double[,] d) {
    double sum = 0;
    int l1 = d.GetLength(0);
    int l2 = d.GetLength(1);
    for (int i = 0; i < l1; ++i)
        for (int j = 0; j < l2; ++j)
            sum += d[i, j];
    return sum;
}

public static double sum(double[][] d) {
    double sum = 0;
    for (int i = 0; i < d.Length; ++i)
        for (int j = 0; j < d[i].Length; ++j)
            sum += d[i][j];
    return sum;
}

public static void Main() {
    Random random = new Random();
    const int l1  = 1024, l2 = 1024;
    double[ ] d1  = new double[l1 * l2];
    double[,] d2  = new double[l1 , l2];
    double[][] d3 = new double[l1][];

    for (int i = 0; i < l1; ++i) {
        d3[i] = new double[l2];
        for (int j = 0; j < l2; ++j)
            d3[i][j] = d2[i, j] = d1[i * l2 + j] = random.NextDouble();
    }
    //
    const int iterations = 1000;
    TestTime(sum, d1, l1, iterations);
    TestTime(sum, d2, iterations);
    TestTime(sum, d3, iterations);
}

进一步的调查表明，IL的第二种方法比第一种方法的大23％。（code尺寸的68 VS 52）这主要是由于调用的System.Array ::对GetLength（INT）。编译器还发出呼吁阵列::获取的锯齿线多维数组，而它只是简单地调用 ldelem 的简单数组。

Further investigation showed that the IL for the second method is 23% larger than that of the first method. (Code size 68 vs 52.) This is mostly due to calls to System.Array::GetLength(int). The compiler also emits calls to Array::Get for the jagged multi-dimensional array, whereas it simply calls ldelem for the simple array.

所以，我很纳闷，为什么通过多维数组访问速度慢于正常的阵列？我会认为，编译器（或JIT）会做类似的事情，以我在我的第一个方法做了，但是这不是真正的情况。

So I am wondering, why is access through multi-dimensional arrays slower than normal arrays? I would have assumed the compiler (or JIT) would do something similar to what I did in my first method, but this was not actually the case.

你能普莱舍帮助我理解为什么发生这种情况的方式是？

Could you plese help me understand why this is happening the way it is?

更新：以下亨克Holterman的建议，这里是实施原料与材料：

Update: Following Henk Holterman's suggestion, here is the implementation of TestTime:

public static void TestTime<T, TR>(Func<T, TR> action, T obj,
                                   int iterations)
{
    Stopwatch stopwatch = Stopwatch.StartNew();
    for (int i = 0; i < iterations; ++i)
        action(obj);
    Console.WriteLine(action.Method.Name + " took " + stopwatch.Elapsed);
}

public static void TestTime<T1, T2, TR>(Func<T1, T2, TR> action, T1 obj1,
                                        T2 obj2, int iterations)
{
    Stopwatch stopwatch = Stopwatch.StartNew();
    for (int i = 0; i < iterations; ++i)
        action(obj1, obj2);
    Console.WriteLine(action.Method.Name + " took " + stopwatch.Elapsed);
}

为什么多维数组的.NET比正常阵列慢？多维、数组、阵列、正常

推荐答案