Скорость выполнения C программы

Question

На экзамене у меня возникла одна проблема по предмету «Основы языка программирования». Я долго думал, но все еще не понял проблемы

Проблема: Ниже приведена программа C, которая выполняется в среде MSVC ++ 6.0 на ПК с конфигурацией ~ CPU Intel 1,8 ГГц, Ram 512 МБ

#define M 10000
#define N 5000
int a[M][N];

void main() {
    int i, j;
    time_t start, stop;

    // Part A
    start = time(0);
    for (i = 0; i < M; i++)
        for (j = 0; j < N; j++)
            a[i][j] = 0;
    stop = time(0);
    printf("%d\n", stop - start);

    // Part B
    start = time(0);
    for (j = 0; j < N; j++)
        for (i = 0; i < M; i++)
            a[i][j] = 0;
    stop = time(0);
    printf("%d\n", stop - start);
}

Объясните, почему часть А выполняется только за 1 с , но для ее завершения потребовалось участие B 8 с ?

Answer 1

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

Answer 2

Старший порядок строк по сравнению с основным порядком столбцов.

Напомним сначала, что все многомерные массивы представлены в памяти как непрерывный блок памяти. Таким образом, многомерный массив A (m, n) может быть представлен в памяти как

a00 a01 a02 ... a0n a10 a11 a12 ... a1n a20 ... amn

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

a00  a01  a02  ...  a0n  a10  a11  a12  ...  a1n  a20 ... amn

1    2    3         n    n+1  n+2  n+3 ...   2n   2n+1    mn

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

a00  a10  a20  ...  am0  a01  a11  a21  ...  am1  a02  ...  amn

или, возможно, более ясно,

a00  a01  a02  ...  a10  a11  a12  ...  a20 ... amn
1    m+1  2m+1      2    m+2  2m+2      3       mn

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

Answer 3

Массив, который вы объявляете, располагается в памяти построчно. В основном у вас есть большой блок из M × N целых чисел, и C делает небольшую хитрость, чтобы заставить вас поверить, что он прямоугольный. Но на самом деле он плоский.

Так что, когда вы проходите через него по линиям (с M в качестве переменной внешнего цикла), вы действительно линейно перемещаетесь по памяти. Что-то, с чем очень хорошо справляется кеш процессора.

Однако, когда вы выполняете итерацию с N во внешнем цикле, вы всегда делаете более или менее случайные скачки в памяти (по крайней мере, для аппаратного обеспечения это выглядит так). Вы получаете доступ к первой ячейке, затем перемещаете M целых чисел дальше и делаете то же самое, и т. Д. Поскольку ваши страницы в памяти обычно имеют размер около 4 КБ, это приводит к доступу к другой странице для каждой итерации внутренней петля. Таким образом, почти любая стратегия кэширования дает сбой, и вы видите значительное замедление.

Answer 4

Из-за аппаратной оптимизации архитектуры. Часть A выполняет операции с последовательными адресами памяти, что позволяет аппаратному обеспечению существенно ускорить обработку вычислений. Часть B в основном постоянно перемещается в памяти, что побеждает множество аппаратных оптимизаций.

Ключевым понятием для этого конкретного случая является кэш процессора .

Answer 5

Проблема в том, как ваш массив лежит в памяти.

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

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

Теперь возникает еще одна проблема: современные процессоры имеют кэши. У них есть несколько кэшей, и у них есть так называемые «строки кэша» для кэша первого уровня. Что это значит. Доступ к памяти быстрый, но недостаточно быстрый. Современные процессоры намного быстрее. Таким образом, у них есть свои кэш-память на чипе, которые ускоряют процесс. Также они больше не обращаются к отдельным ячейкам памяти, но заполняют одну полную строку кэша за один выбор. Это также для производительности. Но такое поведение дает все преимущества операций, которые обрабатывают данные линейно. Когда вы получаете доступ сначала ко всем столбцам подряд, затем к следующей строке и т. Д., Вы фактически работаете линейно. Когда вы впервые обрабатываете все первые столбцы всех строк, вы «прыгаете» в память. Таким образом, вы всегда заставляете заполнять новую строку кэша, можно обработать всего несколько байтов, а затем строка кэша, возможно, станет недействительной при вашем следующем переходе ....

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