Пустой цикл медленнее, чем непустый в C

При попытке узнать, как долго выполнялась строка кода C, я заметил эту странную вещь:

int main (char argc, char * argv[]) {
    time_t begin, end;
    uint64_t i;
    double total_time, free_time;
    int A = 1;
    int B = 1;

    begin = clock();
    for (i = 0; i<(1<<31)-1; i++);
    end = clock();
    free_time = (double)(end-begin)/CLOCKS_PER_SEC;
    printf("%f\n", free_time);

    begin = clock();
    for (i = 0; i<(1<<31)-1; i++) {
        A += B%2;
    }
    end = clock();
    free_time = (double)(end-begin)/CLOCKS_PER_SEC;
    printf("%f\n", free_time);

    return(0);
}

Что при выполнении показов:

5.873425
4.826874

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

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

Я использую кодовые блоки как IDE с GNU gcc-компилятором, linux ubuntu 14.04 и имею Quadcore intel i5 на 2.3 ГГц (я пытался запустить программу на одном ядре, это не меняет результат).

Ответ 1

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

Оба OP и "этот другой парень", по-видимому, обнаружили, что короткий цикл занимает 11 циклов, а длинный - 9 циклов. Для длинного цикла 9 циклов - это много времени, хотя есть много операций. Для короткого цикла должен быть некоторый ларек, вызванный тем, что он был настолько коротким, и просто добавление nop делает цикл достаточно длинным, чтобы избежать срыва.

Одна вещь, которая возникает, если мы посмотрим на код:

0x00000000004005af <+50>:    addq   $0x1,-0x20(%rbp)
0x00000000004005b4 <+55>:    cmpq   $0x7fffffff,-0x20(%rbp)
0x00000000004005bc <+63>:    jb     0x4005af <main+50>

Мы читаем i и записываем его обратно (addq). Мы снова читаем его и сравниваем (cmpq). А потом мы зацикливаемся. Но цикл использует предсказание ветвей. Поэтому в то время, когда выполняется addq, процессор на самом деле не уверен, что ему разрешено писать на i (поскольку предсказание ветки может быть неправильным).

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

Проблема здесь в том, что условный скачок, addq, который приводит к условному хранилищу, и cmpq, которые не уверены, откуда получить данные, очень близки друг к другу. Они необычайно близки друг к другу. Может быть, они так близко друг к другу, что в этот момент процессор не может понять, взять ли i из инструкции магазина или прочитать его из памяти. И читает это из памяти, которая медленнее, потому что она должна ждать окончания магазина. И добавление только одного nop дает процессору достаточно времени.

Обычно вы думаете, что есть RAM, и есть кеш. На современном процессоре Intel память чтения может считываться с (от самого медленного до самого быстрого):

Память (ОЗУ)
Кэш L3 (необязательно)
Кэш L2
Кэш L1
Предыдущая инструкция магазина, которая еще не написана в кеш-память L1.

То, что процессор делает внутренне в коротком, медленном цикле:

Прочитайте i из кеша L1
Добавить 1 в i
Записать i в кеш L1
Подождите, пока i не будет записано в кеш L1
Прочитайте i из кеша L1
Сравните i с INT_MAX
Отнести к (1), если оно меньше.

В длинном, быстром цикле процессор выполняет:

Много вещей
Прочитайте i из кеша L1
Добавить 1 в i
Сделайте инструкцию "store", которая будет писать i в кеш L1
Прочитайте i непосредственно из инструкции "store", не касаясь кеша L1
Сравните i с INT_MAX
Отнести к (1), если оно меньше.

Ответ 2

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

