significa - ¿Por qué el compilador no puede(o no lo hace) optimizar un bucle de adición predecible en una multiplicación?

predecible ejemplos

Question

Esta es una pregunta que me vino a la mente al leer la respuesta brillante 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 está reconociendo que estos son equivalentes y, por lo tanto, está 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.

Answer 1

Bueno, supongo que algunos compiladores podrían hacer este tipo de optimización, suponiendo que estamos hablando de aritmética de enteros.

Al mismo tiempo, algunos compiladores pueden negarse a hacerlo porque reemplazar la adición repetitiva con la multiplicación podría cambiar el comportamiento de desbordamiento del código. Para los tipos integrales unsigned no debería marcar la diferencia, ya que el idioma especifica por completo su comportamiento de desbordamiento. Pero para los firmados podría (probablemente no en la plataforma de complemento de 2). Es cierto que el desbordamiento firmado realmente conduce a un comportamiento indefinido en C, lo que significa que debería estar perfectamente bien ignorar por completo la semántica de desbordamiento, aunque no todos los compiladores son lo suficientemente valientes como para hacer eso. A menudo recibe muchas críticas del público "C es solo un lenguaje ensamblador de alto nivel". (¿Recuerda lo que sucedió cuando GCC introdujo optimizaciones basadas en semántica de alias estrictos?)

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 como "intencionado por el usuario", incluso si no está definido por el lenguaje.

Answer 2

El compilador contiene varios pases que hace la optimización. Por lo general, en cada pasada se realiza una optimización en las declaraciones o optimizaciones de bucle. Actualmente no existe un modelo que realice una optimización del 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 el movimiento de código invariante de bucle. Esto se puede hacer usando un conjunto de técnicas.

Answer 3

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 este último podría conducir al desbordamiento de enteros con signo donde el primero no. Incluso con un comportamiento envolvente garantizado para el desbordamiento de los enteros complementarios dos firmados, cambiaría el resultado (si los data[c] son 30000, el producto pasaría a ser -1294967296 para los típicos int 32 bits con envoltura, mientras que 100000 veces agregar 30000 a sum sería, si eso no se desborda, aumentar la sum en 3000000000). Tenga en cuenta que lo mismo se aplica a las cantidades sin firmar, con números diferentes, el desbordamiento de 100000 * data[c] normalmente introduciría un módulo de reducción 2^32 que 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 siempre, long long es suficientemente más grande que int .

Por qué no hace eso, no puedo decir, 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 bucle 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 Es kosher aquí, ya que la condición asegura que todos los data[c] que se agregan tienen el mismo signo, por lo que si uno se desborda, ambos lo hacen.

Sin embargo, no estaría tan seguro de que el compilador tuviera eso en cuenta (@Mysticial, ¿podría probar con una condición como data[c] & 0x80 o menos que pueda ser cierto para valores positivos y negativos?). Hice que los compiladores realizaran optimizaciones no válidas (por ejemplo, hace un par de años, tuve un ICC (11.0, iirc) que usaba la conversión signed-32-bit-int-to-double en 1.0/n donde n era un unsigned int . aproximadamente el doble de rápido que la salida de gcc. Pero equivocado, muchos valores eran más grandes que 2^31 , ¡Uy!).

Answer 4

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

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);

Demostración: http://ideone.com/7RhfP

Answer 5

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

Answer 6

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 interesa a sus usuarios: convertir el código bien escrito en código rápido. No quieren gastar su tiempo tratando de encontrar formas de convertir el código tonto en código rápido; para eso es la revisión de código. En un lenguaje de alto nivel, puede haber un código "tonto" que exprese una idea importante, por lo que vale la pena el tiempo de los desarrolladores para hacerlo rápido; por ejemplo, la deforestación corta y la fusión de flujos permiten que los programas de Haskell se estructuran en torno a ciertos tipos de produjo estructuras de datos para ser compiladas en bucles ajustados que no asignan memoria. Pero ese tipo de incentivo simplemente no se aplica a convertir la adición en bucle en multiplicación. Si quieres que sea rápido, solo escríbelo con multiplicación.