Un salto costoso con GCC 5.4.0

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 no generar más.

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 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 casos donde la evaluación de las condiciones es un proceso costoso. Por ejemplo:

if ((DoLengthyCheck1(p) && (DoLengthyCheck2(p))

Si DoLengthyCheck1falla, no tiene sentido llamar 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 ifdeclaración 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 ( cmpinstrucciones) aquí, cada una seguida de un salto / rama condicional por separado ( jao 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 cola de captación previa extremadamente pequeña [comparable a una caché de instrucciones], combinada con la falta total de predicción de ramificación, significaban que las ramificaciones tomadas requerían que la caché se volcara ) 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,Su 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 contrario a la intuición que esto podría ser más rápido, ya que hay más instrucciones aquí, pero así es como a veces funciona la optimización. cmpAquí se ven las mismas comparaciones ( ), pero ahora, cada una está precedida por una xory seguida de una setbe. El XOR es solo un truco estándar para borrar un registro. Esta setbees 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í, setbees 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 se jaramificó si la comparación fue superior. Una vez que estos dos valores se han obtenido en el r15byr14bregistros, 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 está multiplicando dos valores de tamaño de byte.

También podría haber reemplazado la multiplicación con el operador AND ( &) bit a 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 para emitir el código de esta manera, pero por alguna razón, sus heurísticas internas le dicen que es más rápido. Que sería probablemente será más rápido si el predictor de saltos fue de su lado, pero es probable que sea más lento si la predicción de saltos falla con más frecuencia que lo consigue.

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 &&expresiones al mismo código que se habría emitido si lo 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 ( jgy setle) en lugar de condiciones no firmadas ( jay 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 setCCinstrucción para generar código sin ramificación para la segunda condición, pero se ha vuelto mucho más eficiente en la forma en que aumenta . En lugar de hacer una segunda comparación redundante para establecer los indicadores para una sbboperación, utiliza el conocimiento que r14dserá 1 o 0 para simplemente agregar incondicionalmente este valor nontopOverlap. Si r14des 0, entonces la suma es un no-op; 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 bit a bit :

    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 de 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 prepárese 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 ifdeclaración, 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 de una manera sin sucursales, los resultados intermedios se anded juntos, y luego este resultado (que será ya sea 0 o 1) se added 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 bifurcación 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 falla la predicción de la rama, ejecutar algunas instrucciones adicionales según sea necesario para evitar una rama definitivamente será más rápido que una rama mal predicha. Incluso el compilador más inteligente e inteligente tendrá 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, se sienta con el desmontaje y encuentra formas de ajustarlo. Y, como dije antes, prepárate para revisar esas decisiones cuando actualices a una versión más nueva del compilador, ya que 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!

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 <= iy i < curr.size()son ambos verdaderos
• curr[i] < 479 Es falso
• i + shift < 0o i + shift >= l.size()es verdad

entonces (curr[i] < 479) && (l[i + shift] < 479)se garantiza que la expresión sea ​​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 comportamiento indefinido ; que se permitió a causar un fallo de segmentación.

Esto significa que, por ejemplo, para el fragmento de código original, el compilador no puede simplemente escribir un bucle que realiza ambas comparaciones y realiza una andoperación, a menos que el compilador también pueda probar que l[i + shift]nunca causará una falla por defecto en una situación en la que se requiere que no lo haga.

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) {
    // ...

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 primero el código generado f(x), luego verifica la salida y salta a la evaluación de g(x)cuándo fue 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.

Esto podría 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 realiza 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.