Почему многомерные массивы в .NET медленнее, чем обычные массивы?

Потому что многомерный массив - это просто синтаксический сахар, поскольку на самом деле это просто плоский массив с некоторой магией вычисления индекса. С другой стороны, зубчатый массив подобен массиву массивов. В случае двумерного массива для доступа к элементу требуется чтение памяти только один раз, в то время как для двухуровневого массива с зазубринами вам нужно дважды прочитать память.

Обновлено: Очевидно, в оригинальном плакате «зубчатые массивы» смешивались с «многомерными массивами», поэтому мои рассуждения не совсем верны. Чтобы узнать настоящую причину, проверьте ответ Джона Скита о тяжелой артиллерии выше.

Я думаю, что здесь есть чем заняться, потому что зубчатые массивы на самом деле являются массивами массивов, следовательно, есть два уровня косвенного обращения к фактическим данным.

Проверка границ. Ваша переменная «j» может превышать l2 при условии, что «i» меньше l1. Во втором примере это было бы недопустимо.

Неровные массивы - это массивы ссылок на классы (другие массивы) вплоть до листового массива, который может быть массивом примитивного типа. Следовательно, память, выделенная для каждого из других массивов, может быть повсюду.

В то время как многомерный массив имеет свою память, распределенную в виде одного непрерывного блока.

Проверка границ массива?

Одномерный массив имеет член длины, к которому вы обращаетесь напрямую - при компиляции это просто чтение из памяти.

Для многомерного массива требуется вызов метода GetLength (int Dimension), который обрабатывает аргумент, чтобы получить соответствующую длину для этого измерения. Это не компилируется до чтения из памяти, поэтому вы получаете вызов метода и т. д.

Кроме того, GetLength (int Dimension) будет проверять границы параметра.

Я здесь со всеми

У меня была программа с трехмерным массивом, позвольте мне сказать вам, что когда я переместил массив в двухмерный, я увидел огромный прирост, а затем я перешел к одномерному массиву.

В конце концов, я думаю, что я увидел прирост производительности более чем на 500% во время выполнения.

Единственным недостатком была сложность определения того, где что находится в одномерном массиве, а не в трех.

Одномерные массивы с нижней границей 0 являются типом, отличным от многомерных или ненулевых массивов нижней границы в IL (vector против array IIRC). С vector проще работать - чтобы добраться до элемента x, достаточно выполнить pointer + size * x. Для array вы должны выполнить pointer + size * (x-lower bound) для одномерного массива и еще больше арифметических операций для каждого добавляемого вами измерения.

В основном среда CLR оптимизирована для гораздо более распространенных случаев.

Я думаю, что многомерный процесс медленнее, среда выполнения должна проверять две или более границы (трехмерные и выше).

Интересно, что я запустил следующий код сверху используя VS2008 NET3.5SP1 Win32 на коробке Vista, а в выпуске / оптимизации разница была едва заметной, в то время как debug / noopt многотомные массивы были намного медленнее. (Я провел три теста дважды, чтобы уменьшить влияние JIT во втором наборе.)

  Here are my numbers: 
    sum took 00:00:04.3356535
    sum took 00:00:04.1957663
    sum took 00:00:04.5523050
    sum took 00:00:04.0183060
    sum took 00:00:04.1785843 
    sum took 00:00:04.4933085

Посмотрите на второй набор из трех чисел. Мне не хватает разницы, чтобы кодировать все в одномерных массивах.

Хотя я их не публиковал, в Debug / unoptimized multidimension vs. одиночный / зубчатый действительно имеет огромное значение.

Полная программа:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace single_dimension_vs_multidimension
{
    class Program
    {


        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 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);
        }
        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<double[], int, double>(sum, d1, l1, iterations);
            TestTime<double[,], double>(sum, d2, iterations);

            TestTime<double[][], double>(sum, d3, iterations);
            TestTime<double[], int, double>(sum, d1, l1, iterations);
            TestTime<double[,], double>(sum, d2, iterations);
            TestTime<double[][], double>(sum, d3, iterations); 
        }

    }
}

Что быстрее всего зависит от размеров ваших массивов.

Изображение для удобства чтения:

Результат в консоли:

// * Summary *

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.18363.997 (1909/November2018Update/19H2)
Intel Core i7-6700HQ CPU 2.60GHz (Skylake), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=3.1.302
  [Host]        : .NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT
  .NET Core 3.1 : .NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT

Job=.NET Core 3.1  Runtime=.NET Core 3.1

