Optimizar un "while(1);" en C++ 0x
optimization loops (8)
Actualizado, mira abajo!
He escuchado y leído que C ++ 0x permite a un compilador imprimir "Hola" para el siguiente fragmento
#include <iostream>
int main() {
while(1)
;
std::cout << "Hello" << std::endl;
}
Aparentemente tiene algo que ver con los hilos y las capacidades de optimización. Sin embargo, me parece que esto puede sorprender a muchas personas.
¿Alguien tiene una buena explicación de por qué fue necesario permitir esto? Como referencia, el borrador más reciente de C ++ 0x dice a 6.5/5
Un bucle que, fuera de la instrucción for-init en el caso de una instrucción for,
- no realiza llamadas a las funciones de E / S de la biblioteca, y
- no accede ni modifica objetos volátiles, y
- no realiza operaciones de sincronización (1.10) u operaciones atómicas (Cláusula 29)
puede ser asumida por la implementación para terminar. [Nota: Esto está diseñado para permitir las transformaciones del compilador, como la eliminación de bucles vacíos, incluso cuando la terminación no puede ser probada. - nota final]
Editar:
Este perspicaz artículo dice acerca de ese texto de Estándares
Lamentablemente, las palabras "comportamiento indefinido" no se utilizan. Sin embargo, cada vez que el estándar dice "el compilador puede asumir P", se da a entender que un programa que tiene la propiedad not-P tiene una semántica indefinida.
¿Es correcto y el compilador puede imprimir "Adiós" para el programa anterior?
Aquí hay un hilo conductor aún más perspicaz, que trata sobre un cambio análogo a C, iniciado por el individuo, hecho en el artículo vinculado anterior. Entre otros hechos útiles, presentan una solución que también parece aplicarse a C ++ 0x ( Actualización : Esto ya no funcionará con n3225 - ver más abajo!)
endless:
goto endless;
Un compilador no puede optimizar eso, al parecer, porque no es un bucle, sino un salto. Otro chico resume el cambio propuesto en C ++ 0x y C201X
Al escribir un bucle, el programador afirma que el bucle hace algo con un comportamiento visible (realiza operaciones de E / S, accede a objetos volátiles, realiza sincronizaciones u operaciones atómicas) o termina eventualmente. Si violo esa suposición al escribir un ciclo infinito sin efectos secundarios, estoy mintiendo al compilador, y el comportamiento de mi programa no está definido. (Si tengo suerte, el compilador podría advertirme al respecto.) El lenguaje no proporciona (¿ya no proporciona?) Una forma de expresar un ciclo infinito sin un comportamiento visible.
Actualización el 3.1.2011 con n3225: el comité movió el texto a 1.10 / 24 y dijo
La implementación puede suponer que cualquier subproceso llevará a cabo una de las siguientes acciones:
- Terminar,
- hacer una llamada a una función de E / S de la biblioteca,
- acceder o modificar un objeto volátil, o
- realizar una operación de sincronización o una operación atómica.
¡El truco de goto ya no funcionará!
¿Alguien tiene una buena explicación de por qué fue necesario permitir esto?
Sí, Hans Boehm proporciona una razón fundamental para esto en N1528: ¿Por qué comportamiento indefinido para bucles infinitos? Aunque este es el documento WG14, la justificación también se aplica a C ++ y el documento hace referencia tanto a WG14 como a WG21:
Como correctamente señala el N1509, el borrador actual esencialmente da un comportamiento indefinido a los bucles infinitos en 6.8.5p6. Un problema importante para hacerlo es que permite que el código se mueva a través de un bucle potencialmente no terminable. Por ejemplo, supongamos que tenemos los siguientes bucles, donde count y count2 son variables globales (o se ha tomado su dirección), y p es una variable local, cuya dirección no se ha tomado:
for (p = q; p != 0; p = p -> next) { ++count; } for (p = q; p != 0; p = p -> next) { ++count2; }¿Se podrían fusionar estos dos bucles y reemplazarse por el siguiente bucle?
for (p = q; p != 0; p = p -> next) { ++count; ++count2; }Sin la dispensación especial en 6.8.5p6 para bucles infinitos, esto no se permitiría: si el primer bucle no termina porque q apunta a una lista circular, el original nunca escribe en count2. Por lo tanto, podría ejecutarse en paralelo con otro hilo que acceda o actualice count2. Esto ya no es seguro con la versión transformada que accede a count2 a pesar del bucle infinito. Por lo tanto, la transformación potencialmente introduce una raza de datos.
En casos como este, es muy poco probable que un compilador pueda probar la terminación del ciclo; Tendría que entender que q apunta a una lista acíclica, que creo que está más allá de la capacidad de la mayoría de los compiladores convencionales, y a menudo es imposible sin toda la información del programa.
Las restricciones impuestas por los bucles no terminadores son una restricción en la optimización de bucles de terminación para los cuales el compilador no puede probar la terminación, así como en la optimización de bucles realmente no terminadores. Los primeros son mucho más comunes que los segundos, y a menudo más interesantes de optimizar.
Claramente también hay bucles for con una variable de ciclo entero en la cual sería difícil para un compilador probar la terminación, y sería difícil para el compilador reestructurar bucles sin 6.8.5p6. Incluso algo así como
for (i = 1; i != 15; i += 2)o
for (i = 1; i <= 10; i += j)parece no trivial de manejar. (En el primer caso, se requiere cierta teoría básica de los números para probar la terminación, en este último caso, necesitamos saber algo sobre los posibles valores de j para hacerlo. El reenvío para los enteros sin signo puede complicar aún más este razonamiento. )
Este problema parece aplicarse a casi todas las transformaciones de reestructuración de bucle, incluidas la paralelización de compiladores y las transformaciones de optimización de caché, que probablemente ganarán importancia y ya son importantes para el código numérico. Es probable que esto se convierta en un costo sustancial para el beneficio de poder escribir bucles infinitos de la manera más natural posible, especialmente porque la mayoría de nosotros rara vez escribimos bucles intencionalmente infinitos.
La principal diferencia con C es que C11 proporciona una excepción para controlar expresiones que son expresiones constantes que difieren de C ++ y hace que su ejemplo específico esté bien definido en C11.
Creo que el problema podría ser mejor dicho, ya que "si una parte posterior del código no depende de una pieza anterior de código, y la parte anterior del código no tiene efectos secundarios en ninguna otra parte del sistema, la salida del compilador puede ejecutar el último fragmento de código antes, después o entremezclado con la ejecución del primero, incluso si el primero contiene bucles, sin tener en cuenta cuándo o si el código anterior realmente se completaría . Por ejemplo, el compilador podría reescribir:
void testfermat(int n) { int a=1,b=1,c=1; while(pow(a,n)+pow(b,n) != pow(c,n)) { if (b > a) a++; else if (c > b) {a=1; b++}; else {a=1; b=1; c++}; } printf("The result is "); printf("%d/%d/%d", a,b,c); }
como
void testfermat(int n) { if (fork_is_first_thread()) { int a=1,b=1,c=1; while(pow(a,n)+pow(b,n) != pow(c,n)) { if (b > a) a++; else if (c > b) {a=1; b++}; else {a=1; b=1; c++}; } signal_other_thread_and_die(); } else // Second thread { printf("The result is "); wait_for_other_thread(); } printf("%d/%d/%d", a,b,c); }
Generalmente no es irracional, aunque podría preocuparme que:
int total=0; for (i=0; num_reps > i; i++) { update_progress_bar(i); total+=do_something_slow_with_no_side_effects(i); } show_result(total);
se convertiría
int total=0; if (fork_is_first_thread()) { for (i=0; num_reps > i; i++) total+=do_something_slow_with_no_side_effects(i); signal_other_thread_and_die(); } else { for (i=0; num_reps > i; i++) update_progress_bar(i); wait_for_other_thread(); } show_result(total);
Al hacer que una CPU maneje los cálculos y otro manipular la barra de progreso se actualiza, la reescritura mejoraría la eficiencia. Desafortunadamente, las actualizaciones de la barra de progreso serían menos útiles de lo que deberían ser.
Creo que la interpretación correcta es la de tu edición: los bucles infinitos vacíos son un comportamiento indefinido.
No diría que es un comportamiento particularmente intuitivo, pero esta interpretación tiene más sentido que la alternativa, que al compilador se le permite arbitrariamente ignorar bucles infinitos sin invocar a UB.
Si los bucles infinitos son UB, significa que los programas que no terminan no se consideran significativos: según C ++ 0x, no tienen semántica.
Eso tiene un cierto sentido también. Son un caso especial, donde ya no se producen varios efectos secundarios (por ejemplo, nunca se devuelve nada desde main ), y una cantidad de optimizaciones del compilador se ven obstaculizadas por la necesidad de preservar bucles infinitos. Por ejemplo, mover cálculos a través del ciclo es perfectamente válido si el ciclo no tiene efectos secundarios, porque eventualmente, el cálculo se realizará en cualquier caso. Pero si el bucle nunca termina, no podemos reordenar el código de forma segura a través de él, porque podríamos estar cambiando las operaciones que realmente se ejecutan antes de que se cuelgue el programa. A menos que tratemos un programa colgante como UB, eso es.
Creo que vale la pena señalar que los bucles que serían infinitos, excepto por el hecho de que interactúan con otros hilos mediante variables no volátiles y no sincronizadas, ahora pueden generar un comportamiento incorrecto con un nuevo compilador.
En otras palabras, haz que tus globales sean volátiles, así como los argumentos pasados a dicho ciclo a través de un puntero / referencia.
El problema relevante es que el compilador puede reordenar el código cuyos efectos secundarios no entran en conflicto. El sorprendente orden de ejecución podría ocurrir incluso si el compilador producía código de máquina no terminante para el ciclo infinito.
Creo que este es el enfoque correcto. La especificación de idioma define las formas de aplicar el orden de ejecución. Si quieres un bucle infinito que no se puede reordenar, escribe esto:
volatile int dummy_side_effect;
while (1) {
dummy_side_effect = 0;
}
printf("Never prints./n");
No es decidible para el compilador para casos no triviales si se trata de un ciclo infinito.
En diferentes casos, puede suceder que su optimizador alcance una clase de complejidad mejor para su código (por ejemplo, fue O (n ^ 2) y obtiene O (n) u O (1) después de la optimización).
Por lo tanto, incluir tal regla que no permita eliminar un bucle infinito en el estándar C ++ haría imposible muchas optimizaciones. Y la mayoría de la gente no quiere esto. Creo que esto responde tu pregunta.
Otra cosa: nunca he visto ningún ejemplo válido donde necesites un bucle infinito que no hace nada.
El único ejemplo del que he oído hablar es un truco feo que realmente debería resolverse de otro modo: se trataba de sistemas integrados en los que la única forma de activar un reinicio era congelar el dispositivo para que el perro guardián lo reiniciara automáticamente.
Si conoce algún ejemplo válido / bueno en el que necesita un ciclo infinito que no hace nada, por favor dígame.
Para mí, la justificación relevante es:
Esto tiene como objetivo permitir las transformaciones del compilador, como la eliminación de bucles vacíos, incluso cuando la terminación no puede ser probada.
Presumiblemente, esto se debe a que probar la terminación mecánicamente es difícil y la incapacidad para probar la terminación obstaculiza los compiladores que de otro modo podrían realizar transformaciones útiles, como mover operaciones no dependientes desde antes al bucle o viceversa, realizar operaciones de bucle en un hilo mientras el ciclo se ejecuta en otro, y así sucesivamente. Sin estas transformaciones, un bucle podría bloquear todos los otros hilos mientras esperan que el único hilo termine dicho bucle. (Uso el término "hilo" para referirme a cualquier forma de procesamiento paralelo, incluidas las secuencias de instrucciones VLIW separadas).
EDITAR: Ejemplo tonto:
while (complicated_condition()) {
x = complicated_but_externally_invisible_operation(x);
}
complex_io_operation();
cout << "Results:" << endl;
cout << x << endl;
Aquí, sería más rápido para un subproceso hacer el complex_io_operation mientras que el otro está haciendo todos los cálculos complejos en el bucle. Pero sin la cláusula que ha citado, el compilador debe probar dos cosas antes de poder realizar la optimización: 1) que complex_io_operation() no depende de los resultados del ciclo, y 2) que el ciclo terminará . Probar 1) es bastante fácil, demostrando 2) es el problema de detención. Con la cláusula, puede suponer que el bucle termina y obtener una ganancia de paralelización.
También me imagino que los diseñadores consideraron que los casos en que ocurren bucles infinitos en el código de producción son muy raros y generalmente son cosas como bucles impulsados por eventos que acceden a E / S de alguna manera. Como resultado, han ponderado el raro caso (bucles infinitos) a favor de la optimización del caso más común (no infinito, pero difícil de demostrar mecánicamente no infinito, bucles).
Sin embargo, significa que los bucles infinitos utilizados en ejemplos de aprendizaje sufrirán como resultado, y aumentarán los errores en el código de principiante. No puedo decir que esto sea del todo bueno.
EDITAR: con respecto al artículo perspicaz que ahora vincula, diría que "el compilador puede asumir X sobre el programa" es lógicamente equivalente a "si el programa no satisface X, el comportamiento no está definido". Podemos mostrar esto de la siguiente manera: supongamos que existe un programa que no satisface la propiedad X. ¿Dónde se definiría el comportamiento de este programa? El Estándar solo define el comportamiento asumiendo que la propiedad X es verdadera. Aunque el Estándar no declara explícitamente el comportamiento indefinido, lo ha declarado indefinido por omisión.
Considere un argumento similar: "el compilador puede suponer que una variable x solo se asigna a lo sumo una vez entre puntos de secuencia" es equivalente a "asignar a x más de una vez entre puntos de secuencia no está definido".