Почему GCC генерирует код на 15-20% быстрее, если я оптимизирую размер вместо скорости?

Я впервые заметил в 2009 году, что GCC (по крайней мере, в моих проектах и ​​на моих машинах) имеет тенденцию генерировать заметно более быстрый код, если я оптимизирую для size ( -Os) вместо скорости ( -O2или -O3), и с тех пор я удивляюсь, почему.

Мне удалось создать (довольно глупый) код, который демонстрирует это удивительное поведение и достаточно мал, чтобы быть размещенным здесь.

const int LOOP_BOUND = 200000000;

__attribute__((noinline))
static int add(const int& x, const int& y) {
    return x + y;
}

__attribute__((noinline))
static int work(int xval, int yval) {
    int sum(0);
    for (int i=0; i<LOOP_BOUND; ++i) {
        int x(xval+sum);
        int y(yval+sum);
        int z = add(x, y);
        sum += z;
    }
    return sum;
}

int main(int , char* argv[]) {
    int result = work(*argv[1], *argv[2]);
    return result;
}

Если я скомпилирую его -Os, выполнение этой программы займет 0,38 с и 0,44 с, если она скомпилирована с помощью -O2или -O3. Эти времена получены последовательно и практически без помех (gcc 4.7.2, x86_64 GNU / Linux, Intel Core i5-3320M).

(Обновление: я переместил весь ассемблерный код на GitHub : они сделали публикацию раздутой и, по-видимому, добавили очень мало значения к вопросам, поскольку fno-align-*флаги имеют тот же эффект.)

Вот сгенерированная сборка с -Osи -O2.

К сожалению, мое понимание сборки очень ограничено, так что я понятия не имею ли то , что я делал дальше , было правильно: я схватил сборку для -O2и объединить все свои различия в сборку за -Os исключением тех .p2alignлиний, результат здесь . Этот код по-прежнему работает в 0.38 с, и единственное отличие состоит в .p2align материале.

Если я правильно угадал, это отступы для выравнивания стека. Согласно Почему GCC pad работает с NOP? это сделано в надежде, что код будет работать быстрее, но, очевидно, эта оптимизация не принесла результатов в моем случае.

В этом случае виновником является прокладка? Почему и как?

Шум, который он издает, делает невозможным микро-оптимизацию синхронизации.

Как я могу убедиться, что такие случайные удачные / неудачные выравнивания не мешают, когда я выполняю микрооптимизации (не связанные с выравниванием по стеку) в исходном коде C или C ++?

ОБНОВИТЬ:

После ответа Паскаля Куока я немного повозился с выравниванием. Переходя -O2 -fno-align-functions -fno-align-loopsк gcc, все .p2alignуходит из сборки, и сгенерированный исполняемый файл запускается за 0.38 с. Согласно документации gcc :

-Os включает все оптимизации -O2 [но] -Os отключает следующие флаги оптимизации:

  -falign-functions  -falign-jumps  -falign-loops
  -falign-labels  -freorder-blocks  -freorder-blocks-and-partition
  -fprefetch-loop-arrays

Таким образом, это в значительной степени похоже на (неправильную) проблему выравнивания.

Я все еще скептически отношусь к тому, -march=nativeчто было предложено в ответе Марата Духана . Я не уверен, что это не только мешает этой (неправильной) проблеме выравнивания; это абсолютно не влияет на мою машину. (Тем не менее, я проголосовал за его ответ.)

ОБНОВЛЕНИЕ 2:

Мы можем взять -Osиз картины. Следующие времена получены путем компиляции с

• -O2 -fno-omit-frame-pointer 0.37s

• -O2 -fno-align-functions -fno-align-loops 0.37s

• -S -O2затем вручную перемещая сборку add()через work()0,37 с

• -O2 0.44s

Похоже, для меня add()большое значение имеет расстояние от сайта вызова. Я пытался perf, но вывод perf statи perf reportимеет очень мало смысла для меня. Тем не менее, я мог получить только один последовательный результат из этого:

-O2:

 602,312,864 stalled-cycles-frontend   #    0.00% frontend cycles idle
       3,318 cache-misses
 0.432703993 seconds time elapsed
 [...]
 81.23%  a.out  a.out              [.] work(int, int)
 18.50%  a.out  a.out              [.] add(int const&, int const&) [clone .isra.0]
 [...]
       ¦   __attribute__((noinline))
       ¦   static int add(const int& x, const int& y) {
       ¦       return x + y;
100.00 ¦     lea    (%rdi,%rsi,1),%eax
       ¦   }
       ¦   ? retq
[...]
       ¦            int z = add(x, y);
  1.93 ¦    ? callq  add(int const&, int const&) [clone .isra.0]
       ¦            sum += z;
 79.79 ¦      add    %eax,%ebx

Для fno-align-*:

 604,072,552 stalled-cycles-frontend   #    0.00% frontend cycles idle
       9,508 cache-misses
 0.375681928 seconds time elapsed
 [...]
 82.58%  a.out  a.out              [.] work(int, int)
 16.83%  a.out  a.out              [.] add(int const&, int const&) [clone .isra.0]
 [...]
       ¦   __attribute__((noinline))
       ¦   static int add(const int& x, const int& y) {
       ¦       return x + y;
 51.59 ¦     lea    (%rdi,%rsi,1),%eax
       ¦   }