foo.c:5:5: error: first parameter of 'main' (argument count) must be of type 'int'
int main (char argc, char * argv[]) {
    ^
foo.c:13:26: warning: overflow in expression; result is 2147483647 with type 'int' [-Winteger-overflow]
    for (i = 0; i<(1<<31)-1; i++);
                         ^
foo.c:19:26: warning: overflow in expression; result is 2147483647 with type 'int' [-Winteger-overflow]
    for (i = 0; i<(1<<31)-1; i++) {
                         ^

Попробуем исправить это:

#include <stdint.h>
#include <stdio.h>
#include <time.h>
#include <limits.h>

int main (int argc, char * argv[]) {
    time_t begin, end;
    uint64_t i;
    double total_time, free_time;
    int A = 1;
    int B = 1;

    begin = clock();
    for (i = 0; i<INT_MAX; i++);
    end = clock();
    free_time = (double)(end-begin)/CLOCKS_PER_SEC;
    printf("%f\n", free_time);

    begin = clock();
    for (i = 0; i<INT_MAX; i++) {
        A += B%2;
    }
    end = clock();
    free_time = (double)(end-begin)/CLOCKS_PER_SEC;
    printf("%f\n", free_time);

    return(0);
}

Теперь посмотрим на сборку этого кода. Лично я считаю, что внутренняя сборка LLVM очень читаема, поэтому я собираюсь это показать. Я создам его, выполнив:

clang -O3 foo.c -S -emit-llvm -std=gnu99

Здесь соответствующая часть выхода (основная функция):

define i32 @main(i32 %argc, i8** nocapture readnone %argv) #0 {
  %1 = tail call i64 @"\01_clock"() #3
  %2 = tail call i64 @"\01_clock"() #3
  %3 = sub nsw i64 %2, %1
  %4 = sitofp i64 %3 to double
  %5 = fdiv double %4, 1.000000e+06
  %6 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i64 0, i64 0), double %5) #3
  %7 = tail call i64 @"\01_clock"() #3
  %8 = tail call i64 @"\01_clock"() #3
  %9 = sub nsw i64 %8, %7
  %10 = sitofp i64 %9 to double
  %11 = fdiv double %10, 1.000000e+06
  %12 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i64 0, i64 0), double %11) #3
  ret i32 0
}

Обратите внимание, что между вызовами clock() для любого случая существуют операции нет. Таким образом, они оба скомпилированы для точно такой же.

Ответ 3

Этот ответ предполагает, что вы уже поняли и рассмотрели отличные моменты в отношении undefined поведения sharth делает в его ответ. Он также указывает на трюки, которые компилятор может воспроизвести на вашем коде. Вы должны предпринять шаги, чтобы убедиться, что компилятор не распознает весь цикл как бесполезный. Например, изменение объявления итератора на volatile uint64_t i; предотвратит удаление цикла, а volatile int A; гарантирует, что второй цикл фактически будет работать больше, чем первый. Но даже если вы все это сделаете, вы все равно можете обнаружить, что:

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

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

Что еще более важно, у вас есть процессор i5, который имеет динамический такт. Когда ваша программа начнет выполнение, тактовая частота, скорее всего, будет низкой, потому что процессор простаивает. Просто запуск программы заставляет процессор больше не работать, поэтому после небольшой задержки тактовая частота будет увеличиваться. Соотношение между частотой вращения на холостом ходу и частотой TurboBoosted CPU может быть значительным. (На моем ультрабуке Haswell i5-4200U прежний множитель равен 8, а второй - 26, что делает код запуска менее 30% так же быстро, как и более поздний код! "Калиброванные" петли для реализации задержек - ужасная идея на современных компьютерах! )

Включая фазу прогрева (повторение теста и отбрасывание первого результата) для более точного времени не только для управляемых фреймворков с JIT-компиляторами!

Ответ 4

Я могу воспроизвести это с помощью GCC 4.8.2-19ubuntu1 без оптимизации:

$ ./a.out 
4.780179
3.762356

Вот пустой цикл:

0x00000000004005af <+50>:    addq   $0x1,-0x20(%rbp)
0x00000000004005b4 <+55>:    cmpq   $0x7fffffff,-0x20(%rbp)
0x00000000004005bc <+63>:    jb     0x4005af <main+50>

И здесь непустой:

0x000000000040061a <+157>:   mov    -0x24(%rbp),%eax
0x000000000040061d <+160>:   cltd   
0x000000000040061e <+161>:   shr    $0x1f,%edx
0x0000000000400621 <+164>:   add    %edx,%eax
0x0000000000400623 <+166>:   and    $0x1,%eax
0x0000000000400626 <+169>:   sub    %edx,%eax
0x0000000000400628 <+171>:   add    %eax,-0x28(%rbp)
0x000000000040062b <+174>:   addq   $0x1,-0x20(%rbp)
0x0000000000400630 <+179>:   cmpq   $0x7fffffff,-0x20(%rbp)
0x0000000000400638 <+187>:   jb     0x40061a <main+157>

Вставьте a nop в пустой цикл:

0x00000000004005af <+50>:    nop
0x00000000004005b0 <+51>:    addq   $0x1,-0x20(%rbp)
0x00000000004005b5 <+56>:    cmpq   $0x7fffffff,-0x20(%rbp)
0x00000000004005bd <+64>:    jb     0x4005af <main+50>

Теперь они работают одинаково быстро:

$ ./a.out 
3.846031
3.705035

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