studio - visual c++ online
Un salto costoso con GCC 5.4.0 (4)
Tenía una función que se veía así (mostrando solo la parte importante):
double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY) {
...
for(std::size_t i=std::max(0,-shift);i<max;i++) {
if ((curr[i] < 479) && (l[i + shift] < 479)) {
nontopOverlap++;
}
...
}
...
}
Escrito así, la función tomó ~ 34 ms en mi máquina. Después de cambiar la condición a la multiplicación bool (haciendo que el código se vea así):
double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY) {
...
for(std::size_t i=std::max(0,-shift);i<max;i++) {
if ((curr[i] < 479) * (l[i + shift] < 479)) {
nontopOverlap++;
}
...
}
...
}
El tiempo de ejecución disminuyó a ~ 19ms.
El compilador utilizado fue GCC 5.4.0 con -O3 y después de verificar el código asm generado usando godbolt.org descubrí que el primer ejemplo genera un salto, mientras que el segundo no. Decidí probar GCC 6.2.0, que también genera una instrucción de salto al usar el primer ejemplo, pero GCC 7 parece que ya no genera una.
Descubrir esta forma de acelerar el código fue bastante horrible y tomó bastante tiempo. ¿Por qué el compilador se comporta de esta manera? ¿Está destinado y es algo que los programadores deben tener en cuenta? ¿Hay más cosas similares a esto?
EDITAR: enlace a godbolt https://godbolt.org/g/5lKPF3
El operador
&&
implementa la evaluación de cortocircuito.
Esto significa que el segundo operando solo se evalúa si el primero se evalúa como
true
.
Esto ciertamente resulta en un salto en ese caso.
Puede crear un pequeño ejemplo para mostrar esto:
#include <iostream>
bool f(int);
bool g(int);
void test(int x, int y)
{
if ( f(x) && g(x) )
{
std::cout << "ok";
}
}
La salida del ensamblador se puede encontrar aquí .
Puede ver que el código generado primero llama a
f(x)
, luego verifica la salida y salta a la evaluación de
g(x)
cuando esto era
true
.
De lo contrario, deja la función.
El uso de la multiplicación "booleana" obliga a la evaluación de ambos operandos cada vez y, por lo tanto, no necesita un salto.
Dependiendo de los datos, el salto puede causar una desaceleración porque perturba la tubería de la CPU y otras cosas como la ejecución especulativa. Normalmente, la predicción de ramificación ayuda, pero si sus datos son aleatorios, no hay mucho que pueda predecirse.
El operador lógico AND (
&&
) utiliza la evaluación de cortocircuito, lo que significa que la segunda prueba solo se realiza si la primera comparación se evalúa como verdadera.
Esto es a menudo exactamente la semántica que necesita.
Por ejemplo, considere el siguiente código:
if ((p != nullptr) && (p->first > 0))
Debe asegurarse de que el puntero no sea nulo antes de desreferenciarlo. Si esto no fuera una evaluación de cortocircuito, tendría un comportamiento indefinido porque estaría desreferenciando un puntero nulo.
También es posible que la evaluación de cortocircuito produzca una ganancia de rendimiento en los casos en que la evaluación de las condiciones sea un proceso costoso. Por ejemplo:
if ((DoLengthyCheck1(p) && (DoLengthyCheck2(p))
Si
DoLengthyCheck1
falla, no tiene sentido llamar a
DoLengthyCheck2
.
Sin embargo, en el binario resultante, una operación de cortocircuito a menudo da como resultado dos ramas, ya que esta es la forma más fácil para que el compilador conserve esta semántica.
(Es por eso que, en el otro lado de la moneda, la evaluación de cortocircuito a veces puede
inhibir el
potencial de optimización). Puede ver esto mirando la parte relevante del código objeto generado para su declaración
if
por GCC 5.4:
movzx r13d, WORD PTR [rbp+rcx*2]
movzx eax, WORD PTR [rbx+rcx*2]
cmp r13w, 478 ; (curr[i] < 479)
ja .L5
cmp ax, 478 ; (l[i + shift] < 479)
ja .L5
add r8d, 1 ; nontopOverlap++
Puede ver aquí las dos comparaciones (instrucciones
cmp
) aquí, cada una seguida de un salto / rama condicional por separado (
ja
, o salto si está arriba).
Es una regla general que las ramas son lentas y, por lo tanto, deben evitarse en bucles estrechos. Esto ha sido cierto en prácticamente todos los procesadores x86, desde el humilde 8088 (cuyos tiempos de recuperación lentos y una cola de captura previa extremadamente pequeña [comparable a un caché de instrucciones], combinado con la falta total de predicción de ramificación, significaba que las ramificaciones tomadas requerían que se volcara el caché ) a implementaciones modernas (cuyas largas canalizaciones hacen que las ramas erróneas sean igualmente caras). Tenga en cuenta la pequeña advertencia que me metí allí. Los procesadores modernos desde el Pentium Pro tienen motores de predicción de sucursales avanzados que están diseñados para minimizar el costo de las sucursales. Si la dirección de la rama se puede predecir adecuadamente, el costo es mínimo. La mayoría de las veces, esto funciona bien, pero si te encuentras en casos patológicos en los que el predictor de rama no está de tu lado, tu código puede ser extremadamente lento . Presumiblemente, aquí es donde se encuentra aquí, ya que dice que su matriz no está ordenada.
Usted dice que los puntos de referencia confirmaron que reemplazar el
&&
con un
*
hace que el código sea notablemente más rápido.
La razón de esto es evidente cuando comparamos la porción relevante del código objeto:
movzx r13d, WORD PTR [rbp+rcx*2]
movzx eax, WORD PTR [rbx+rcx*2]
xor r15d, r15d ; (curr[i] < 479)
cmp r13w, 478
setbe r15b
xor r14d, r14d ; (l[i + shift] < 479)
cmp ax, 478
setbe r14b
imul r14d, r15d ; meld results of the two comparisons
cmp r14d, 1 ; nontopOverlap++
sbb r8d, -1
Es un poco contra-intuitivo que esto podría ser más rápido, ya que hay
más
instrucciones aquí, pero así es como funciona la optimización a veces.
Ves las mismas comparaciones (
cmp
) que se están haciendo aquí, pero ahora, cada una está precedida por un
xor
y seguido por un
setbe
.
El XOR es solo un truco estándar para borrar un registro.
El
setbe
es una instrucción x86 que establece un bit en función del valor de un indicador, y a menudo se usa para implementar código sin ramificación.
Aquí,
setbe
es el inverso de
ja
.
Establece su registro de destino en 1 si la comparación fue inferior o igual (dado que el registro se puso a cero previamente, de lo contrario será 0), mientras que
ja
ramificó si la comparación fue superior.
Una vez que estos dos valores se han obtenido en los
r15b
y
r14b
, se multiplican usando
imul
.
La multiplicación era tradicionalmente una operación relativamente lenta, pero es muy rápida en los procesadores modernos, y esto será especialmente rápido, ya que solo multiplica dos valores de dos bytes.
Con la misma facilidad, podría haber reemplazado la multiplicación con el operador AND a nivel de bit (
&
), que no realiza una evaluación de cortocircuito.
Esto hace que el código sea mucho más claro y es un patrón que los compiladores generalmente reconocen.
Pero cuando hace esto con su código y lo compila con GCC 5.4, continúa emitiendo la primera rama:
movzx r13d, WORD PTR [rbp+rcx*2]
movzx eax, WORD PTR [rbx+rcx*2]
cmp r13w, 478 ; (curr[i] < 479)
ja .L4
cmp ax, 478 ; (l[i + shift] < 479)
setbe r14b
cmp r14d, 1 ; nontopOverlap++
sbb r8d, -1
No hay ninguna razón técnica por la que tuviera que emitir el código de esta manera, pero por alguna razón, sus heurísticas internas le dicen que es más rápido. Probablemente sería más rápido si el predictor de rama estuviera de su lado, pero probablemente será más lento si la predicción de rama falla más de lo que tiene éxito.
Las generaciones más nuevas del compilador (y otros compiladores, como Clang) conocen esta regla, y a veces la usarán para generar el mismo código que hubieras buscado optimizando a mano.
Regularmente veo que Clang traduce las expresiones
&&
al mismo código que se habría emitido si hubiera usado
&
.
La siguiente es la salida relevante de GCC 6.2 con su código usando el operador
&&
normal:
movzx r13d, WORD PTR [rbp+rcx*2]
movzx eax, WORD PTR [rbx+rcx*2]
cmp r13d, 478 ; (curr[i] < 479)
jg .L7
xor r14d, r14d ; (l[i + shift] < 479)
cmp eax, 478
setle r14b
add esi, r14d ; nontopOverlap++
¡Tenga en cuenta lo inteligente que es
esto
!
Utiliza condiciones firmadas (
jg
y
setle
) en lugar de condiciones sin firmar (
ja
y
setbe
), pero esto no es importante.
Puede ver que todavía hace la comparación y la ramificación para la primera condición, como la versión anterior, y utiliza la misma instrucción
setCC
para generar código sin ramificación para la segunda condición, pero se ha vuelto mucho más eficiente en cómo funciona incremento.
En lugar de hacer una segunda comparación redundante para establecer los indicadores para una operación
sbb
, utiliza el conocimiento de que
r14d
será 1 o 0 para agregar este valor de manera
nontopOverlap
a
nontopOverlap
.
Si
r14d
es 0, entonces la suma es no
r14d
;
de lo contrario, agrega 1, exactamente como se supone que debe hacer.
GCC 6.2 en realidad produce un código
más
eficiente cuando utiliza el operador de cortocircuito
&&
que el operador bitwise
&
:
movzx r13d, WORD PTR [rbp+rcx*2]
movzx eax, WORD PTR [rbx+rcx*2]
cmp r13d, 478 ; (curr[i] < 479)
jg .L6
cmp eax, 478 ; (l[i + shift] < 479)
setle r14b
cmp r14b, 1 ; nontopOverlap++
sbb esi, -1
La rama y el conjunto condicional todavía están allí, pero ahora vuelve a la forma menos inteligente de incrementar
nontopOverlap
.
¡Esta es una lección importante sobre por qué debes tener cuidado al intentar superar a tu compilador!
Pero si puede probar con puntos de referencia que el código de ramificación es realmente más lento, entonces puede ser útil intentar y superar su compilador. Solo tiene que hacerlo con una inspección cuidadosa del desensamblaje y estar preparado para reevaluar sus decisiones cuando actualice a una versión posterior del compilador. Por ejemplo, el código que tiene podría reescribirse como:
nontopOverlap += ((curr[i] < 479) & (l[i + shift] < 479));
Aquí no hay ninguna declaración
if
, y la gran mayoría de los compiladores nunca pensarán en emitir código de ramificación para esto.
GCC no es una excepción;
Todas las versiones generan algo similar a lo siguiente:
movzx r14d, WORD PTR [rbp+rcx*2]
movzx eax, WORD PTR [rbx+rcx*2]
cmp r14d, 478 ; (curr[i] < 479)
setle r15b
xor r13d, r13d ; (l[i + shift] < 479)
cmp eax, 478
setle r13b
and r13d, r15d ; meld results of the two comparisons
add esi, r13d ; nontopOverlap++
Si ha estado siguiendo los ejemplos anteriores, esto debería serle muy familiar.
Ambas comparaciones se realizan sin ramificaciones, los resultados intermedios se unen y
nontopOverlap
juntos, y luego este resultado (que será 0 o 1) se
add
a
nontopOverlap
.
Si desea un código sin ramificación, esto prácticamente garantizará que lo obtenga.
GCC 7 se ha vuelto aún más inteligente. Ahora genera un código prácticamente idéntico (excepto una ligera reorganización de las instrucciones) para el truco anterior como el código original. Entonces, la respuesta a su pregunta, "¿Por qué el compilador se comporta de esta manera?" , probablemente sea porque no son perfectos! Intentan utilizar la heurística para generar el código más óptimo posible, pero no siempre toman las mejores decisiones. ¡Pero al menos pueden volverse más inteligentes con el tiempo!
Una forma de ver esta situación es que el código de ramificación tiene el mejor rendimiento en el mejor de los casos . Si la predicción de la rama es exitosa, omitir operaciones innecesarias resultará en un tiempo de ejecución un poco más rápido. Sin embargo, el código sin ramificación tiene el mejor rendimiento en el peor de los casos . Si la predicción de bifurcación falla, ejecutar algunas instrucciones adicionales según sea necesario para evitar una bifurcación definitivamente será más rápido que una bifurcación errónea. Incluso los compiladores más inteligentes e inteligentes tendrán dificultades para tomar esta decisión.
Y para su pregunta de si esto es algo a lo que los programadores deben estar atentos, la respuesta es casi seguro que no, excepto en ciertos circuitos que está tratando de acelerar a través de micro optimizaciones. Luego, te sientas con el desmontaje y encuentras formas de ajustarlo. Y, como dije antes, prepárate para revisar esas decisiones cuando actualices a una versión más nueva del compilador, porque puede hacer algo estúpido con tu código complicado, o puede haber cambiado su heurística de optimización lo suficiente como para que puedas retroceder a usar su código original. ¡Comenta a fondo!
Esto puede deberse a que cuando está utilizando el operador lógico
&&
el compilador tiene que verificar dos condiciones para que la instrucción if tenga éxito.
Sin embargo, en el segundo caso, ya que está convirtiendo implícitamente un valor int a bool, el compilador hace algunas suposiciones basadas en los tipos y valores que se pasan, junto con (posiblemente) una sola condición de salto.
También es posible que el compilador optimice completamente los jmps con cambios de bit.
Una cosa importante a tener en cuenta es que
(curr[i] < 479) && (l[i + shift] < 479)
y
(curr[i] < 479) * (l[i + shift] < 479)
no son semánticamente equivalentes! En particular, si alguna vez tiene la situación donde:
-
0 <= iei < curr.size()son ambos verdaderos -
curr[i] < 479es falso -
i + shift < 0oi + shift >= l.size()es verdadero
entonces se garantiza que la expresión
(curr[i] < 479) && (l[i + shift] < 479)
es un valor booleano bien definido.
Por ejemplo, no causa una falla de segmentación.
Sin embargo, en estas circunstancias, la expresión
(curr[i] < 479) * (l[i + shift] < 479)
es
un comportamiento indefinido
;
Se
permite causar una falla de segmentación.
Esto significa que, por ejemplo, para el fragmento de código original, el compilador no puede simplemente escribir un bucle que realice ambas comparaciones y realice una operación, a menos que el compilador también pueda probar que
l[i + shift]
nunca causará una falla por defecto en una situación que se requiere no hacer.
En resumen, el código original ofrece menos oportunidades de optimización que este último. (por supuesto, si el compilador reconoce o no la oportunidad es una pregunta completamente diferente)
Puede arreglar la versión original haciendo
bool t1 = (curr[i] < 479);
bool t2 = (l[i + shift] < 479);
if (t1 && t2) {
// ...