[...]
       ¦    __attribute__((noinline))
       ¦    static int work(int xval, int yval) {
       ¦        int sum(0);
       ¦        for (int i=0; i<LOOP_BOUND; ++i) {
       ¦            int x(xval+sum);
  8.20 ¦      lea    0x0(%r13,%rbx,1),%edi
       ¦            int y(yval+sum);
       ¦            int z = add(x, y);
 35.34 ¦    ? callq  add(int const&, int const&) [clone .isra.0]
       ¦            sum += z;
 39.48 ¦      add    %eax,%ebx
       ¦    }

Для -fno-omit-frame-pointer:

 404,625,639 stalled-cycles-frontend   #    0.00% frontend cycles idle
      10,514 cache-misses
 0.375445137 seconds time elapsed
 [...]
 75.35%  a.out  a.out              [.] add(int const&, int const&) [clone .isra.0]                                                                                     ¦
 24.46%  a.out  a.out              [.] work(int, int)
 [...]
       ¦   __attribute__((noinline))
       ¦   static int add(const int& x, const int& y) {
 18.67 ¦     push   %rbp
       ¦       return x + y;
 18.49 ¦     lea    (%rdi,%rsi,1),%eax
       ¦   const int LOOP_BOUND = 200000000;
       ¦
       ¦   __attribute__((noinline))
       ¦   static int add(const int& x, const int& y) {
       ¦     mov    %rsp,%rbp
       ¦       return x + y;
       ¦   }
 12.71 ¦     pop    %rbp
       ¦   ? retq
 [...]
       ¦            int z = add(x, y);
       ¦    ? callq  add(int const&, int const&) [clone .isra.0]
       ¦            sum += z;
 29.83 ¦      add    %eax,%ebx

Похоже, мы остановились на вызове add()в медленном случае.

Я изучил все, что perf -eможет выплюнуть на моей машине; не только статистика, которая приведена выше.

Для того же исполняемого файла stalled-cycles-frontendпоказана линейная корреляция со временем выполнения; Я не заметил ничего другого, что так четко соотносилось бы. (Сравнение stalled-cycles-frontendдля разных исполняемых файлов не имеет смысла для меня.)

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

По умолчанию компиляторы оптимизируют для «среднего» процессора. Поскольку разные процессоры предпочитают разные последовательности команд, включенная оптимизация компилятора -O2может принести пользу среднему процессору, но снизить производительность вашего конкретного процессора (и то же самое относится к -Os). Если вы попробуете один и тот же пример на разных процессорах, вы обнаружите, что на некоторых из них выгода, в -O2то время как другие более благоприятны для -Osоптимизации.

Вот результаты для time ./test 0 0нескольких процессоров (время пользователя сообщается):

Processor (System-on-Chip)             Compiler   Time (-O2)  Time (-Os)  Fastest
AMD Opteron 8350                       gcc-4.8.1    0.704s      0.896s      -O2
AMD FX-6300                            gcc-4.8.1    0.392s      0.340s      -Os
AMD E2-1800                            gcc-4.7.2    0.740s      0.832s      -O2
Intel Xeon E5405                       gcc-4.8.1    0.603s      0.804s      -O2
Intel Xeon E5-2603                     gcc-4.4.7    1.121s      1.122s       -
Intel Core i3-3217U                    gcc-4.6.4    0.709s      0.709s       -
Intel Core i3-3217U                    gcc-4.7.3    0.708s      0.822s      -O2
Intel Core i3-3217U                    gcc-4.8.1    0.708s      0.944s      -O2
Intel Core i7-4770K                    gcc-4.8.1    0.296s      0.288s      -Os
Intel Atom 330                         gcc-4.8.1    2.003s      2.007s      -O2
ARM 1176JZF-S (Broadcom BCM2835)       gcc-4.6.3    3.470s      3.480s      -O2
ARM Cortex-A8 (TI OMAP DM3730)         gcc-4.6.3    2.727s      2.727s       -
ARM Cortex-A9 (TI OMAP 4460)           gcc-4.6.3    1.648s      1.648s       -
ARM Cortex-A9 (Samsung Exynos 4412)    gcc-4.6.3    1.250s      1.250s       -
ARM Cortex-A15 (Samsung Exynos 5250)   gcc-4.7.2    0.700s      0.700s       -
Qualcomm Snapdragon APQ8060A           gcc-4.8       1.53s       1.52s      -Os

В некоторых случаях вы можете смягчить эффект невыгодных оптимизаций, попросив gccвыполнить оптимизацию для вашего конкретного процессора (используя опции -mtune=nativeили -march=native):

Processor            Compiler   Time (-O2 -mtune=native) Time (-Os -mtune=native)
AMD FX-6300          gcc-4.8.1         0.340s                   0.340s
AMD E2-1800          gcc-4.7.2         0.740s                   0.832s
Intel Xeon E5405     gcc-4.8.1         0.603s                   0.803s
Intel Core i7-4770K  gcc-4.8.1         0.296s                   0.288s

Обновление: в Core i3 на базе Ivy Bridge три версии gcc( 4.6.4, 4.7.3и 4.8.1) производят двоичные файлы со значительно отличающейся производительностью, но код сборки имеет лишь незначительные различия. Пока у меня нет объяснения этому факту.

Сборка из gcc-4.6.4 -Os(выполняется за 0,709 с):

00000000004004d2 <_ZL3addRKiS0_.isra.0>:
  4004d2:       8d 04 37                lea    eax,[rdi+rsi*1]
  4004d5:       c3                      ret

00000000004004d6 <_ZL4workii>:
  4004d6:       41 55                   push   r13
  4004d8:       41 89 fd                mov    r13d,edi
  4004db:       41 54                   push   r12
  4004dd:       41 89 f4                mov    r12d,esi
  4004e0:       55                      push   rbp
  4004e1:       bd 00 c2 eb 0b          mov    ebp,0xbebc200
  4004e6:       53                      push   rbx
  4004e7:       31 db                   xor    ebx,ebx
  4004e9:       41 8d 34 1c             lea    esi,[r12+rbx*1]
  4004ed:       41 8d 7c 1d 00          lea    edi,[r13+rbx*1+0x0]
  4004f2:       e8 db ff ff ff          call   4004d2 <_ZL3addRKiS0_.isra.0>
  4004f7:       01 c3                   add    ebx,eax
  4004f9:       ff cd                   dec    ebp
  4004fb:       75 ec                   jne    4004e9 <_ZL4workii+0x13>
  4004fd:       89 d8                   mov    eax,ebx
  4004ff:       5b                      pop    rbx
  400500:       5d                      pop    rbp
  400501:       41 5c                   pop    r12
  400503:       41 5d                   pop    r13
  400505:       c3                      ret

Сборка из gcc-4.7.3 -Os(выполняется за 0,822 секунды):

00000000004004fa <_ZL3addRKiS0_.isra.0>:
  4004fa:       8d 04 37                lea    eax,[rdi+rsi*1]
  4004fd:       c3                      ret

00000000004004fe <_ZL4workii>:
  4004fe:       41 55                   push   r13
  400500:       41 89 f5                mov    r13d,esi
  400503:       41 54                   push   r12
  400505:       41 89 fc                mov    r12d,edi
  400508:       55                      push   rbp
  400509:       bd 00 c2 eb 0b          mov    ebp,0xbebc200
  40050e:       53                      push   rbx
  40050f:       31 db                   xor    ebx,ebx
  400511:       41 8d 74 1d 00          lea    esi,[r13+rbx*1+0x0]
  400516:       41 8d 3c 1c             lea    edi,[r12+rbx*1]
  40051a:       e8 db ff ff ff          call   4004fa <_ZL3addRKiS0_.isra.0>
  40051f:       01 c3                   add    ebx,eax
  400521:       ff cd                   dec    ebp
  400523:       75 ec                   jne    400511 <_ZL4workii+0x13>
  400525:       89 d8                   mov    eax,ebx
  400527:       5b                      pop    rbx
  400528:       5d                      pop    rbp
  400529:       41 5c                   pop    r12
  40052b:       41 5d                   pop    r13
  40052d:       c3                      ret

Сборка из gcc-4.8.1 -Os(выполняется за 0,994 секунды):

00000000004004fd <_ZL3addRKiS0_.isra.0>:
  4004fd:       8d 04 37                lea    eax,[rdi+rsi*1]
  400500:       c3                      ret

0000000000400501 <_ZL4workii>:
  400501:       41 55                   push   r13
  400503:       41 89 f5                mov    r13d,esi
  400506:       41 54                   push   r12
  400508:       41 89 fc                mov    r12d,edi
  40050b:       55                      push   rbp
  40050c:       bd 00 c2 eb 0b          mov    ebp,0xbebc200
  400511:       53                      push   rbx
  400512:       31 db                   xor    ebx,ebx
  400514:       41 8d 74 1d 00          lea    esi,[r13+rbx*1+0x0]
  400519:       41 8d 3c 1c             lea    edi,[r12+rbx*1]
  40051d:       e8 db ff ff ff          call   4004fd <_ZL3addRKiS0_.isra.0>
  400522:       01 c3                   add    ebx,eax
  400524:       ff cd                   dec    ebp
  400526:       75 ec                   jne    400514 <_ZL4workii+0x13>
  400528:       89 d8                   mov    eax,ebx
  40052a:       5b                      pop    rbx
  40052b:       5d                      pop    rbp
  40052c:       41 5c                   pop    r12
  40052e:       41 5d                   pop    r13
  400530:       c3                      ret

Мой коллега помог мне найти правдоподобный ответ на мой вопрос. Он заметил важность 256-байтовой границы. Он не зарегистрирован здесь и призвал меня опубликовать ответ сам (и принять всю известность).

Короткий ответ:

В этом случае виновником является прокладка? Почему и как?

Все сводится к выравниванию. Выравнивания могут оказать значительное влияние на производительность, поэтому -falign-*флаги у нас на первом месте.

Я отправил (фальшивый?) Отчет об ошибке разработчикам gcc . Оказывается, что поведение по умолчанию - «мы выравниваем циклы по 8 байт по умолчанию, но стараемся выровнять его по 16 байтам, если нам не нужно заполнять более 10 байтов».Видимо, этот дефолт не лучший выбор в данном конкретном случае и на моей машине. Clang 3.4 (trunk) -O3делает соответствующее выравнивание, и сгенерированный код не показывает это странное поведение.

Конечно, если неправильное выравнивание сделано, это ухудшает ситуацию. Ненужное / плохое выравнивание просто съедает байты без причины и потенциально увеличивает количество кешей и т. Д.

Шум, который он издает, делает невозможным микро-оптимизацию синхронизации.

Как я могу убедиться, что такие случайные удачные / неудачные выравнивания не мешают, когда я выполняю микрооптимизации (не связанные с выравниванием по стеку) в исходных кодах C или C ++?

Просто указав gcc сделать правильное выравнивание:

g++ -O2 -falign-functions=16 -falign-loops=16

Длинный ответ:

Код будет работать медленнее, если:

• Н. XXбайтовые граничные разрезы add()в середине (XX будучи машиннозависимый).

• если вызов add()должен перепрыгнуть черезXX границу байта и цель не выровнена.

• если add() не выровнен.

• если цикл не выровнен.

Первые 2 прекрасно видны на кодах и результатах, которые любезно разместил Марат Духан . В этом случае gcc-4.8.1 -Os(выполняется за 0,994 секунды):

00000000004004fd <_ZL3addRKiS0_.isra.0>:
  4004fd:       8d 04 37                lea    eax,[rdi+rsi*1]
  400500:       c3   

граница 256 байт режет add()прямо посередине и ниadd() цикл, ни цикл не выровнены. Сюрприз, сюрприз, это самый медленный случай!

В случае gcc-4.7.3 -Os(выполняется за 0,822 секунды), граница в 256 байт только врезается в холодную секцию (но не в цикл и не add()обрезается):

00000000004004fa <_ZL3addRKiS0_.isra.0>:
  4004fa:       8d 04 37                lea    eax,[rdi+rsi*1]
  4004fd:       c3                      ret

[...]

  40051a:       e8 db ff ff ff          call   4004fa <_ZL3addRKiS0_.isra.0>

Ничто не выравнивается, и призыв к add() должен перепрыгнуть через 256-байтовую границу. Этот код является вторым самым медленным.

В случае gcc-4.6.4 -Os(выполняется за 0,709 с), хотя ничего не выровнено, вызову add()не нужно перепрыгивать через 256-байтовую границу, а цель находится ровно в 32 байтах:

  4004f2:       e8 db ff ff ff          call   4004d2 <_ZL3addRKiS0_.isra.0>
  4004f7:       01 c3                   add    ebx,eax
  4004f9:       ff cd                   dec    ebp
  4004fb:       75 ec                   jne    4004e9 <_ZL4workii+0x13>

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

Теперь на моей машине я не получаю этот 256-байтовый граничный эффект. На моей машине включается только функция и выравнивание петель. Если я прохожу, g++ -O2 -falign-functions=16 -falign-loops=16то все возвращается на круги своя: я всегда получаю самый быстрый случай, и время больше не зависит от -fno-omit-frame-pointerфлага. Я могу передать g++ -O2 -falign-functions=32 -falign-loops=32или любое число, кратное 16, код также не чувствителен к этому.

Я впервые заметил в 2009 году, что gcc (по крайней мере, в моих проектах и ​​на моих машинах) имеет тенденцию генерировать заметно более быстрый код, если я оптимизирую по размеру (-Os) вместо скорости (-O2 или -O3), и мне было интересно с тех пор почему.

Вероятное объяснение состоит в том, что у меня были горячие точки, которые были чувствительны к выравниванию, как в этом примере. Перемешав с флагами (передавая -Osвместо -O2), эти горячие точки были случайно выровнены, и код стал быстрее. Это не имело ничего общего с оптимизацией по размеру: это было случайно, что горячие точки были выровнены лучше. С этого момента я буду проверять влияние выравнивания на мои проекты.

Да, и еще одна вещь. Как могут возникать такие горячие точки, как показано в примере? Как может встраиваться такая крошечная функция, как add()сбой?

Учти это:

// add.cpp
int add(const int& x, const int& y) {
    return x + y;
}

и в отдельном файле:

// main.cpp
int add(const int& x, const int& y);

const int LOOP_BOUND = 200000000;

__attribute__((noinline))
static int work(int xval, int yval) {
    int sum(0);
    for (int i=0; i<LOOP_BOUND; ++i) {
        int x(xval+sum);
        int y(yval+sum);
        int z = add(x, y);
        sum += z;
    }
    return sum;
}

int main(int , char* argv[]) {
    int result = work(*argv[1], *argv[2]);
    return result;
}

и скомпилирован как: g++ -O2 add.cpp main.cpp.

      GCC не будет встроен add()!

Вот и все, это так просто непреднамеренно создать горячие точки, как в OP. Конечно, это отчасти моя вина: gcc - отличный компилятор. Если скомпилировать вышеизложенное как:, g++ -O2 -flto add.cpp main.cppто есть, если я выполняю оптимизацию времени соединения, код выполняется за 0,19 с!

(В OP искусственно отключено встраивание, следовательно, код в OP был в 2 раза медленнее).

Я добавляю этот пост-акцепт, чтобы указать, что влияние выравнивания на общую производительность программ, в том числе больших, было изучено. Например, эта статья (и я полагаю, что эта версия также появилась в CACM) показывает, как одного лишь изменения порядка ссылок и размера среды ОС было достаточно для значительного смещения производительности. Они связывают это с выравниванием «горячих петель».

Эта статья под названием "Создание неправильных данных без каких-либо действий, которые явно не соответствуют действительности!" говорит, что непреднамеренный экспериментальный уклон из-за почти неконтролируемых различий в средах выполнения программ, вероятно, делает бессмысленными многие результаты тестов.

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

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

Я думаю, что вы можете получить тот же результат, что и вы:

Я взял сборку для -O2 и объединил все ее отличия в сборку для -Os, за исключением строк .p2align:

... используя -O2 -falign-functions=1 -falign-jumps=1 -falign-loops=1 -falign-labels=1. Я собирал все с этими опциями, которые были быстрее, чем обычные, -O2каждый раз, когда я пытался измерить, в течение 15 лет.

Кроме того, для совершенно другого контекста (включая другой компилятор) я заметил, что ситуация похожа : опция, которая должна «оптимизировать размер кода, а не скорость», оптимизирует размер кода и скорость.

Если я правильно угадал, это отступы для выравнивания стека.

Нет, это не имеет никакого отношения к стеку, NOP, которые генерируются по умолчанию, и что опции -falign - * = 1 предотвращают это для выравнивания кода.

Согласно Почему GCC pad работает с NOP? это сделано в надежде, что код будет работать быстрее, но, очевидно, эта оптимизация не принесла результатов в моем случае.

В этом случае виновником является прокладка? Почему и как?

Весьма вероятно, что обивка является виновником. Причина того, что заполнение считается необходимым, и в некоторых случаях полезно, заключается в том, что код обычно выбирается в строках по 16 байтов (подробности см. В ресурсах оптимизации Agner Fog , которые зависят от модели процессора). Выравнивание функции, цикла или метки на 16-байтовой границе означает, что шансы статистически увеличиваться, что для размещения функции или цикла потребуется меньше строк. Очевидно, что это приводит к обратным последствиям, поскольку эти NOP уменьшают плотность кода и, следовательно, эффективность кэширования. В случае циклов и метки, NOP может даже потребоваться выполнить один раз (когда выполнение поступает в цикл / метку нормально, в отличие от перехода).

Если ваша программа ограничена кешем CODE L1, то оптимизация по размеру внезапно начинает приносить плоды.

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

В вашем случае -O3, вероятно, генерирует код, достаточный для двух строк кэша, но -Os помещается в одну строку кэша.

Я ни в коем случае не эксперт в этой области, но я помню, что современные процессоры довольно чувствительны, когда дело доходит до предсказания ветвлений . Алгоритмы, используемые для предсказания ветвей, (или, по крайней мере, были в те времена, когда я писал код на ассемблере) основывались на нескольких свойствах кода, включая расстояние до цели и направление.

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

Тем не менее, я понятия не имею, как это проверить, и я просто хотел, чтобы вы знали, что это может быть то, что вы хотите посмотреть.