c++ - functions - ¿Por qué pow(int, int) es tan lento?

pow c++

Question

He estado trabajando en algunos proyectos de ejercicios de Euler para mejorar mi conocimiento de C ++.

He escrito la siguiente función:

int a = 0,b = 0,c = 0;

for (a = 1; a <= SUMTOTAL; a++)
{
    for (b = a+1; b <= SUMTOTAL-a; b++)
    {
        c = SUMTOTAL-(a+b);

        if (c == sqrt(pow(a,2)+pow(b,2)) && b < c)
        {
            std::cout << "a: " << a << " b: " << b << " c: "<< c << std::endl;
            std::cout << a * b * c << std::endl;
        }
    }
}

Esto se computa en 17 milisegundos.

Sin embargo, si cambio la línea

if (c == sqrt(pow(a,2)+pow(b,2)) && b < c)

a

if (c == sqrt((a*a)+(b*b)) && b < c)

el cálculo tiene lugar en 2 milisegundos. ¿Hay algún detalle de implementación obvio de pow(int, int) que me falta, lo que hace que la primera expresión calcule mucho más despacio?

Answer 1

Has elegido una de las formas más lentas posibles para verificar

c*c == a*a + b*b   // assuming c is non-negative

Eso compila a tres multiplicaciones enteras (una de las cuales se puede sacar del ciclo). Incluso sin pow() , todavía está convirtiendo a double y tomando una raíz cuadrada, lo que es terrible para el rendimiento. (Y también la latencia, pero la predicción de ramas + ejecución especulativa en CPU modernas significa que la latencia no es un factor aquí).

La instrucción SQRTSD de Intel Haswell tiene un rendimiento de uno por 8-14 ciclos ( fuente: tablas de instrucciones de Agner Fog ), por lo que incluso si su versión sqrt() mantiene saturada la unidad de ejecución sqrt FP, sigue siendo 4 veces más lenta que la que obtuve gcc para emitir (abajo).

También puede optimizar la condición de bucle para salir del bucle cuando la parte b < c de la condición se convierte en falsa, por lo que el compilador solo tiene que hacer una versión de esa comprobación.

void foo_optimized()
{ 
  for (int a = 1; a <= SUMTOTAL; a++) {
    for (int b = a+1; b < SUMTOTAL-a-b; b++) {
        // int c = SUMTOTAL-(a+b);   // gcc won''t always transform signed-integer math, so this prevents hoisting (SUMTOTAL-a) :(
        int c = (SUMTOTAL-a) - b;
        // if (b >= c) break;  // just changed the loop condition instead

        // the compiler can hoist a*a out of the loop for us
        if (/* b < c && */ c*c == a*a + b*b) {
            // Just print a newline.  std::endl also flushes, which bloats the asm
            std::cout << "a: " << a << " b: " << b << " c: "<< c << ''/n'';
            std::cout << a * b * c << ''/n'';
        }
    }
  }
}

Esto compila (con gcc6.2 -O3 -O3 -mtune=haswell ) para codificar con este bucle interno. Vea el código completo en el explorador del compilador Godbolt .

# a*a is hoisted out of the loop.  It''s in r15d
.L6:
    add     ebp, 1    # b++
    sub     ebx, 1    # c--
    add     r12d, r14d        # ivtmp.36, ivtmp.43  # not sure what this is or why it''s in the loop, would have to look again at the asm outside
    cmp     ebp, ebx  # b, _39
    jg      .L13    ## This is the loop-exit branch, not-taken until the end
                    ## .L13 is the rest of the outer loop.
                    ##  It sets up for the next entry to this inner loop.
.L8:
    mov     eax, ebp        # multiply a copy of the counters
    mov     edx, ebx
    imul    eax, ebp        # b*b
    imul    edx, ebx        # c*c
    add     eax, r15d       # a*a + b*b
    cmp     edx, eax  # tmp137, tmp139
    jne     .L6
 ## Fall-through into the cout print code when we find a match
 ## extremely rare, so should predict near-perfectly

En Intel Haswell, todas estas instrucciones son de 1 upa cada una. (Y el cmp / jcc empareja el macro fusible en uops de comparación y rama). Así que eso es 10 uops de dominio fusionado, que pueden emitirse en una iteración por cada 2.5 ciclos .

Haswell ejecuta imul r32, r32 con un rendimiento de una iteración por reloj, por lo que las dos multiplicaciones dentro del bucle interno no saturan el puerto 1 en dos multiplicaciones por 2.5c. Esto deja espacio para absorber los conflictos de recursos inevitables de ADD y SUB robar el puerto 1.

Ni siquiera estamos cerca de ningún otro cuello de botella en el puerto de ejecución, por lo que el cuello de botella del front-end es el único problema, y ​​esto debería ejecutarse en una iteración por cada 2.5 ciclos en Intel Haswell y más tarde.

El desenrollado de bucles podría ayudar aquí a reducir la cantidad de uops por cheque. por ejemplo, use lea ecx, [rbx+1] para calcular b + 1 para la siguiente iteración, de modo que podamos imul ebx, ebx sin usar un MOV para hacerlo no destructivo.

También es posible una reducción de la fuerza : dado b*b podemos intentar calcular (b-1) * (b-1) sin un IMUL. (b-1) * (b-1) = b*b - 2*b + 1 , así que tal vez podamos hacer un lea ecx, [rbx*2 - 1] y luego restarlo de b*b . (No hay modos de direccionamiento que restan en lugar de agregar. Hmm, tal vez podríamos mantener -b en un registro, y contar hacia cero, entonces podríamos usar lea ecx, [rcx + rbx*2 - 1] para actualizar b*b en ECX, dado -b en EBX).

A menos que realmente bloquee el rendimiento de IMUL, esto podría llevar a más usuarios y no ser un ganador. Podría ser divertido ver qué tan bien haría un compilador con esta reducción de la fuerza en la fuente de C ++.

Probablemente también puedas vectorizar esto con SSE o AVX , verificando 4 u 8 valores b consecutivos en paralelo. Dado que los éxitos son realmente raros, simplemente verifica si alguno de los 8 tuvo un golpe y luego determina cuál era en el raro caso de que hubiera una coincidencia.

Consulte también la wiki de la etiqueta x86 para obtener más información sobre optimización.

Answer 2

pow() funciona con números reales de coma flotante y utiliza bajo el capó la fórmula

pow(x,y) = e^(y log(x))

para calcular x^y . Los int se convierten en double antes de llamar a pow . ( log es el logaritmo natural, basado en e)

x^2 usando pow() es, por lo tanto, más lento que x*x .

Edición basada en comentarios relevantes

• Usar pow incluso con exponentes enteros puede producir resultados incorrectos ( PaulMcKenzie )
• Además de usar una función matemática con doble tipo, pow es una llamada a función (mientras x*x no lo es) ( jtbandes )
• De hecho, muchos compiladores modernos optimizarán el uso de pow con argumentos enteros constantes, pero esto no se debe confiar.