¿Por qué es pow (int, int) tan lento?

Has elegido una de las formas más lentas posibles de comprobar

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

Que compila a tres multiplicaciones enteras (una de las cuales puede ser izada fuera del bucle). Incluso sin pow(), todavía estás convirtiendo a double y tomando una raíz cuadrada, lo cual es terrible para el rendimiento. (Y también latencia, pero la predicción de rama + ejecución especulativa en CPUs 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 cycles (source: Agner Fog's instruction tables), por lo que incluso si su versión sqrt() mantiene saturada la unidad de ejecución sqrt de FP, todavía es aproximadamente 4 veces más lenta de lo que tengo que emitir gcc (abajo).

También puede optimizar la condición del bucle para romper el bucle cuando la parte b < c de la condición se convierte en false, 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 -mtune=haswell) para codificar con este bucle interno. Ver el completo código 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 1 uop cada una. (Y los pares cmp/jcc 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 2.5 ciclos.

Haswell ejecuta imul r32, r32 con un rendimiento de una iteración por reloj, por lo que los dos multiplicados dentro del bucle interno no están saturando el puerto 1 a dos multiplicados por 2.5 c. Esto deja espacio para absorber el conflictos inevitables de recursos de ADD y SUB stealing port 1.

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

El desenrollamiento de bucle podría ayudar a reducir el número de uops por comprobación. por ejemplo, use lea ecx, [rbx+1] para calcular b + 1 para la siguiente iteración, por lo que podemos imul ebx, ebx sin usar un MOV para hacerlo no destructivo.

Una reducción de fuerza también es posible : Dado b*b podríamos tratar de calcular (b-1) * (b-1) sin un IMUL. (b-1) * (b-1) = b*b - 2*b + 1, así que tal vez podemos hacer un lea ecx, [rbx*2 - 1] y luego restar eso de b*b. (No hay modos de direccionamiento que resten en lugar de sumar. Hmm, tal vez podríamos mantener -b en un registro, y contar hacia cero, por lo que podríamos usar lea ecx, [rcx + rbx*2 - 1] para actualizar b*b en ECX, dado -b en EBX).

A menos que realmente cuello de botella en el rendimiento IMUL, esto podría terminar tomando más uops y no ser una victoria. Podría ser divertido ver qué tan bien le iría a un compilador con esta reducción de fuerza en el código fuente de C++.

Probablemente también podría vectorizar esto con SSE o AVX , verificando 4 u 8 valores consecutivos b en paralelo. Dado que los hits son realmente raros, solo tienes que comprobar si alguno de los 8 tuvo un hit y luego ordenar cuál fue en el raro caso de que hubo un partido.

Ver también el wiki de etiquetas x86 para más información cosas de optimización.