c++ - El indicador de optimización de gcc-O3 hace que el código sea más lento que-O2

optimization

Question

Encuentro este tema ¿Por qué es más rápido procesar una matriz ordenada que una matriz sin clasificar? . E intente ejecutar este código. Y encuentro un comportamiento extraño. Si compilo este código con el indicador de optimización 2.98605 sec se tarda 2.98605 sec en ejecutarse. Si compilo con -O2 tarda 1.98093 sec . Intento ejecutar este código varias veces (5 o 6) en la misma máquina en el mismo entorno, cierro el resto del software (Chrome, Skype, etc.).

gcc --version
gcc (Ubuntu 4.9.2-0ubuntu1~14.04) 4.9.2
Copyright (C) 2014 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Entonces, por favor, ¿puedes explicarme por qué sucede esto? Leo el manual de gcc y veo que -O2 incluye -O2 . Gracias por ayudar.

PS agregar código

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

Answer 1

gcc -O3 usa un cmov para el condicional, por lo que alarga la cadena de dependencia transportada en bucle para incluir un cmov (que es 2 uops y 2 ciclos de latencia en su CPU Intel Sandybridge, de acuerdo con las tablas de instrucciones de Agner Fog . Consulte también el x86 etiqueta wiki). Este es uno de los casos donde cmov apesta .

Si los datos cmov incluso moderadamente impredecibles, cmov probablemente sería una victoria, por lo que esta es una elección bastante sensata para un compilador. (Sin embargo, los compiladores a veces pueden usar demasiado código sin ramificación ).

Puse su código en el explorador del compilador Godbolt para ver el asm (con un bonito resaltado y filtrado de líneas irrelevantes. Sin embargo, todavía tiene que desplazarse hacia abajo más allá de todo el código de clasificación para llegar a main ()).

.L82:  # the inner loop from gcc -O3
    movsx   rcx, DWORD PTR [rdx]  # sign-extending load of data[c]
    mov     rsi, rcx
    add     rcx, rbx        # rcx = sum+data[c]
    cmp     esi, 127
    cmovg   rbx, rcx        # sum = data[c]>127 ? rcx : sum
    add     rdx, 4          # pointer-increment
    cmp     r12, rdx
    jne     .L82

gcc podría haber guardado el MOV usando LEA en lugar de ADD.

Los cuellos de botella del bucle en la latencia de ADD-> CMOV (3 ciclos), ya que una iteración del bucle escribe rbx con CMO, y la siguiente iteración lee rbx con ADD.

El bucle solo contiene 8 uops de dominio fusionado, por lo que puede emitirse a uno por cada 2 ciclos. La presión del puerto de ejecución tampoco es un cuello de botella tan malo como la latencia de la cadena sum dep, pero está cerca (Sandybridge solo tiene 3 puertos ALU, a diferencia de los 4 de Haswell).

Por cierto, escribirlo como sum += (data[c] >= 128 ? data[c] : 0); sacar el cmov de la cadena dep transportada en bucle es potencialmente útil. Todavía hay muchas instrucciones, pero el cmov en cada iteración es independiente. Esto se compila como se esperaba en gcc6.3 -O2 y anteriores , pero gcc7 se optimiza en un cmov en la ruta crítica ( https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82666 ). (También se vectoriza automáticamente con versiones anteriores de gcc que la forma if() de escribirlo).

Clang saca el cmov de la ruta crítica incluso con la fuente original.

gcc -O2 usa una rama (para gcc5.xy anteriores), que predice bien porque sus datos están ordenados. Dado que las CPU modernas utilizan la predicción de ramificación para manejar las dependencias de control, la cadena de dependencia transportada en bucle es más corta: solo un add (latencia de 1 ciclo).

La comparación y la ramificación en cada iteración es independiente, gracias a la predicción de ramificación + ejecución especulativa, que permite que la ejecución continúe antes de que se sepa con certeza la dirección de la ramificación.

.L83:   # The inner loop from gcc -O2
    movsx   rcx, DWORD PTR [rdx]  # load with sign-extension from int32 to int64
    cmp     ecx, 127
    jle     .L82        # conditional-jump over the next instruction 
    add     rbp, rcx    # sum+=data[c]
.L82:
    add     rdx, 4
    cmp     rbx, rdx
    jne     .L83

Hay dos cadenas de dependencia transportadas en bucle: sum y el contador de bucles. sum es de 0 o 1 ciclo de largo, y el contador de bucle siempre es de 1 ciclo de largo. Sin embargo, el bucle es de 5 uops de dominio fusionado en Sandybridge, por lo que no puede ejecutarse a 1c por iteración de todos modos, por lo que la latencia no es un cuello de botella.

Probablemente se ejecuta en aproximadamente una iteración por 2 ciclos (cuello de botella en el rendimiento de la instrucción de bifurcación), frente a uno por cada 3 ciclos para el bucle -O3. El siguiente cuello de botella sería el rendimiento de ALU uop: 4 ALU uops (en el caso no tomado) pero solo 3 puertos ALU. (ADD puede ejecutarse en cualquier puerto).

Esta predicción de análisis de canalización coincide casi exactamente con sus tiempos de ~ 3 segundos para -O3 frente a ~ 2 segundos para -O2.

Haswell / Skylake podría ejecutar el caso no tomado a uno por 1.25 ciclos, ya que puede ejecutar una rama no tomada en el mismo ciclo que una rama tomada y tiene 4 puertos ALU. (O un poco menos, ya que un ciclo de 5 uop no se emite a las 4 uops en cada ciclo ).

(Recién probado: Skylake @ 3.9GHz ejecuta la versión ramificada de todo el programa en 1.45s, o la versión sin ramificación en 1.68s. Por lo tanto, la diferencia es mucho menor allí).

g ++ 6.3.1 usa cmov incluso en -O2 , pero g ++ 5.4 todavía se comporta como 4.9.2.

Con g ++ 6.3.1 y g ++ 5.4, el uso de -fprofile-generate / -fprofile-use produce la versión ramificada incluso en -O3 (con -fno-tree-vectorize ).

La versión CMOV del bucle de los nuevos gcc usa add ecx,-128 / cmovge rbx,rdx lugar de CMP / CMOV. Eso es un poco extraño, pero probablemente no lo desacelere. ADD escribe un registro de salida, así como banderas, por lo que crea más presión sobre el número de registros físicos. Pero mientras no sea un cuello de botella, debería ser casi igual.

El nuevo gcc auto-vectoriza el ciclo con -O3, que es una aceleración significativa incluso con solo SSE2. (p. ej., mi i7-6700k Skylake ejecuta la versión vectorizada en 0.74s, aproximadamente el doble de rápido que el escalar. O -O3 -march=native en 0.35s, usando vectores AVX2 256b).

La versión vectorizada parece muchas instrucciones, pero no está tan mal, y la mayoría de ellas no son parte de una cadena de dep. Solo tiene que descomprimir en elementos de 64 bits cerca del final. Sin embargo, hace pcmpgtd dos veces, porque no se da cuenta de que podría simplemente extender a cero en lugar de extender a signo cuando la condición ya ha puesto a cero todos los enteros negativos.