Путаница по поводу разного времени работы двух алгоритмов в C

У меня есть массив, long matrix[8*1024][8*1024] и две функции sum1 и sum2:

long sum1(long m[ROWS][COLS]) {
    long register sum = 0;
    int i,j;

    for (i=0; i < ROWS; i++) {
        for (j=0; j < COLS; j++) {
            sum += m[i][j];
        }
    }
    return sum;
}

long sum2(long m[ROWS][COLS]) {
    long register sum = 0;
    int i,j;

    for (j=0; j < COLS; j++) {
        for (i=0; i < ROWS; i++) {
            sum += m[i][j];
        }
    }

    return sum;
}

Когда я выполняю две функции с данным массивом, я получаю время выполнения:

сумма 1: 0,19 с

сумма 2: 1,25 с

Кто-нибудь может объяснить, почему существует такая огромная разница?

Ответ 1

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

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

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

Наиболее частые обращения к программе - последовательные места в памяти. Очень часто после того, как программа читает элемент 237 массива, она вскоре читает 238, затем 239 и так далее. Реже читается 7024 сразу после чтения 237.

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

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

Связанный ресурс: Макет памяти многомерных массивов

Ответ 2

C использует упорядочение по основным строкам для хранения многомерных массивов, как описано в § 6.5.2.1 Подписка на массивы, параграф 3 Стандарта C:

Последовательные операторы нижнего индекса обозначают элемент объекта многомерного массива. Если E - массив n -dimensional (n> = 2) с размерами ixjx. , , xk, затем E (используется как отличное от lvalue) преобразуется в указатель на массив (n - 1) -dimensional с размерами jx. , , х к. Если унарный оператор * применяется к этому указателю явно или неявно в результате подписки, результатом является ссылочный (n - 1) массив -dimensional, который сам преобразуется в указатель, если он используется как значение, отличное от lvalue. Из этого следует, что массивы хранятся в основном порядке строк (последний индекс изменяется быстрее всего).

Акцент мой.

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

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

Есть некоторые другие языки, которые используют упорядочение по главному столбцу для многомерных массивов; среди них R, FORTRAN и MATLAB. Если бы вы написали эквивалентный код на этих языках, вы бы sum2 более быстрый вывод с sum2.

Ответ 3

На машине с кешем данных (даже у 68030 он есть) чтение/запись данных в последовательных ячейках памяти происходит намного быстрее, потому что блок памяти (размер зависит от процессора) выбирается один раз из памяти и затем вызывается из кеша ( операция чтения) или записано все сразу (очистка кэша для операции записи).

"Пропуская" данные (читая далеко от предыдущего чтения), ЦПУ должен снова прочитать память.

Вот почему ваш первый фрагмент быстрее.

Для более сложных операций (например, быстрого преобразования Фурье), когда данные читаются более одного раза (в отличие от вашего примера), многие библиотеки (например, FFTW) предлагают использовать шаг для размещения вашей организации данных (в строках/столбцах), Никогда не используйте его, всегда сначала перемещайте ваши данные и используйте шаг 1, это будет быстрее, чем пытаться сделать это без транспонирования.

Чтобы убедиться, что ваши данные последовательны, никогда не используйте 2D нотацию. Сначала поместите данные в выбранную строку и установите указатель на начало строки, затем используйте внутренний цикл в этой строке.

for (i=0; i < ROWS; i++) {
    const long *row = m[i];
    for (j=0; j < COLS; j++) {
        sum += row[j];
    }
}

Если вы не можете сделать это, это означает, что ваши данные неправильно ориентированы.

Ответ 4

Это проблема с кешем.

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

Ответ 5

Матрица в памяти выровнена линейно, так что элементы в строке находятся рядом друг с другом в памяти (spacial locality). Когда вы перемещаетесь по элементам в таком порядке, что вы проходите все столбцы подряд, а затем переходите к следующему, когда ЦП сталкивается с записью, которая еще не загружена в свой кэш, он пойдет и загрузит это значение по с целым блоком других значений, близких к нему в физической памяти, поэтому следующие несколько значений будут уже кэшированы к тому времени, когда потребуется их прочитать.

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

К тому времени, когда вы вернетесь к другой записи, которую ранее кэшировали, она, скорее всего, будет выгружена из кэша в пользу всех других данных, которые вы с тех пор загрузили, поскольку они больше не будут использоваться в последнее время (temporal locality)

Ответ 6

Чтобы расширить другие ответы о том, что это связано с отсутствием кэша для второй программы и при условии, что вы используете Linux, * BSD или MacOS, то Cachegrind может дать вам просветление. Он является частью valgrind и будет запускать вашу программу без изменений и выводить статистику использования кэша. Это работает очень медленно, хотя.

http://valgrind.org/docs/manual/cg-manual.html