c++ - que - Valores booleanos como 8 bits en compiladores. ¿Las operaciones sobre ellos son ineficientes?
que es booleano en programacion (3)
Estoy leyendo " Optimizing software in C ++ " de Agner Fog (específico para procesadores x86 para Intel, AMD y VIA) y afirma en la página 34
Las variables booleanas se almacenan como enteros de 8 bits con el valor 0 para falso y 1 para verdadero. Las variables booleanas están sobredeterminadas en el sentido de que todos los operadores que tienen variables booleanas como entrada verifican si las entradas tienen cualquier otro valor que 0 o 1, pero los operadores que tienen booleanos como salida no pueden producir ningún otro valor que 0 o 1. Esto hace que las operaciones Las variables booleanas como entrada son menos eficientes de lo necesario.
¿Sigue siendo cierto hoy y en qué compiladores? ¿Puedes dar un ejemplo? El autor declara
Las operaciones booleanas se pueden hacer mucho más eficientes si se sabe con certeza que los operandos no tienen otros valores que 0 y 1. La razón por la cual el compilador no hace tal suposición es que las variables pueden tener otros valores si son sin inicializar o provienen de fuentes desconocidas.
¿Esto significa que si tomo un puntero de función bool(*)() por ejemplo y lo llamo, entonces las operaciones en él producen un código ineficiente? ¿O es el caso cuando accedo a un booleano desreferenciando un puntero o leyendo de una referencia y luego actúo sobre él?
Creo que este no es el caso.
En primer lugar, este razonamiento es completamente inaceptable:
La razón por la cual el compilador no hace tal suposición es que las variables pueden tener otros valores si no están inicializadas o provienen de fuentes desconocidas.
Revisemos algunos códigos (compilados con clang 6, pero GCC 7 y MSVC 2017 producen un código similar).
Booleano o:
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
Como se puede ver, no hay verificación 0/1 aquí, simple or .
Convierte bool a int:
int fn(bool a) {
return a;
}
0000000000000000 <fn(bool)>:
0: 40 0f b6 c7 movzx eax,dil
4: c3 ret
De nuevo, sin control, movimiento simple.
Convierta char a 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
Aquí, char se verifica si es 0, o no, y el valor de bool se establece en 0 o 1 en consecuencia.
Así que creo que es seguro decir que el compilador usa bool de una manera que siempre contiene un 0/1. Nunca verifica su validez.
Acerca de la eficiencia: creo que bool es óptimo. El único caso que puedo imaginar, donde este enfoque no es óptimo es la conversión char-> bool. Esa operación podría ser un simple mov, si el valor de bool no estuviera restringido a 0/1. Para todas las demás operaciones, el enfoque actual es igualmente bueno o mejor.
EDITAR: Peter Cordes mencionó ABI. Aquí está el texto relevante del System V ABI para AMD64 (el texto para i386 es similar):
Los booleanos, cuando se almacenan en un objeto de memoria, se almacenan como objetos de un solo byte cuyo valor siempre es 0 (falso) o 1 (verdadero) . Cuando se almacenan en registros enteros (excepto para pasar como argumentos), los 8 bytes del registro son significativos; cualquier valor distinto de cero se considera verdadero
Entonces, para las plataformas que siguen a SysV ABI, podemos estar seguros de que un bool tiene un valor 0/1.
Busqué un documento ABI para MSVC, pero lamentablemente no encontré nada sobre bool .
Recopilé lo siguiente con clang ++ -O3 -S
bool andbool(bool a, bool b)
{
return a && b;
}
bool andint(int a, int b)
{
return a && b;
}
El archivo .s contiene:
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
Claramente, es la versión bool que está haciendo menos.
TL: DR : los compiladores actuales todavía tienen bool -optimizaciones cuando hacen cosas como
(a&&b) ? x : y (a&&b) ? x : y . Pero la razón por la cual no es que no asuman 0/1, simplemente apestan por esto.
Muchos usos de bool son para locales, o funciones en línea, por lo que booleanizing a un 0/1 puede optimizar lejos y rama (o cmov o lo que sea) en la condición original. Solo preocúpese por optimizar las entradas / salidas bool cuando tiene que pasarse / devolverse a través de algo que no está en línea, o realmente almacenado en la memoria.
Posible guía de optimización : combine bool s de fuentes externas (función args / memoria) con operadores bit a bit, como a&b . MSVC e ICC funcionan mejor con esto. IDK si es peor para los habitantes locales. Tenga en cuenta que a&b es solo equivalente a a&&b para bool , no para tipos enteros. 2 && 1 es verdadero, pero 2 & 1 es 0, que es falso. Bitwise OR no tiene este problema.
IDK si esta guía alguna vez perjudicará a los locales que se establecieron a partir de una comparación dentro de la función (o en algo que está en línea). Por ejemplo, podría llevar al compilador a hacer booleanos enteros en lugar de simplemente usar resultados de comparación directamente cuando sea posible. También tenga en cuenta que no parece ayudar con gcc y clang actuales.
Sí, implementaciones C ++ en x86 store bool en un byte que siempre es 0 o 1 (al menos a través de los límites de llamadas a funciones donde el compilador debe respetar la convención ABI / calling que requiere esto).
Los compiladores a veces se aprovechan de esto, por ejemplo, para bool -> int conversion incluso gcc 4.4 simplemente zero-extends a 32-bit ( movzx eax, dil ). Clang y MSVC hacen esto también. Las reglas C y C ++ requieren que esta conversión produzca 0 o 1, por lo que este comportamiento solo es seguro si siempre es seguro suponer que una función bool arg o una variable global tiene un valor 0 o 1.
Incluso los compiladores antiguos normalmente lo aprovecharon para bool -> int , pero no en otros casos. Por lo tanto, Agner está equivocado sobre el motivo cuando dice:
La razón por la cual el compilador no hace tal suposición es que las variables pueden tener otros valores si no están inicializadas o provienen de fuentes desconocidas.
MSVC CL19 sí crea un código que asume que los bool función bool son 0 o 1, por lo tanto, Windows x86-64 ABI debe garantizar esto.
En el sistema x86-64 System V ABI (utilizado por todo lo que no sea Windows), el registro de cambios para la revisión 0.98 dice "Especifique que _Bool (también conocido como bool ) es booleanizado en la persona que llama". Creo que incluso antes de ese cambio, los compiladores lo estaban asumiendo, pero esto solo documenta en qué estaban confiando los compiladores. El lenguaje actual en el x86-64 SysV ABI es:
3.1.2 Representación de datos
Los booleanos, cuando se almacenan en un objeto de memoria, se almacenan como objetos de un solo byte cuyo valor siempre es 0 (falso) o 1 (verdadero). Cuando se almacenan en registros enteros (excepto para pasar como argumentos), los 8 bytes del registro son significativos; cualquier valor distinto de cero se considera verdadero.
La segunda frase es absurda: el ABI no tiene sentido decirle a los compiladores cómo almacenar cosas en registros dentro de una función, solo en los límites entre diferentes unidades de compilación (args de memoria / función y valores devueltos). Informé este defecto de ABI hace un tiempo en la página de github donde se mantiene .
3.2.3 Paso de parámetros :
Cuando se devuelve o pasa un valor de tipo
_Boolen un registro o en la pila, el bit 0 contiene el valor de verdad y los bits 1 a 7 deben ser cero 16 .(nota al pie 16): otros bits quedan sin especificar, por lo tanto, el lado del consumidor de esos valores puede confiar en que es 0 o 1 cuando se trunca a 8 bits.
El lenguaje en el i386 System V ABI es el mismo, IIRC.
Cualquier compilador que asume 0/1 por una cosa (por ejemplo, conversión a int ) pero no puede aprovecharlo en otros casos tiene una optimización perdida . Lamentablemente, estas optimizaciones perdidas todavía existen, aunque son más raras que cuando Agner escribió ese párrafo sobre compiladores siempre con booleanización.
(Source + asm en el explorador del compilador Godbolt para gcc4.6 / 4.7, y clang / MSVC. Consulte también la charla de CppCon2017 de Matt Godbolt ¿Qué ha hecho mi compilador últimamente? Desbloqueo de la tapa del compilador )
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
Así que incluso gcc4.6 no re-booleanize b , pero sí pasó por alto la optimización que hace gcc4.7: (y clang y compiladores posteriores como se muestra en otras respuestas):
# gcc4.7 -O3 to present: looks ideal to me.
mov eax, esi
or eax, edi
ret
(Clang or dil, sil / mov eax, edi es tonto: se garantiza que causará un bloqueo parcial en Nehalem o Intel anterior al leer edi después de escribir dil , y tiene un tamaño de código peor al necesitar un prefijo REX para usar el bajo -8 parte de edi. Una mejor opción podría ser or dil,sil / movzx eax, dil si quiere evitar leer cualquier registro de 32 bits en caso de que su interlocutor haya dejado algunos registros de paso de arg con registros parciales "sucios").
MSVC emite este código que comprueba a a luego b separado, no aprovecha al máximo nada , e incluso usa xor al,al lugar de xor eax,eax . Por lo tanto, tiene una dependencia falsa en el valor anterior de eax en la mayoría de las CPU ( incluyendo Haswell / Skylake, que no cambian el nombre de las reglas parciales bajas 8 por separado de todo el registro, solo AH / BH / ... ). Esto es tonto. La única razón para usar xor al,al es cuando explícitamente desea conservar los bytes superiores.
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 tampoco aprovecha la naturaleza 0/1 conocida de las entradas, simplemente usa una instrucción or para establecer indicadores de acuerdo con el OR bit a bit de las dos entradas, y setcc para producir un 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 emite el mismo código incluso para bool bitwise_or(bool a, bool b) { return a|b; } bool bitwise_or(bool a, bool b) { return a|b; } . Promueve a int (con movzx ), y usa or para establecer flags de acuerdo con la OR bit a bit. Esto es tonto en comparación con or dil,sil / setne al .
Para bitwise_or , bitwise_or solo usa una instrucción or (después de movzx en cada entrada), pero de todos modos no re-booleanize.
Optimizaciones perdidas en gcc / clang actual:
Solo ICC / MSVC creaba un código tonto con la simple función anterior, pero esta función aún genera problemas de gcc y clang:
int select(bool a, bool b, int x, int y) {
return (a&&b) ? x : y;
}
Source + asm en el explorador del compilador Godbolt (Misma fuente, diferentes compiladores seleccionados en comparación con la última vez).
Parece bastante simple; uno esperaría que un compilador inteligente lo hiciera sin cmov con una test / cmov . La instrucción de test de x86 establece banderas de acuerdo con un AND a nivel de bit. Es una instrucción AND que en realidad no escribe el destino. (Al igual que cmp es un sub que no escribe el destino).
# 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
Pero incluso las compilaciones diarias de gcc y clang en el explorador del compilador Godbolt hacen un código mucho más complicado, verificando cada booleano por separado. Saben cómo optimizar bool ab = a&&b; si devuelve ab , pero incluso escribiéndolo de esa manera (con una variable booleana separada para contener el resultado) no logra mantenerlos a mano para crear un código que no succione.
Tenga en cuenta que test same,same es exactamente equivalente a cmp reg, 0 , y es más pequeño, por lo que es lo que usan los compiladores.
La versión de Clang es estrictamente peor que mi versión manuscrita. (Tenga en cuenta que requiere que la persona que llama amplíe cero los bool args a 32 bits, como lo hace para los tipos enteros estrechos como una parte no oficial de la ABI que implementan y gcc pero de la que depende solamente el 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 hace código de raya para esto, similar a lo que hacen las versiones anteriores de 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 hace un código ramificado muy similar. Está dirigido a la convención de llamadas de Windows, donde los números enteros están en 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 también hace código ramificado, pero con ambas instrucciones mov después de las ramas.
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
Tratando de ayudar al compilador usando
int select2(bool a, bool b, int x, int y) {
bool ab = a&&b;
return (ab) ? x : y;
}
lleva a MSVC a hacer un código hilarantemente malo :
;; 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
Esto es solo con MSVC (y ICC18 tiene la misma optimización perdida de test / cmov en un registro que acaba de establecerse en una constante).
gcc y clang como siempre no hacen que el código sea tan malo como MSVC; hacen el mismo asm que hacen para select() , que aún no es bueno, pero al menos intentar ayudarlos no lo empeora con MSVC.
Combinar bool con operadores bit a bit ayuda a MSVC e ICC
En mi prueba muy limitada, | y parecen funcionar mejor que || y && para MSVC e ICC. Mire la salida del compilador para su propio código con su compilador + opciones de compilación para ver qué pasa.
int select_bitand(bool a, bool b, int x, int y) {
return (a&b) ? x : y;
}
Gcc aún se bifurca por separado en test separadas de las dos entradas, el mismo código que las otras versiones de select . clang todavía hace dos test/cmov , el mismo asm que para las otras versiones de origen.
MSVC viene y se optimiza correctamente, superando a todos los demás compiladores (al menos en la definición independiente):
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 desperdicia dos instrucciones movzx extendiendo cero los bool a int , pero luego hace el mismo código que 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