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

Ответ 1

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

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

Является ли это прописью, которая является виновником в этом случае? Почему и как?

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

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

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

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

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

Просто сообщив gcc о правильном выравнивании:

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

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

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

• an 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 (по крайней мере, в моих проектах и ​​на моем машины) имеют тенденцию генерировать значительно более быстрый код, если я оптимизируйте размер (-O) вместо скорости (-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.19s!

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

Ответ 2

По умолчанию компиляторы оптимизируются для "среднего" процессора. Поскольку разные процессоры предпочитают разные последовательности команд, оптимизация компилятора, поддерживаемая -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

Ответ 3

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

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

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

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

Ответ 4

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

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

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

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

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

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

В соответствии с тем, почему функция GCC работает с NOP? это делается в надежде, что код будет работать быстрее, но, по-видимому, эта оптимизация была неудачной в моем случае.

Является ли это прописью, которая является виновником в этом случае? Почему и как?

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

Ответ 5

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

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

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

Ответ 6

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

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

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