¿Por qué el compilador no puede (o no) optimizar un ciclo de suma predecible en una multiplicación?

Esta es una pregunta que se me ocurrió al leer la brillante respuesta de Mysticial a la pregunta: ¿por qué es más rápido procesar una matriz ordenada que una matriz sin clasificar ?

Contexto para los tipos involucrados:

const unsigned arraySize = 32768;
int data[arraySize];
long long sum = 0;

En su respuesta, explica que el Compilador Intel (ICC) optimiza esto:

for (int i = 0; i < 100000; ++i)
    for (int c = 0; c < arraySize; ++c)
        if (data[c] >= 128)
            sum += data[c];

... en algo equivalente a esto:

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

El optimizador reconoce que estos son equivalentes y, por lo tanto, intercambiando los bucles , moviendo la rama fuera del bucle interno. ¡Muy inteligente!

¿Pero por qué no hace esto?

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000 * data[c];

Esperemos que Mysticial (o cualquier otra persona) pueda dar una respuesta igualmente brillante. Nunca antes había aprendido sobre las optimizaciones discutidas en esa otra pregunta, así que estoy realmente agradecido por esto.

El compilador generalmente no puede transformar

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

dentro

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000 * data[c];

porque el último podría provocar el desbordamiento de enteros con signo donde el primero no. Incluso con un comportamiento envolvente garantizado para el desbordamiento de los enteros del complemento de dos firmados, cambiaría el resultado (si data[c]es 30000, el producto se convertiría -1294967296en los típicos s de 32 bits intcon envoltura, mientras que 100000 veces agregaría 30000 a sum, si eso fuera así no se desborda, aumenta sumen 3000000000). Tenga en cuenta que lo mismo vale para cantidades sin signo, con números diferentes, el desbordamiento de 100000 * data[c]normalmente introduciría un módulo de reducción 2^32que no debe aparecer en el resultado final.

Podría transformarlo en

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000LL * data[c];  // resp. 100000ull

sin embargo, si, como de costumbre, long longes suficientemente mayor que int.

No puedo decir por qué no hace eso, supongo que es lo que dijo Mysticial , "aparentemente, no ejecuta un pase de colapso de bucle después del intercambio de bucle".

Tenga en cuenta que el intercambio de bucles en sí no es generalmente válido (para enteros con signo), ya que

for (int c = 0; c < arraySize; ++c)
    if (condition(data[c]))
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

puede conducir al desbordamiento donde

for (int i = 0; i < 100000; ++i)
    for (int c = 0; c < arraySize; ++c)
        if (condition(data[c]))
            sum += data[c];

no lo haría Aquí es kosher, ya que la condición garantiza data[c]que todos los que se agreguen tengan el mismo signo, por lo que si uno se desborda, ambos lo hacen.

Sin embargo, no estaría muy seguro de que el compilador lo haya tenido en cuenta (@Mysticial, ¿podría intentarlo con una condición como data[c] & 0x80esa que puede ser cierta para los valores positivos y negativos?). Hice que los compiladores hicieran optimizaciones inválidas (por ejemplo, hace un par de años, tuve un ICC (11.0, iirc) que usaba conversión de 32 bits con int a doble en 1.0/ndonde nera un unsigned int. Era aproximadamente el doble de rápido que el de gcc salida. Pero mal, muchos valores eran mayores que 2^31, ¡Uy!).

Esta respuesta no se aplica al caso específico vinculado, pero se aplica al título de la pregunta y puede ser interesante para futuros lectores:

Debido a la precisión finita, la suma repetida de punto flotante no es equivalente a la multiplicación . Considerar:

float const step = 1e-15;
float const init = 1;
long int const count = 1000000000;

float result1 = init;
for( int i = 0; i < count; ++i ) result1 += step;

float result2 = init;
result2 += step * count;

cout << (result1 - result2);

Manifestación

El compilador contiene varios pases que hacen la optimización. Por lo general, en cada pasada, se realiza una optimización en las declaraciones o optimizaciones de bucle. En la actualidad no existe un modelo que optimice el cuerpo del bucle en función de los encabezados del bucle. Esto es difícil de detectar y menos común.

La optimización que se realizó fue un movimiento de código invariante de bucle. Esto se puede hacer usando un conjunto de técnicas.

Bueno, supongo que algunos compiladores podrían hacer este tipo de optimización, suponiendo que estamos hablando de Integer Arithmetics.

