Вопрос по arrays, c, assembly, multidimensional-array, localityofreference – Почему хуже инициализировать двумерный массив, подобный этому?

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

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

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

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

@dlev: почему бы тебе не опубликовать это как ответ? Ned Batchelder
потому что речь идет не о респ. длин о любви Robotnik
Ваш профессор, вероятно, говорит о шаблонах доступа к массивам, иnot инициализации. Инициализация (на момент объявления) имеет свой синтаксис (double array[100][100] = { 0 };) для которого реализация в современных компиляторах, вероятно, «превосходит»; все, что сказано здесь. Jens Gustedt
Этот полезный документ подробно описывает локальность памяти и многие другие факты:akkadia.org/drepper/cpumemory.pdf Crashworks
Справочная информация: вы излишне аннулируете кэш процессора в «медленном» кэше; путь. dlev

Ваш Ответ

4   ответа
2

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

3

Я немного опоздал на вечеринку, и уже есть отличный ответ. Однако я подумал, что могу внести свой вклад, продемонстрировав, как можно экспериментально ответить на этот вопрос, используя инструмент профилирования (в Linux).

Я используюperf инструмент в пакете Ubuntu 10.10linux-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" версия.

Лучше поздно, чем никогда. Понравился этот ответ, большое спасибо! ordinary
4

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

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

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

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

http://www.cplusplus.com/reference/clibrary/cstring/memset/

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

+1 - В C вызов стандартной библиотечной функции ВСЕГДА по порядку.
В c использование стандартных конструкций по сравнению с библиотечными функциями еще лучше: существует синтаксис для инициализации массивов.
@Josh - все компиляторы, которые я использую, понимают, что цикл, присваивающий массиву ноль, является инициализацией. Результирующий код ничем не отличается от использования memset (который также «известен»).
20

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

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

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

Причина того, что ваш код работает медленнее, чем нужно, состоит в том, что он не обращается к элементам массива последовательно. В 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]
    }
}

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

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

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

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

Это именно то, что я искал, спасибо! ordinary
Вау, это отличный ответ!
@ pst- Я преподаю курс компиляторов каждое лето и только сейчас просматривал свои слайды, так что все это было свежим в моей памяти. (Я только что понял, что это означает, что я мог быстро его напечатать, потому что он был в кеше ... жуткий ...)
может быть, здесь не применимо, но вы также можете немного развернуть цикл или позволить компилятору сделать это для вас, чтобы также ускорить работу. Это также может дать кешу и конвейеру некоторые преимущества. Конечно, у вас также, вероятно, есть некоторые глубокие знания об оборудовании, на котором вы работаете.
И вы ожидаете, что я поверю, что это было написано за 8 минут? Пфф. (Очень хороший ответ.)

Похожие вопросы