Почему хуже инициализировать двумерный массив, подобный этому?

for(int i = 0; i<100; i++)

    for(int j = 0; j<100; j++)

         array[j][i] = 0;
         // array[i][j] = 0;

Мой профессор сказал, что инициализация двумерного массива в первом случае намного дороже, чем во втором. Может кто-нибудь объяснить, что происходит под капотом, что делает это дело? Или оба средства инициализации имеют одинаковую производительность?

Источник

4 ответа

Решение

Как уже упоминалось @dlev, это связано с локальностью ссылок и связано с тем, как работает физическое оборудование компьютера.

Внутри компьютера есть много разных типов памяти. Как правило, только определенные области памяти (регистры) могут иметь фактические операции над ними; в остальное время, если вы выполняете операции с данными, вы должны загрузить их из памяти в регистр, выполнить некоторые вычисления, а затем записать их обратно.

Основная память (ОЗУ) намного, намного медленнее, чем регистры, часто в сотни и тысячи раз. Следовательно, следует избегать чтения из памяти, если это вообще возможно. Для решения этой проблемы большинство компьютеров обычно имеют специальные области памяти, называемые кэшами. Задача кэша состоит в том, чтобы хранить данные, к которым недавно обращались, из памяти, так что, если к той же самой области памяти обращаются снова, значение может быть извлечено из кэша (быстро), а не из основной памяти (медленно). Как правило, кэши разрабатываются таким образом, чтобы при чтении значения из памяти это значение вместе с целым рядом смежных значений помещалось в кэш. Таким образом, если вы выполняете итерацию по массиву, то после прочтения первого значения остальные значения массива будут храниться в кэше, и к ним можно будет обращаться более эффективно.

Причина того, что ваш код работает медленнее, чем нужно, заключается в том, что он не обращается к элементам массива последовательно. В C двумерные массивы располагаются в основном порядке строк, что означает, что память организована как

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 (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        // Do something with A[i][j]
    }
}

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

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

Компиляторы начинают становиться достаточно умными, чтобы автоматически обмениваться подобными циклами, но мы все еще далеки от возможности игнорировать эти детали. Как правило, при написании кода на C или C++ для многомерных массивов старайтесь выполнять итерацию в основном порядке строк, а не в основном столбце. Вы можете получить заметные ускорения в вашей программе.

Надеюсь это поможет!

Источник

Я, вероятно, буду за это опускаться, но если вы программируете на C, то, скорее всего, "лучший":

memset (массив, 0, sizeof(массив));

Затем вы можете отложить всю ответственность за оптимизацию (о которой вы, очевидно, беспокоитесь) до реализации memset. Любые конкретные аппаратные преимущества могут быть сделаны там.

http://en.wikipedia.org/wiki/Sizeof

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% )

И теперь мы экспериментально убедились, что вы на самом деле видите на два порядка больше пропусков кэша с версией "строка-минор".

Источник

Если вы посмотрите на ячейки памяти, к которым обращается каждый метод, второй получит доступ к последовательным байтам, тогда как первый будет прыгать на 100-байтовых скачках. Кэш памяти будет работать намного эффективнее, если вы сделаете это вторым способом.

Источник
Другие вопросы по тегам