Почему двумерные массивы работают чуть быстрее одновременых?

Question

[Даниил]

internal class Program
    {
        static void Main(string[] args)
        {
            int k = 10_000;
            Console.WriteLine("Hello, World!");
            Stopwatch s = new Stopwatch();
            int[][] a1 = new int[k][];
            int[,] a2 = new int[k, k];
            int[] a3 = new int[k * k];
            for (int i = 0; i < k; i++)
            {
                a1[i]=new int[k];
                for (int j = 0; j < k; j++)
                {
                    a1[i][j] = Random.Shared.Next(10000);
                    a2[i,j] = a1[i][j];
                    a3[j+k*i] = a1[i][j];
                }
            }
            int n = 20;
            long sum = 0;
            s.Start();
           
            for (int l = 0; l < n; l++)
            {
                for (int i = 0; i < k; i++)
                {
                     
                    for (int j = 0; j < k; j++)
                    {
                        sum+=a1[i][j]  ; 
                    }
                }
            }
           
            s.Stop();
            Console.WriteLine(" sum:" + sum + ",  "+s.ElapsedMilliseconds);
            s.Restart();
            sum = 0;
            for (int l = 0; l < n; l++)
            {
                for (int i = 0; i < k; i++)
                {

                    for (int j = 0; j < k; j++)
                    {
                        sum += a2[i, j]  ; 
                    }
                }
            }
            s.Stop();
            Console.WriteLine(" sum:" + sum + ",  " + s.ElapsedMilliseconds);
            s.Restart();
            sum = 0;
            for (int l = 0; l < n; l++)
            {
                for (int i = 0; i < k; i++)
                {
                    int _i = i * k;
                    for (int j = 0; j < k; j++)
                    {
                        sum += a3[j +_i] ;
                    }
                }
            }
            s.Stop();
            Console.WriteLine(" sum:" + sum + ",  " + s.ElapsedMilliseconds); 
        }
    }
// [][] 4865
//[,]    5192
//[]   4852

Почему arr[x][y] на уровне, чем arr[x+ _y], _u=w*y ?

А например в примерах, что выпадают в сети, там даже без микро оптимизации, цифры другие, и одномерный в раза 2 быстрее. Почему у меня не так.

Comments

[mayton2019]

Сделай тест подлиннее. Хотя-бы в 1 минуту на каждую матрицу.
И попробуй перевернуть индексы местами (i,j).

И еще неплохо-бы размеры строк матриц выровнять под границу в 64 байта.

[Даниил]

mayton2019,

sum+=a1[i][j] => sum+=a1[j][i]

А зачем. Z ;Я же хочу как быстрее а не как медленнее. Ну конечно да, если замедлить двумерный, что бы одновременный был быстрее на фоне. Не понял совет.

[mayton2019]

Даниил, я честно говоря не помню как DotNet расставляет элементы в памяти. Но ты словил эффект удачного попадания в кеш для многомерных массивов а для одномерного почему-то расклад был неудачен.

[Даниил]

mayton2019, А я понял. Я не правильно делаю обход массива, я забыл про преимущество использовать

for(int i=0;i<x*y;i++)  
//вместо
for (int i)
  for(int j)

[mayton2019]

Даниил, помогло? У меня нет шарпов под рукой. Я не могу проверить.

Answer 1

[Роман]

// [][] 4865
// [,]  5192
// []   4852

int[] - простейший массив, в памяти лежит линейно.
Работает за счёт IL инструкций (newarr, ldelem, ...), которые могут лучше оптимизировать jit компилятором

int[,] - многомерный массив, в памяти лежит также линейно как int[].
Работает через вызовы методов, а так же за счёт не популярности работает на общем коде с массивами где первый элемент может быть не по индексу 0. Соответственно, для доставания элементов требуется дополнительная математика и проверки.

int[][] - массив массивов, в памяти линейно лежат ссылки на линейно лежащие строки.
Работает медленнее int[] потому что требуется доступ к другим участкам памяти (строкам).