for(int i = 0; i<100; i++)
for(int j = 0; j<100; j++)
array[j][i] = 0;
// array[i][j] = 0;
Мой профессор сказал, что было намного дороже инициализировать двумерный массив в первую очередь, а не второй. Может кто-нибудь объяснить, что происходит под капотом, что делает это дело? Или, имеют ли два средства инициализации равную производительность?
Как упоминалось в @dlev, это связано с локалью ссылки и связано с тем, как работает физическое оборудование на компьютере.
Внутри компьютера существует много разных типов памяти. Как правило, только определенные ячейки памяти (регистры) могут выполнять на них фактические операции; в остальное время, если вы выполняете операции с данными, вы должны загрузить его из памяти в регистр, выполнить некоторое вычисление, а затем записать его обратно.
Основная память (ОЗУ) намного, намного медленнее, чем регистры, часто в сотни и тысячи раз. Следовательно, следует избегать чтения из памяти, если это вообще возможно. Чтобы решить эту проблему, большинство компьютеров обычно имеют специальные области памяти, называемые кэшами. Задача кэша состоит в том, чтобы хранить данные, которые недавно были получены из памяти, так что, если к этой же области памяти снова обращаются, это значение можно вытащить из кеша (быстро), а не из основной памяти (медленно). Как правило, кэши сконструированы так, что если значение считывается из памяти, это значение, плюс целая куча смежных значений, втягивается в кеш. Таким образом, если вы перебираете массив, то после прочтения первого значения остальные значения из массива будут сидеть в кеше и могут быть доступны более эффективно.
Причина, по которой ваш код медленнее, чем он должен быть, заключается в том, что он не обращается к элементам массива последовательно. В C 2D-массивы выложены в порядок строк, что означает, что память упорядочена как
A[0][0] A[0][4] A[0][5] ... A[1][0] A[1][6] A[1][7] ... A[2][0] A[2][8] A[2][9] ...
Следовательно, если вы используете этот цикл for:
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// Do something with A[i][j]
}
}
Тогда вы получите отличную локальность, потому что вы будете получать доступ к элементам массива в том порядке, в котором они появляются в памяти. Это делает число чтений основной памяти очень маленьким, поскольку все, как правило, находится в кеше и готово к работе.
Однако, если вы меняете петли, как вы это делали, ваши обращения перескакивают в памяти и не обязательно являются последовательными. Это означает, что у вас будет много промахов в кеше, в которых адрес памяти, который вы читаете дальше, не находится в кеше. Это увеличивает количество загрузок кэш-памяти, что может значительно замедлить работу программы.
Компиляторы начинают получать достаточно умные, чтобы автоматически обменивать петли, как это происходит автоматически, но мы по-прежнему не можем игнорировать эти детали. Как правило, при написании кода C или С++ для многомерных массивов попробуйте выполнить итерацию в порядке порядка строк, а не в порядке столбцов. Вы можете получать заметные ускорения в своей программе.
Надеюсь, это поможет!
Вероятно, я заберусь для этого, но если вы программируете C, то наиболее вероятным будет:
memset (массив, 0, sizeof (массив));
Затем вы можете отложить всю ответственность за оптимизацию (что вас явно беспокоит) за внедрение memset. Любые конкретные преимущества аппаратного обеспечения могут быть выполнены там.
http://en.wikipedia.org/wiki/Sizeof#Using_sizeof_with_arrays/
http://www.cplusplus.com/reference/clibrary/cstring/memset/
Другое наблюдение: если вы начинаете с нуля, спросите себя, почему? Если ваш массив статичен (что для этого достаточно, вероятно, это?), То cstartup инициализирует до нуля для вас. Опять же, это, вероятно, будет использовать наиболее эффективный способ для вашего оборудования.
Я немного опаздываю на вечеринку, и уже есть отличный ответ. Тем не менее, я думал, что могу внести свой вклад, продемонстрировав, как можно было бы экспериментально ответить на этот вопрос с помощью инструмента профилирования (в Linux).
Я использую инструмент perf в пакете Ubuntu 10.10 linux-tools-common.
Вот небольшая программа на C, которую я написал, чтобы ответить на этот вопрос:
// test.c
#define DIM 1024
int main()
{
int v[DIM][DIM];
unsigned i, j;
for (i = 0; i < DIM; i++) {
for (j = 0; j < DIM; j++) {
#ifdef ROW_MAJOR_ORDER
v[i][j] = 0;
#else
v[j][i] = 0;
#endif
}
}
return 0;
}
Затем скомпилируйте две разные версии:
$ gcc test.c -O0 -DROW_MAJOR_ORDER -o row-maj
$ gcc test.c -O0 -o row-min
Примечание. Я отключил оптимизацию с помощью -O0, поэтому gcc не имеет шансов переставить наш цикл, чтобы быть более эффективным.
Мы можем перечислить статистику производительности, доступную с помощью perf, выполнив perf list. В этом случае нас интересуют пропуски кэша, которые являются событием cache-misses.
Теперь это так же просто, как запустить каждую версию программы много раз и принять среднее значение:
$ perf stat -e cache-misses -r 100 ./row-min
Performance counter stats for './row-min' (100 runs):
286468 cache-misses ( +- 0.810% )
0.016588860 seconds time elapsed ( +- 0.926% )
$ perf stat -e cache-misses -r 100 ./row-maj
Performance counter stats for './row-maj' (100 runs):
9594 cache-misses ( +- 1.203% )
0.006791615 seconds time elapsed ( +- 0.840% )
И теперь мы экспериментально подтвердили, что вы действительно видите на два порядка больше промахов в кеше с версией "row-minor".
Если вы посмотрите на ячейки памяти, к которым обращаются по каждому методу, второй будет иметь доступ к последовательным байтам, в то время как первый будет прыгать вокруг на 100-байтные прыжки. Кэш памяти будет работать намного эффективнее, если вы сделаете это вторым способом.