Al mismo tiempo, algunos compiladores pueden negarse a hacerlo porque reemplazar la suma repetitiva con la multiplicación podría cambiar el comportamiento de desbordamiento del código. Para los tipos enteros sin signo, no debería hacer una diferencia ya que su comportamiento de desbordamiento está completamente especificado por el idioma. Pero para los firmados, podría (aunque probablemente no en la plataforma de complemento de 2). Es cierto que el desbordamiento firmado en realidad conduce a un comportamiento indefinido en C, lo que significa que debería estar perfectamente bien ignorar esa semántica de desbordamiento por completo, pero no todos los compiladores son lo suficientemente valientes como para hacerlo. A menudo atrae muchas críticas de la multitud "C es solo un lenguaje ensamblador de nivel superior". (¿Recuerdas lo que sucedió cuando GCC introdujo optimizaciones basadas en semánticas de alias estricto?)

Históricamente, GCC se ha mostrado como un compilador que tiene lo necesario para dar pasos tan drásticos, pero otros compiladores podrían preferir seguir con el comportamiento percibido "intencionado por el usuario" incluso si el lenguaje no lo define.

Lo hace ahora, al menos, el sonido metálico hace :

long long add_100k_signed(int *data, int arraySize)
{
    long long sum = 0;

    for (int c = 0; c < arraySize; ++c)
        if (data[c] >= 128)
            for (int i = 0; i < 100000; ++i)
                sum += data[c];
    return sum;
}

compila con -O1 para

add_100k_signed:                        # @add_100k_signed
        test    esi, esi
        jle     .LBB0_1
        mov     r9d, esi
        xor     r8d, r8d
        xor     esi, esi
        xor     eax, eax
.LBB0_4:                                # =>This Inner Loop Header: Depth=1
        movsxd  rdx, dword ptr [rdi + 4*rsi]
        imul    rcx, rdx, 100000
        cmp     rdx, 127
        cmovle  rcx, r8
        add     rax, rcx
        add     rsi, 1
        cmp     r9, rsi
        jne     .LBB0_4
        ret
.LBB0_1:
        xor     eax, eax
        ret

El desbordamiento de enteros no tiene nada que ver con eso; Si hay un desbordamiento de enteros que causa un comportamiento indefinido, puede suceder en cualquier caso. Aquí está el mismo tipo de función usando en intlugar delong :

int add_100k_signed(int *data, int arraySize)
{
    int sum = 0;

    for (int c = 0; c < arraySize; ++c)
        if (data[c] >= 128)
            for (int i = 0; i < 100000; ++i)
                sum += data[c];
    return sum;
}

compila con -O1 para

add_100k_signed:                        # @add_100k_signed
        test    esi, esi
        jle     .LBB0_1
        mov     r9d, esi
        xor     r8d, r8d
        xor     esi, esi
        xor     eax, eax
.LBB0_4:                                # =>This Inner Loop Header: Depth=1
        mov     edx, dword ptr [rdi + 4*rsi]
        imul    ecx, edx, 100000
        cmp     edx, 127
        cmovle  ecx, r8d
        add     eax, ecx
        add     rsi, 1
        cmp     r9, rsi
        jne     .LBB0_4
        ret
.LBB0_1:
        xor     eax, eax
        ret

Hay una barrera conceptual para este tipo de optimización. Los autores del compilador dedican mucho esfuerzo a la reducción de la fuerza , por ejemplo, reemplazando las multiplicaciones con sumas y cambios. Se acostumbran a pensar que las multiplicaciones son malas. Por lo tanto, un caso en el que uno debería ir por el otro lado es sorprendente y contradictorio. Entonces nadie piensa implementarlo.

Las personas que desarrollan y mantienen compiladores tienen una cantidad limitada de tiempo y energía para gastar en su trabajo, por lo que generalmente quieren centrarse en lo que más les importa a sus usuarios: convertir el código bien escrito en código rápido. No quieren pasar su tiempo tratando de encontrar formas de convertir el código tonto en código rápido, para eso sirve la revisión de código. En un lenguaje de alto nivel, puede haber un código "tonto" que exprese una idea importante, haciendo que valga la pena el tiempo de los desarrolladores para acelerarlo, por ejemplo, la deforestación de atajo y la fusión de corrientes permiten a los programas de Haskell estructurados en torno a ciertos tipos de pereza produjo estructuras de datos para ser compiladas en ciclos cerrados que no asignan memoria. Pero ese tipo de incentivo simplemente no se aplica a convertir la suma en bucle en multiplicación. Si quieres que sea rápido,