Изменить: Прошу прощения у всех. Я использовал термин "зубчатый массив", когда я на самом деле хотел сказать "многомерный массив" (как можно видеть в моем примере ниже). Приносим извинения за неправильное имя. Я на самом деле нашел зубчатые массивы быстрее, чем многомерные! Я добавил свои измерения для зубчатых массивов.
Я пытался использовать многомерный массив jagged сегодня, когда я заметил, что его производительность не такая, как я ожидал. Использование одномерного массива и ручное вычисление индексов было намного быстрее (почти в два раза), чем использование 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 для многомерного массива jagged, тогда как он просто вызывает ldelem для простого массива.
Итак, мне интересно, почему доступ через многомерные массивы медленнее, чем обычные массивы? Я бы предположил, что компилятор (или JIT) сделает что-то похожее на то, что я сделал в моем первом методе, но на самом деле это не так.
Не могли бы вы помочь мне понять, почему это происходит так, как оно есть?
Обновление: Следующее предложение Хенка Холтермана, вот реализация 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);
}
Одномерные массивы с нижней границей 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. одиночный/зубчатый имеет огромное значение.
Полная программа:
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);
}
}
}
Поскольку многомерный массив является просто синтаксическим сахаром, так как это действительно просто плоский массив с некоторой магией вычисления индекса. С другой стороны, массив с зазубринами подобен массиву массивов. При использовании двумерного массива доступ к элементу требует считывания памяти только один раз, а с двухуровневым массивом, вам нужно дважды прочитать память.
РЕДАКТИРОВАТЬ:. По-видимому, оригинальный плакат смешал "зубчатые массивы" с "многомерными массивами", поэтому мои рассуждения точно не стоят. По настоящей причине, проверьте тяжелую артиллерию Джона Скита выше.
Массированные массивы представляют собой массивы ссылок на классы (другие массивы) вплоть до массива листьев, которые могут быть массивом примитивного типа. Следовательно, память, выделенная для каждого из других массивов, может быть повсюду.
В то время как у mutli-мерного массива выделена его память в одном компактном компе.
Я думаю, что у него есть что-то сделать для того, что зубчатые массивы - это на самом деле массивы массивов, поэтому есть два уровня косвенности, чтобы добраться до фактических данных.
Я со всеми здесь
У меня была программа с трехмерным массивом, позвольте мне сказать вам, что когда я переместил массив в два измерения, я увидел огромный импульс, а затем перешел в один размерный массив.
В конце концов, я думаю, что я видел более 500% повышения производительности во время выполнения.
Единственным недостатком была сложность, добавленная, чтобы узнать, где было то, что в одномерном массиве, и в сравнении с тремя.
Я думаю, что многомерный медленнее, время выполнения должно проверять проверку двух или более (трехмерных и верхних) границ.
Проверка границ. Ваша переменная "j" может превышать l2, если "i" меньше, чем l1. Это не будет законным во втором примере