Почему GCC генерирует код на 15-20% быстрее, если я оптимизирую размер вместо скорости?
Я впервые заметил в 2009 году, что GCC (по крайней мере, в моих проектах и на моих машинах) имеет тенденцию генерировать заметно более быстрый код, если я оптимизирую по размеру (-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 <br/> -falign-labels -freorder-blocks -freorder-blocks-and-partition <br/> -fprefetch-loop-arrays <br/>
Таким образом, это в значительной степени похоже на (неправильную) проблему выравнивания.
Я все еще скептически отношусь к -march=native как предложено в ответе Марата Духана. Я не уверен, что это не только мешает этой (неправильной) проблеме выравнивания; это абсолютно не влияет на мою машину. (Тем не менее, я проголосовал за его ответ.)
ОБНОВЛЕНИЕ 2:
Мы можем взять -Os из картины. Следующие времена получены путем компиляции с
-O2 -fno-omit-frame-pointer0.37s-O2 -fno-align-functions -fno-align-loops0.37s-S -O2затем вручную перемещая сборкуadd()послеwork()0.37s-O20.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 а не только те, которые приведены выше. Промахи в кеше очень шумные и практически не коррелируют со временем выполнения.
6 ответов
Мой коллега помог мне найти правдоподобный ответ на мой вопрос. Он заметил важность 256-байтовой границы. Он не зарегистрирован здесь и призвал меня опубликовать ответ сам (и принять всю известность).
Короткий ответ:
В этом случае виновником является прокладка? Почему и как?
Все сводится к выравниванию. Выравнивания могут оказать значительное влияние на производительность, поэтому у нас есть -falign-* флаги на первом месте.
Я отправил (фальшивый?) Отчет об ошибке разработчикам gcc. Оказывается, что поведение по умолчанию - "мы выравниваем циклы по 8 байт по умолчанию, но стараемся выровнять его по 16 байтам, если нам не нужно заполнять более 10 байтов". Видимо, этот дефолт не лучший выбор в данном конкретном случае и на моей машине. Лязг 3,4 (багажник) с -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 раза медленнее).
По умолчанию компиляторы оптимизируют для "среднего" процессора. Поскольку разные процессоры предпочитают разные последовательности команд, оптимизация компилятора включена -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
Обновление: на Ivy Bridge на базе Core i3 три версии 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
Я добавляю этот пост-акцепт, чтобы указать, что влияние выравнивания на общую производительность программ, в том числе больших, было изучено. Например, эта статья (и я полагаю, что эта версия также появилась в 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 в сгенерированном коде или когда положение обоих слегка меняется.
Тем не менее, я понятия не имею, как это проверить, и я просто хотел, чтобы вы знали, что это может быть то, что вы хотите посмотреть.