Логические значения как 8-битные в компиляторах. Операции на них неэффективны?
Я читаю " Оптимизацию программного обеспечения в C++" Агнера Фога (специально для процессоров x86 для Intel, AMD и VIA), и это говорится на странице 34
Булевы переменные хранятся в виде 8-битных целых чисел со значением 0 для false и 1 для true. Булевы переменные переопределяются в том смысле, что все операторы, которые имеют булевы переменные в качестве входных данных, проверяют, имеют ли входы любое другое значение, кроме 0 или 1, но операторы, которые имеют логические переменные в качестве выходных данных, не могут давать никакого другого значения, кроме 0 или 1. Это делает операции Булевы переменные в качестве входных данных менее эффективны, чем необходимо.
Это все еще верно сегодня и на каких компиляторах? Можете ли вы привести пример? Автор заявляет
Логические операции можно сделать намного более эффективными, если с уверенностью известно, что у операндов нет других значений, кроме 0 и 1. Причина, по которой компилятор не делает такое предположение, состоит в том, что переменные могут иметь другие значения, если они неинициализированы или приходят из неизвестных источников.
Означает ли это, что если я возьму указатель на функцию bool(*)() например, и назовите это, тогда операции над ним производят неэффективный код? Или это тот случай, когда я получаю доступ к логическому значению путем разыменования указателя или чтения из ссылки, а затем работаю с ней?
3 ответа
TL: DR: текущие компиляторы все еще имеют bool Пропущенные оптимизации при выполнении таких вещей, как (a&&b) ? x : y, Но причина не в том, что они не принимают 0/1, они просто сосут.
Многие использования bool для локальных или встроенных функций, так что 0 / 1 можно оптимизировать и разветвить (или CMOV или что-то) на исходное состояние. Беспокоиться только об оптимизации bool входы / выходы, когда они должны быть переданы / возвращены через что-то, что не встроено или действительно сохранено в памяти.
Возможные рекомендации по оптимизации: объединить bool s из внешних источников (функция args / memory) с побитовыми операторами, такими как a&b, MSVC и ICC справляются с этим лучше. ИДК, если это будет еще хуже для местных bool s. Остерегайтесь этого a&b только эквивалентно a&&b за bool, а не целочисленные типы. 2 && 1 верно, но 2 & 1 0, что неверно. Побитовое ИЛИ не имеет этой проблемы.
IDK, если это руководство будет когда-либо вредить местным жителям, которые были установлены из сравнения внутри функции (или в чем-то, что встроено). Например, это может привести к тому, что компилятор на самом деле сделает целочисленные логические значения, а не просто использует результаты сравнения напрямую, когда это возможно. Также обратите внимание, что это не помогает с текущими gcc и clang.
Да, реализации C++ в x86 store bool в байте это всегда 0 или 1 (по крайней мере, через границы вызова функции, где компилятор должен соблюдать соглашение ABI / вызова, которое требует этого.)
Компиляторы иногда пользуются этим, например, для bool -> int преобразование даже в gcc 4.4 просто ноль расширяется до 32 бит (movzx eax, dil). Clang и MSVC тоже делают это. Правила C и C++ требуют, чтобы это преобразование производило 0 или 1, поэтому такое поведение безопасно только в том случае, если всегда можно предположить, что bool Функция arg или глобальная переменная имеет значение 0 или 1.
Даже старые компиляторы обычно использовали это для bool -> int, но не в других случаях. Таким образом, Агнер ошибается в отношении причины, когда он говорит:
Причина, по которой компилятор не делает такого предположения, заключается в том, что переменные могут иметь другие значения, если они неинициализированы или получены из неизвестных источников.
MSVC CL19 делает код, который предполагает bool Аргументы функции равны 0 или 1, поэтому ABI Windows x86-64 должен это гарантировать.
В x86-64 System V ABI (используется всем, кроме Windows), в журнале изменений для версии 0.98 написано "Укажите, что _Bool (ака bool) - это логическое выражение для вызывающей стороны. "Я думаю, что даже до этого изменения компиляторы предполагали это, но это только документирует, на что уже полагались компиляторы. Текущий язык в x86-64 SysV ABI:
3.1.2 Представление данных
Логические значения, когда они хранятся в объекте памяти, хранятся как однобайтовые объекты, значение которых всегда равно 0 (ложь) или 1 (истина). При хранении в целочисленных регистрах (за исключением передачи в качестве аргументов) все 8 байтов регистра имеют значение; любое ненулевое значение считается истинным.
Второе предложение бессмысленно: у ABI нет бизнес-компиляторов, говорящих о том, как хранить вещи в регистрах внутри функции, только на границах между различными блоками компиляции (аргументы памяти / функции и возвращаемые значения). Я сообщил об этом дефекте ABI некоторое время назад на странице github, где он поддерживается.
3.2.3 Передача параметров:
Когда значение типа
_Boolвозвращается или передается в регистре или в стеке, бит 0 содержит значение истинности, а биты с 1 по 7 должны быть равны нулю 16.(сноска 16): Остальные биты остаются неуказанными, поэтому потребительская сторона этих значений может полагаться на то, что они равны 0 или 1 при усечении до 8 бит.
Язык в i386 System V ABI такой же, IIRC.
Любой компилятор, который принимает 0/1 для одной вещи (например, преобразование в int) но не может воспользоваться этим, в других случаях пропущена оптимизация. К сожалению, такие пропущенные оптимизации все еще существуют, хотя они встречаются реже, чем когда Агнер писал, что параграф о компиляторах всегда перебулеванизируется.
(Source + asm в проводнике компилятора Godbolt для gcc4.6 / 4.7 и clang/MSVC. См. Также доклад Мэтта Годболта CppCon2017 " Что мой компилятор сделал для меня за последнее время? Снятие крышки компилятора")
bool logical_or(bool a, bool b) { return a||b; }
# gcc4.6.4 -O3 for the x86-64 System V ABI
test dil, dil # test a against itself (for non-zero)
mov eax, 1
cmove eax, esi # return a ? 1 : b;
ret
Таким образом, даже gcc4.6 не переустанавливал b, но он пропустил оптимизацию, которую выполняет gcc4.7: (и компиляторы clang и более поздние, как показано в других ответах):
# gcc4.7 -O3 to present: looks ideal to me.
mov eax, esi
or eax, edi
ret
(Clang-х or dil, sil / mov eax, edi глупо: при чтении гарантированно будет происходить частичная регистрация на Nehalem или более ранней версии Intel edi после написания dil и он имеет худший размер кода из-за необходимости использования префикса REX для использования младшей части edi. Лучший выбор может быть or dil,sil / movzx eax, dil если вы хотите избежать чтения каких-либо 32-битных регистров на случай, если вызывающая сторона оставила некоторые регистры передачи аргументов с "грязными" частичными регистрами.)
MSVC испускает этот код, который проверяет a затем b отдельно, совершенно не в состоянии воспользоваться чем-либо, и даже используя xor al,al вместо xor eax,eax, Таким образом, он имеет ложную зависимость от старого значения eax на большинстве процессоров ( включая Haswell/Skylake, которые не переименовывают частичные регистры с низким уровнем 8 отдельно от всего регистра, только AH / BH /...). Это просто глупо. Единственная причина когда-либо использовать xor al,al это когда вы явно хотите сохранить старшие байты.
logical_or PROC ; x86-64 MSVC CL19
test cl, cl ; Windows ABI passes args in ecx, edx
jne SHORT $LN3@logical_or
test dl, dl
jne SHORT $LN3@logical_or
xor al, al ; missed peephole: xor eax,eax is strictly better
ret 0
$LN3@logical_or:
mov al, 1
ret 0
logical_or ENDP
ICC18 также не использует известную природу входов 0/1, он просто использует or инструкция для установки флагов в соответствии с побитовым ИЛИ двух входов, и setcc производить 0/1.
logical_or(bool, bool): # ICC18
xor eax, eax #4.42
movzx edi, dil #4.33
movzx esi, sil #4.33
or edi, esi #4.42
setne al #4.42
ret #4.42
ICC испускает тот же код даже для bool bitwise_or(bool a, bool b) { return a|b; }, Это способствует int (с movzx) и использует or установить флаги в соответствии с побитовым ИЛИ. Это глупо по сравнению с or dil,sil / setne al,
За bitwise_or MSVC просто использует or инструкция (после movzx на каждом входе), но в любом случае не переустанавливает.
Пропущенные оптимизации в текущем gcc/clang:
Только ICC/MSVC делали тупой код с помощью простой функции, описанной выше, но эта функция по-прежнему создает проблемы с gcc и clang:
int select(bool a, bool b, int x, int y) {
return (a&&b) ? x : y;
}
Source + asm в проводнике компилятора Godbolt (тот же источник, разные компиляторы, выбранные по сравнению с прошлым разом).
Выглядит достаточно просто; вы бы надеялись, что умный компилятор сделает это без единого test / cmov, x86-х test инструкция устанавливает флаги в соответствии с побитовым И. Это инструкция AND, которая на самом деле не записывает пункт назначения. (Как cmp это sub это не пишет пункт назначения).
# hand-written implementation that no compilers come close to making
select:
mov eax, edx # retval = x
test edi, esi # ZF = ((a & b) == 0)
cmovz eax, ecx # conditional move: return y if ZF is set
ret
Но даже ежедневные сборки gcc и clang в проводнике компилятора Godbolt создают гораздо более сложный код, проверяя каждый логический тип отдельно. Они знают, как оптимизировать bool ab = a&&b; если ты вернешься ab, но даже написав его таким образом (с отдельной логической переменной для хранения результата) не удается удержать их вручную для создания кода, который не сосет.
Обратите внимание, что test same,same в точности эквивалентно cmp reg, 0 и меньше, так что это то, что используют компиляторы.
Версия Кланга строго хуже моей рукописной версии. (Обратите внимание, что это требует, чтобы вызывающий bool args to 32-bit, как это делается для узких целочисленных типов, как неофициальная часть ABI, которую он и gcc реализуют, но зависит только от clang).
select: # clang 6.0 trunk 317877 nightly build on Godbolt
test esi, esi
cmove edx, ecx # x = b ? y : x
test edi, edi
cmove edx, ecx # x = a ? y : x
mov eax, edx # return x
ret
gcc 8.0.0 20171110 nightly создает для этого ветвистый код, аналогично тому, что делают старые версии gcc.
select(bool, bool, int, int): # gcc 8.0.0-pre 20171110
test dil, dil
mov eax, edx ; compiling with -mtune=intel or -mtune=haswell would keep test/jcc together for macro-fusion.
je .L8
test sil, sil
je .L8
rep ret
.L8:
mov eax, ecx
ret
MSVC x86-64 CL19 делает очень похожий ветвистый код. Он нацелен на соглашение о вызовах Windows, где целочисленные аргументы находятся в rcx, rdx, r8, r9.
select PROC
test cl, cl ; a
je SHORT $LN3@select
mov eax, r8d ; retval = x
test dl, dl ; b
jne SHORT $LN4@select
$LN3@select:
mov eax, r9d ; retval = y
$LN4@select:
ret 0 ; 0 means rsp += 0 after popping the return address, not C return 0.
; MSVC doesn't emit the `ret imm16` opcode here, so IDK why they put an explicit 0 as an operand.
select ENDP
ICC18 также делает ветвистый код, но с обоими mov инструкции после веток.
select(bool, bool, int, int):
test dil, dil #8.13
je ..B4.4 # Prob 50% #8.13
test sil, sil #8.16
jne ..B4.5 # Prob 50% #8.16
..B4.4: # Preds ..B4.2 ..B4.1
mov edx, ecx #8.13
..B4.5: # Preds ..B4.2 ..B4.4
mov eax, edx #8.13
ret #8.13
Попытка помочь компилятору с помощью
int select2(bool a, bool b, int x, int y) {
bool ab = a&&b;
return (ab) ? x : y;
}
приводит MSVC к созданию смешно плохого кода:
;; MSVC CL19 -Ox = full optimization
select2 PROC
test cl, cl
je SHORT $LN3@select2
test dl, dl
je SHORT $LN3@select2
mov al, 1 ; ab = 1
test al, al ;; and then test/cmov on an immediate constant!!!
cmovne r9d, r8d
mov eax, r9d
ret 0
$LN3@select2:
xor al, al ;; ab = 0
test al, al ;; and then test/cmov on another path with known-constant condition.
cmovne r9d, r8d
mov eax, r9d
ret 0
select2 ENDP
Это только с MSVC (и ICC18 имеет ту же пропущенную оптимизацию test/cmov для регистра, который был только что установлен на константу).
gcc и clang, как обычно, не делают код настолько плохим, как MSVC; они делают то же самое, что и для select() что все еще не хорошо, но, по крайней мере, попытка помочь им не усугубляет ситуацию, как в MSVC.
скомбинировать bool с побитовыми операторами помогает MSVC и ICC
В моем очень ограниченном тестировании, | а также & кажется, работает лучше, чем || а также && для MSVC и ICC. Посмотрите на вывод компилятора для вашего собственного кода с опциями компилятор + компиляция, чтобы увидеть, что происходит.
int select_bitand(bool a, bool b, int x, int y) {
return (a&b) ? x : y;
}
Gcc еще разветвляется отдельно на отдельные test s из двух входов, тот же код, что и другие версии select, Clang по-прежнему делает два отдельных test/cmov То же, что и для других версий исходного кода.
MSVC проходит и оптимизирует правильно, опережая все другие компиляторы (по крайней мере, в автономном определении):
select_bitand PROC ;; MSVC
test cl, dl ;; ZF = !(a & b)
cmovne r9d, r8d
mov eax, r9d ;; could have done the mov to eax in parallel with the test, off the critical path, but close enough.
ret 0
ICC18 тратит впустую два movzx инструкции ноль расширения bool с int, но затем делает тот же код, что и MSVC
select_bitand: ## ICC18
movzx edi, dil #16.49
movzx esi, sil #16.49
test edi, esi #17.15
cmovne ecx, edx #17.15
mov eax, ecx #17.15
ret #17.15
Я думаю, что это не так.
Прежде всего, это рассуждение совершенно неприемлемо:
Причина, по которой компилятор не делает такого предположения, заключается в том, что переменные могут иметь другие значения, если они неинициализированы или получены из неизвестных источников.
Давайте проверим некоторый код (скомпилированный с помощью clang 6, но GCC 7 и MSVC 2017 производят похожий код).
Логическое или:
bool fn(bool a, bool b) {
return a||b;
}
0000000000000000 <fn(bool, bool)>:
0: 40 08 f7 or dil,sil
3: 40 88 f8 mov al,dil
6: c3 ret
Как видно, здесь нет проверки 0/1, просто or,
Преобразовать bool в int:
int fn(bool a) {
return a;
}
0000000000000000 <fn(bool)>:
0: 40 0f b6 c7 movzx eax,dil
4: c3 ret
Опять не чек, простой ход.
Конвертировать char в bool:
bool fn(char a) {
return a;
}
0000000000000000 <fn(char)>:
0: 40 84 ff test dil,dil
3: 0f 95 c0 setne al
6: c3 ret
Здесь char проверяется, является ли он 0 или нет, и значение bool устанавливается равным 0 или 1 соответственно.
Поэтому я думаю, что можно с уверенностью сказать, что компилятор использует bool таким образом, чтобы он всегда содержал 0/1. Он никогда не проверяет его действительность.
Об эффективности: я думаю, что bool является оптимальным. Единственный случай, который я могу себе представить, где этот подход не является оптимальным, это преобразование char->bool. Эта операция может быть простым mov, если значение bool не будет ограничено 0/1. Для всех других операций текущий подход одинаково хорош или лучше.
РЕДАКТИРОВАТЬ: Питер Кордес упомянул ABI. Вот соответствующий текст из System V ABI для AMD64 (текст для i386 аналогичен):
Логические значения, когда они хранятся в объекте памяти, хранятся как однобайтовые объекты, значение которых всегда равно 0 (ложь) или 1 (истина). При хранении в целочисленных регистрах (за исключением передачи в качестве аргументов) все 8 байтов регистра имеют значение; любое ненулевое значение считается истинным
Таким образом, для платформ, которые следуют SysV ABI, мы можем быть уверены, что bool имеет значение 0/1.
Я искал документ ABI для MSVC, но, к сожалению, я ничего не нашел о bool,
Я скомпилировал следующее с помощью clang++ -O3 -S
bool andbool(bool a, bool b)
{
return a && b;
}
bool andint(int a, int b)
{
return a && b;
}
.s файл содержит:
andbool(bool, bool): # @andbool(bool, bool)
andb %sil, %dil
movl %edi, %eax
retq
andint(int, int): # @andint(int, int)
testl %edi, %edi
setne %cl
testl %esi, %esi
setne %al
andb %cl, %al
retq
Очевидно, что версия bool делает меньше.