Почему порядок циклов влияет на производительность при итерации по двумерному массиву?

Возможный дубликат:
Какой из этих двух циклов for более эффективен с точки зрения времени и производительности кэша

Ниже приведены две почти идентичные программы, за исключением того, что я переключил i а также j переменные вокруг. Они оба бегут в разное количество времени. Может ли кто-нибудь объяснить, почему это происходит?

Версия 1

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (i = 0; i < 4000; i++) {
    for (j = 0; j < 4000; j++) {
      x[j][i] = i + j; }
  }
}

Версия 2

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (j = 0; j < 4000; j++) {
     for (i = 0; i < 4000; i++) {
       x[j][i] = i + j; }
   }
}
Источник

7 ответов

Решение

Как уже говорили другие, проблема заключается в сохранении места в памяти в массиве: x[i][j], Вот немного понимания почему:

У вас есть двумерный массив, но память в компьютере по своей сути является одномерной. Итак, пока вы представляете свой массив следующим образом:

0,0 | 0,1 | 0,2 | 0,3
----+-----+-----+----
1,0 | 1,1 | 1,2 | 1,3
----+-----+-----+----
2,0 | 2,1 | 2,2 | 2,3

Ваш компьютер хранит его в памяти в виде одной строки:

0,0 | 0,1 | 0,2 | 0,3 | 1,0 | 1,1 | 1,2 | 1,3 | 2,0 | 2,1 | 2,2 | 2,3

Во втором примере вы получаете доступ к массиву, сначала перебирая 2-й номер, то есть:

x[0][0] 
        x[0][1]
                x[0][2]
                        x[0][3]
                                x[1][0] etc...

Это означает, что вы бьете их по порядку. Теперь посмотрим на 1-ую версию. Ты делаешь:

x[0][0]
                                x[1][0]
                                                                x[2][0]
        x[0][1]
                                        x[1][1] etc...

Из-за способа, которым C разместил 2-й массив в памяти, вы просите его перепрыгнуть повсюду. Но теперь для кикера: почему это важно? Все обращения к памяти одинаковы, верно?

Нет: из-за кешей. Данные из вашей памяти передаются в ЦП небольшими порциями (называемыми "строками кэша"), обычно 64 байта. Если у вас есть 4-байтовые целые числа, это означает, что вы получаете 16 последовательных целых чисел в аккуратном небольшом пакете. На самом деле довольно медленно загружать эти куски памяти; Ваш процессор может выполнять большую работу за время, необходимое для загрузки одной строки кэша.

Теперь вернемся к порядку доступа: второй пример: (1) захват фрагмента в 16 дюймов, (2) изменение всех из них, (3) повторение 4000*4000/16 раз. Это приятно и быстро, и процессору всегда есть над чем работать.

Первый пример: (1) получить фрагмент из 16-ти дюймов, (2) изменить только один из них, (3) повторить 4000 * 4000 раз. Это потребует в 16 раз больше "выборок" из памяти. Ваш процессор на самом деле должен будет сидеть без дела, дожидаясь появления этой памяти, а пока он сидит, вы теряете драгоценное время.

Важная заметка:

Теперь, когда у вас есть ответ, вот интересная заметка: нет никакой внутренней причины, по которой ваш второй пример должен быть быстрым. Например, в Фортране первый пример будет быстрым, а второй - медленным. Это потому, что вместо того, чтобы разбирать вещи на концептуальные "строки", как это делает C, Fortran расширяется до "столбцов", то есть:

0,0 | 1,0 | 2,0 | 0,1 | 1,1 | 2,1 | 0,2 | 1,2 | 2,2 | 0,3 | 1,3 | 2,3

Раскладка C называется "Major-row", а Fortran- "Major-column". Как видите, очень важно знать, является ли ваш язык программирования основным или столбцовым! Вот ссылка для получения дополнительной информации: http://en.wikipedia.org/wiki/Row-major_order

Источник

Ничего общего со сборкой. Это связано с отсутствием кэша.

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

Смотрите также: http://en.wikipedia.org/wiki/Loop_interchange.

Источник

Версия 2 будет работать намного быстрее, потому что она использует кэш вашего компьютера лучше, чем версия 1. Если подумать, массивы - это просто смежные области памяти. Когда вы запрашиваете элемент в массиве, ваша ОС, вероятно, внесет страницу памяти в кеш, содержащий этот элемент. Однако, поскольку следующие несколько элементов также находятся на этой странице (потому что они являются смежными), следующий доступ уже будет в кеше! Это то, что делает версия 2, чтобы ускорить процесс.

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

Источник

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

Источник

Помимо других отличных ответов о попаданиях в кеш, есть также возможная разница в оптимизации. Ваш второй цикл, вероятно, будет оптимизирован компилятором во что-то эквивалентное:

  for (j=0; j<4000; j++) {
    int *p = x[j];
    for (i=0; i<4000; i++) {
      *p++ = i+j;
    }
  }

Это менее вероятно для первого цикла, потому что он должен увеличивать указатель "p" каждый раз на 4000.

РЕДАКТИРОВАТЬ: p++ и даже *p++ = .. может быть скомпилирован с одной инструкцией процессора в большинстве процессоров. *p = ..; p += 4000 не может, поэтому есть меньше преимуществ в его оптимизации. Это также сложнее, потому что компилятор должен знать и использовать размер внутреннего массива. И это не происходит часто во внутреннем цикле в нормальном коде (это происходит только для многомерных массивов, где последний индекс остается постоянным в цикле, а второй - последний шаг), поэтому оптимизация является менее приоритетной,

Источник

Эта строка виновника:

x[j][i]=i+j;

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

Я пробовал с

x[50000][50000];

и время выполнения составляет 13 с для версии 1 против 0,6 с для версии 2.

Источник

Я пытаюсь дать общий ответ.

Так как i[y][x] это сокращение для *(i + y*array_width + x) в C (попробуйте классный int P[3]; 0[P] = 0xBEEF;).

Как вы перебираете yперебираете куски размером array_width * sizeof(array_element), Если у вас есть это в вашем внутреннем цикле, то у вас будет array_width * array_height итерации по этим кускам.

Отразив заказ, вы будете иметь только array_height итерации чанков, и между любыми итерациями чанков вы будете иметь array_width итерации только sizeof(array_element),

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

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