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.