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

Edit: Я прошу прощения всех. Я использовал термин «зубчатый массив», когда я на самом деле хотел сказать «multidimensional array» (как можно видеть в моем примере ниже). Приносим извинения за неправильное имя. Я на самом деле нашел зубчатые массивы быстрее, чем многомерные! Я добавил свои измерения для зубчатых массивов.

Я пытался использовать зазубренный multidimensional array сегодня, когда я заметил, что его производительность не так, как я ожидал. Использование одномерного массива и ручное вычисление индексов было намного быстрее (почти в два раза), чем использование 2D-массива. Я написал тест с использованием массивов 1024*1024 (с инициализацией на случайные значения), на 1000 итераций, и я получил следующие результаты на своей машине:

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

Это мой тестовый код:

 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); } 

Дальнейшее исследование показало, что ИЛ для второго метода на 23% больше, чем у первого метода. (Размер кода 68 против 52.) В основном это связано с вызовами System.Array::GetLength(int) . Компилятор также выдает вызовы в Array::Get для зазубренный multidimensional array, тогда как он просто вызывает ldelem для простого массива.

Поэтому мне интересно, почему доступ через многомерные массивы медленнее, чем обычные массивы? Я бы предположил, что компилятор (или JIT) сделает что-то похожее на то, что я сделал в моем первом методе, но на самом деле это было не так.

Не могли бы вы помочь мне понять, почему это происходит так, как есть?


Обновление: после предложения Хенка Холтермана, вот реализация TestTime :

 public static void TestTime(Func 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(Func 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); } 

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

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

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

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

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

Кроме того, GetLength (int dimension) проведет проверку границ параметра.

Интересно, что я запускал следующий код сверху, используя 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 многомерность vs. single / jagged имеет огромное значение.

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

 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(Func 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(Func 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(sum, d1, l1, iterations); TestTime(sum, d2, iterations); TestTime(sum, d3, iterations); TestTime(sum, d1, l1, iterations); TestTime(sum, d2, iterations); TestTime(sum, d3, iterations); } } } 

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

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

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

В то время как у mutli-мерного массива выделена память в одном компактном компе.

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

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

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

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

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

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

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

  • Неверная операция поперечного streamа
  • Можно ли принудительно использовать свойство auto-property для использования поля для чтения в режиме readonly?
  • IEqualityComparer , который использует ReferenceEquals
  • Не удалось загрузить файл или сборку или одну из ее зависимостей
  • отключить колесо мыши на элементах управления в wpf
  • Могут ли атрибуты добавляться динамически в C #?
  • Могу ли я разместить Windows Form внутри элемента управления
  • Способ определения, является ли строка пути локальной или удаленной машиной
  • Инициировать объект с определенным временем выполнения
  • Что такое IndexOutOfRangeException / ArgumentOutOfRangeException и как его исправить?
  • Можно ли перехватить вывод консоли?
  • Давайте будем гением компьютера.