|           Method |    D |            Mean |         Error |        StdDev |      Gen 0 |     Gen 1 |     Gen 2 |  Allocated |
|----------------- |----- |----------------:|--------------:|--------------:|-----------:|----------:|----------:|-----------:|
| 'double[D1][D2]' |   10 |        376.2 ns |       7.57 ns |      12.00 ns |     0.3643 |         - |         - |     1144 B |
| 'double[D1, D2]' |   10 |        325.5 ns |       3.71 ns |       3.47 ns |     0.2675 |         - |         - |      840 B |
| 'double[D1][D2]' |   50 |      4,821.4 ns |      44.71 ns |      37.34 ns |     6.8893 |         - |         - |    21624 B |
| 'double[D1, D2]' |   50 |      5,834.1 ns |      64.35 ns |      60.20 ns |     6.3629 |         - |         - |    20040 B |
| 'double[D1][D2]' |  100 |     19,124.4 ns |     230.39 ns |     454.77 ns |    26.2756 |    0.7019 |         - |    83224 B |
| 'double[D1, D2]' |  100 |     23,561.4 ns |     299.18 ns |     279.85 ns |    24.9939 |         - |         - |    80040 B |
| 'double[D1][D2]' |  500 |  1,248,458.7 ns |  11,241.19 ns |  10,515.01 ns |   322.2656 |  160.1563 |         - |  2016025 B |
| 'double[D1, D2]' |  500 |    966,940.8 ns |   5,694.46 ns |   5,326.60 ns |   303.7109 |  303.7109 |  303.7109 |  2000034 B |
| 'double[D1][D2]' | 1000 |  8,987,202.8 ns |  97,133.16 ns |  90,858.41 ns |  1421.8750 |  578.1250 |  265.6250 |  8032582 B |
| 'double[D1, D2]' | 1000 |  3,628,421.3 ns |  72,240.02 ns | 177,206.01 ns |   179.6875 |  179.6875 |  179.6875 |  8000036 B |
| 'double[D1][D2]' | 1500 | 26,496,994.4 ns | 380,625.25 ns | 356,037.09 ns |  3406.2500 | 1500.0000 |  531.2500 | 18048064 B |
| 'double[D1, D2]' | 1500 | 12,417,733.7 ns | 243,802.76 ns | 260,866.22 ns |   156.2500 |  156.2500 |  156.2500 | 18000038 B |
| 'double[D1][D2]' | 3000 | 86,943,097.4 ns | 485,339.32 ns | 405,280.31 ns | 12833.3333 | 7000.0000 | 1333.3333 | 72096325 B |
| 'double[D1, D2]' | 3000 | 57,969,405.9 ns | 393,463.61 ns | 368,046.11 ns |   222.2222 |  222.2222 |  222.2222 | 72000100 B |

// * Hints *
Outliers
  MultidimensionalArrayBenchmark.'double[D1][D2]': .NET Core 3.1 -> 1 outlier  was  removed (449.71 ns)
  MultidimensionalArrayBenchmark.'double[D1][D2]': .NET Core 3.1 -> 2 outliers were removed, 3 outliers were detected (4.75 us, 5.10 us, 5.28 us)
  MultidimensionalArrayBenchmark.'double[D1][D2]': .NET Core 3.1 -> 13 outliers were removed (21.27 us..30.62 us)
  MultidimensionalArrayBenchmark.'double[D1, D2]': .NET Core 3.1 -> 1 outlier  was  removed (4.19 ms)
  MultidimensionalArrayBenchmark.'double[D1, D2]': .NET Core 3.1 -> 3 outliers were removed, 4 outliers were detected (11.41 ms, 12.94 ms..13.61 ms)
  MultidimensionalArrayBenchmark.'double[D1][D2]': .NET Core 3.1 -> 2 outliers were removed (88.68 ms, 89.27 ms)

// * Legends *
  D         : Value of the 'D' parameter
  Mean      : Arithmetic mean of all measurements
  Error     : Half of 99.9% confidence interval
  StdDev    : Standard deviation of all measurements
  Gen 0     : GC Generation 0 collects per 1000 operations
  Gen 1     : GC Generation 1 collects per 1000 operations
  Gen 2     : GC Generation 2 collects per 1000 operations
  Allocated : Allocated memory per single operation (managed only, inclusive, 1KB = 1024B)
  1 ns      : 1 Nanosecond (0.000000001 sec)

Код эталонного теста:

[SimpleJob(BenchmarkDotNet.Jobs.RuntimeMoniker.NetCoreApp31)]
[MemoryDiagnoser]
public class MultidimensionalArrayBenchmark {
    [Params(10, 50, 100, 500, 1000, 1500, 3000)]
    public int D { get; set; }

    [Benchmark(Description = "double[D1][D2]")]
    public double[][] JaggedArray() {
        var array = new double[D][];
        for (int i = 0; i < array.Length; i++) {
            var subArray = new double[D];
            array[i] = subArray;

            for (int j = 0; j < subArray.Length; j++) {
                subArray[j] = j + i * 10;
            }
        }

        return array;
    }

    [Benchmark(Description = "double[D1, D2]")]
    public double[,] MultidimensionalArray() {
        var array = new double[D, D];
        for (int i = 0; i < D; i++) {
            for (int j = 0; j < D; j++) {
                array[i, j] = j + i * 10;
            }
        }

        return array;
    }
}