Optimizando un "while (1);" en C ++ 0x

153

Actualizado, ver abajo!

He escuchado y leído que C ++ 0x permite que un compilador imprima "Hola" para el siguiente fragmento

#include <iostream>

int main() {
  while(1) 
    ;
  std::cout << "Hello" << std::endl;
}

Aparentemente tiene algo que ver con hilos y capacidades de optimización. Sin embargo, me parece que esto puede sorprender a muchas personas.

¿Alguien tiene una buena explicación de por qué esto era necesario permitir? Como referencia, el borrador más reciente de C ++ 0x dice en6.5/5

Un bucle que, fuera de la declaración for-init en el caso de una declaració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)

la implementación puede suponer que termina. [Nota: Esto está destinado a permitir transformaciones del compilador, como la eliminación de bucles vacíos, incluso cuando no se pueda probar la terminación. - nota final]

Editar:

Este artículo perspicaz dice sobre ese texto de Normas

Lamentablemente, las palabras "comportamiento indefinido" no se utilizan. Sin embargo, cada vez que el estándar dice "el compilador puede asumir P", está implícito que un programa que tiene la propiedad no-P tiene una semántica indefinida.

¿Es correcto y el compilador puede imprimir "Bye" para el programa anterior?


Aquí hay un hilo aún más perspicaz , que trata sobre un cambio análogo a C, iniciado por el tipo que hizo el artículo vinculado anterior. Entre otros datos útiles, presentan una solución que parece aplicarse también a C ++ 0x ( Actualización : esto ya no funcionará con n3225, ¡vea a continuación!)

endless:
  goto endless;

Un compilador no puede optimizar eso, parece, porque no es un bucle, sino un salto. Otro tipo resume el cambio propuesto en C ++ 0x y C201X

Al escribir un bucle, el programador está afirmando ya sea que el bucle hace algo con el comportamiento visible (realiza de E / S, accesos objetos volátiles, o la sincronización realiza o operaciones atómicas), o que eventualmente termina. Si violo esa suposición escribiendo un bucle infinito sin efectos secundarios, le 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 bucle infinito sin un comportamiento visible.


Actualización el 3.1.2011 con n3225: el Comité movió el texto al 1.10 / 24 y dijo

La implementación puede suponer que cualquier hilo eventualmente hará uno de los siguientes:

  • 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 gototruco ya no funcionará!

Johannes Schaub - litb
fuente
44
while(1) { MyMysteriousFunction(); }debe ser compilable independientemente sin conocer la definición de esa misteriosa función, ¿verdad? Entonces, ¿cómo podemos determinar si realiza llamadas a alguna función de E / S de la biblioteca? En otras palabras: seguramente esa primera viñeta podría estar redactada no hace llamadas a funciones .
Daniel Earwicker
19
@Daniel: Si tiene acceso a la definición de la función, puede probar muchas cosas. Existe la optimización interprocedural.
Potatoswatter
3
En este momento, en C ++ 03, es un compilador permitido al cambio int x = 1; for(int i = 0; i < 10; ++i) do_something(&i); x++;en for(int i = 0; i < 10; ++i) do_something(&i); int x = 2;? O posiblemente al revés, con xser inicializado a2 antes del bucle. Puede decir que do_somethingno le importa el valor de x, por lo que es una optimización perfectamente segura, si do_something no hace que el valor de icambie de modo que termine en un bucle infinito.
Dennis Zickefoose
44
Entonces, ¿esto significa que main() { start_daemon_thread(); while(1) { sleep(1000); } }podría salir inmediatamente en lugar de ejecutar mi demonio en un hilo de fondo?
Gabe
2
"Este artículo perspicaz" asume que un comportamiento específico es Comportamiento indefinido simplemente porque no hay un comportamiento explícito y definido. Esa es una suposición incorrecta. En general, cuando el estándar deja abierto un número finito de comportamientos, una implementación debe elegir cualquiera de esos ( Comportamiento no especificado ). Esto no necesita ser determinista. Si un bucle de no hacer nada termina es posiblemente una opción booleana; o lo hace o no. Hacer otra cosa no está permitido.
MSalters

Respuestas:

33

¿Alguien tiene una buena explicación de por qué esto era necesario permitir?

Sí, Hans Boehm proporciona una justificación para esto en N1528: ¿Por qué un comportamiento indefinido para bucles infinitos? , aunque este es el documento WG14, la justificación se aplica también a C ++ y el documento hace referencia tanto a WG14 como a WG21:

Como N1509 señala correctamente, el borrador actual esencialmente da un comportamiento indefinido a 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 ciclo potencialmente sin terminación. 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;
}

¿Podrían estos dos bucles fusionarse 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 carrera de datos.

En casos como este, es muy poco probable que un compilador pueda probar la terminación del bucle; 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 que a menudo es imposible sin la información completa del programa.

Las restricciones impuestas por los bucles sin terminación son una restricción a la optimización de los bucles de terminación para los cuales el compilador no puede probar la terminación, así como a la optimización de los bucles que realmente no terminan. Los primeros son mucho más comunes que los segundos y, a menudo, son más interesantes de optimizar.

Claramente también hay bucles for con una variable de bucle entero en la que sería difícil para un compilador probar la terminación, y por lo tanto sería difícil para el compilador reestructurar bucles sin 6.8.5p6. Incluso algo 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 números para probar la terminación, en el último caso, necesitamos saber algo sobre los posibles valores de j para hacerlo. El ajuste para enteros sin signo puede complicar aún más parte de este razonamiento. )

Este problema parece aplicarse a casi todas las transformaciones de reestructuración de bucles, incluidas la paralelización del compilador y las transformaciones de optimización de caché, las cuales pueden ganar importancia, y ya son importantes para el código numérico. Parece probable que esto se convierta en un costo sustancial en 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 difiere de C ++ y hace que su ejemplo específico esté bien definido en C11.

Shafik Yaghmour
fuente
1
¿Existe alguna optimización segura y útil que sea facilitada por el lenguaje actual que no se facilitaría tan bien al decir "Si la terminación de un ciclo depende del estado de cualquier objeto, el tiempo requerido para ejecutar el ciclo no se considera un efecto secundario observable, incluso si ese tiempo es infinito ". Dado el do { x = slowFunctionWithNoSideEffects(x);} while(x != 23);código de elevación después del ciclo que no dependería x, parecería seguro y razonable, pero permitir que un compilador asuma x==23en dicho código parece más peligroso que útil.
supercat
47

Para mí, la justificación relevante es:

Esto está destinado a permitir transformaciones del compilador, como la eliminación de bucles vacíos, incluso cuando no se pueda probar la terminación.

Presumiblemente, esto se debe a que probar la terminación mecánicamente es difícil , y la imposibilidad de probar la terminación obstaculiza los compiladores que de otro modo podrían hacer transformaciones útiles, como mover operaciones no dependientes desde antes del ciclo hasta después o viceversa, realizar operaciones posteriores al ciclo en un hilo mientras el bucle se ejecuta en otro, y así sucesivamente. Sin estas transformaciones, un bucle podría bloquear todos los otros subprocesos mientras esperan que un subproceso termine dicho bucle. (Utilizo "hilo" libremente 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 hilo hacer complex_io_operationmientras 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 bucle, y 2) que el bucle terminará . Probar 1) es bastante fácil, probar 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 imagino que los diseñadores consideraron que los casos en los que se producen bucles infinitos en el código de producción son muy raros y generalmente son como bucles controlados por eventos que acceden de alguna manera a las E / S. Como resultado, han pesimizado el caso raro (bucles infinitos) a favor de optimizar el caso más común (no infinito, pero difícil de probar mecánicamente bucles no infinitos).

Sin embargo, sí significa que los bucles infinitos utilizados en los ejemplos de aprendizaje sufrirán como resultado y aumentarán las trampas en el código de principiante. No puedo decir que esto sea algo completamente 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 es indefinido". 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 asumir que una variable x solo se asigna como máximo una vez entre puntos de secuencia" es equivalente a "asignar a x más de una vez entre puntos de secuencia no está definido".

Philip Potter
fuente
"Probar 1) es bastante fácil", de hecho, ¿no se deduce inmediatamente de las 3 condiciones para que el compilador pueda asumir la terminación del bucle bajo la cláusula sobre la que Johannes pregunta? Creo que equivalen a "el bucle no tiene un efecto observable, excepto quizás girar para siempre", y la cláusula asegura que "girar para siempre" no garantiza el comportamiento de dichos bucles.
Steve Jessop
@Steve: es fácil si el ciclo no termina; pero si el ciclo termina, entonces puede tener un comportamiento no trivial que afecta el procesamiento de complex_io_operation.
Philip Potter el
Vaya, sí, me perdí que podría modificar locales / alias no volátiles / lo que sea que se use en el IO op. Entonces tiene razón: aunque no necesariamente se sigue, hay muchos casos en los que los compiladores pueden probar y demuestran que no se produce tal modificación.
Steve Jessop
"Sin embargo, significa que los bucles infinitos utilizados en los ejemplos de aprendizaje sufrirán como resultado y aumentarán las trampas en el código de principiante. No puedo decir que esto sea algo completamente bueno". Simplemente compile con las optimizaciones desactivadas y aún debería funcionar
KitsuneYMG
1
@supercat: Lo que describe es lo que sucederá en la práctica, pero no es lo que requiere el borrador del estándar. No podemos suponer que el compilador no sabe si un bucle terminará. Si el compilador hace saber el bucle no dará por terminado, se puede hacer lo que le gusta. El DS9K será crear demonios nasales para cualquier bucle infinito sin I / O etc. (Por lo tanto, los resuelve DS9K el problema de la parada.)
Philip Potter
15

Creo que la interpretación correcta es la de su edición: los bucles infinitos vacíos son comportamientos indefinidos.

No diría que es un comportamiento particularmente intuitivo, pero esta interpretación tiene más sentido que la alternativa, que el compilador puede ignorar arbitrariamente bucles infinitos sin invocar UB.

Si los bucles infinitos son UB, solo significa que los programas sin terminación no se consideran significativos: de acuerdo con C ++ 0x, tienen semántica.

Eso también tiene cierto sentido. Son un caso especial, donde ya no se producen una serie de efectos secundarios (por ejemplo, nunca se devuelve nada main), y una serie de optimizaciones del compilador se ven obstaculizadas por tener que 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 ciclo nunca termina, no podemos reorganizar el código de manera segura, ya que podríamos estar cambiando qué operaciones se ejecutan antes de que el programa se cuelgue. A menos que tratemos un programa colgante como UB, eso es.

jalf
fuente
77
¿"Bucles infinitos vacíos son comportamientos indefinidos"? Alan Turing pediría diferir, pero solo cuando deja de girar en su tumba.
Donal Fellows
11
@Donal: Nunca dije nada sobre su semántica en una máquina de Turing. Estamos discutiendo la semántica de un bucle infinito sin efectos secundarios en C ++ . Y mientras lo leo, C ++ 0x elige decir que tales bucles no están definidos.
jalf
Los bucles infinitos vacíos serían una tontería, y no habría razón para tener reglas especiales para ellos. La regla está diseñada para manejar bucles útiles de duración ilimitada (con suerte no infinita), que calculan algo que se necesitará en el futuro pero no de inmediato.
supercat
1
¿Significa esto que C ++ 0x no es adecuado para dispositivos integrados? Casi todos los dispositivos integrados no tienen terminación y hacen su trabajo dentro de una gran grasa while(1){...}. Incluso usan habitualmente while(1);para invocar un reinicio asistido por un perro guardián.
vsz
1
@vsz: la primera forma está bien. Los bucles infinitos están perfectamente bien definidos, siempre que tengan algún tipo de comportamiento observable. La segunda forma es más complicada, pero puedo pensar en dos formas muy fáciles de salir: (1) un compilador dirigido a dispositivos integrados podría elegir definir un comportamiento más estricto en ese caso, o (2) crear un cuerpo que llame a alguna función de biblioteca ficticia . Mientras el compilador no sepa qué hace esa función, tiene que suponer que puede tener algún efecto secundario, por lo que no puede meterse con el bucle.
jalf
8

Creo que esto está en la línea de este tipo de pregunta , que hace referencia a otro hilo . La optimización ocasionalmente puede eliminar bucles vacíos.

linuxuser27
fuente
3
Buena pregunta. Parece que ese tipo tenía exactamente el problema que este párrafo le permite a ese compilador. En la discusión vinculada por una de las respuestas, está escrito que "Desafortunadamente, las palabras 'comportamiento indefinido' no se usan. Sin embargo, cada vez que el estándar dice 'el compilador puede asumir P', se implica que un programa que tiene el la propiedad no-P tiene una semántica indefinida ". . Esto me sorprende ¿Significa esto que mi programa de ejemplo anterior tiene un comportamiento indefinido y puede simplemente salir de la nada?
Johannes Schaub - litb
@Johannes: el texto "puede suponerse" no aparece en ningún otro lugar del borrador que tengo a mano, y "puede suponer" solo aparece un par de veces. Aunque verifiqué esto con una función de búsqueda que no coincide con los saltos de línea, es posible que me haya perdido algunos. Así que no estoy seguro de que la generalización del autor esté justificada por la evidencia, pero como matemático tengo que reconocer la lógica del argumento, que si el compilador asume algo falso, en general puede deducir algo ...
Steve Jessop
... Permitir una contradicción en el razonamiento del compilador sobre el programa ciertamente sugiere muy fuertemente a UB, ya que en particular le permite al compilador, para cualquier X, deducir que el programa es equivalente a X. Seguramente permitir que el compilador deduzca que es permitiéndole hacer eso. También estoy de acuerdo con el autor en que, si se pretende UB, debe indicarse explícitamente, y si no es así, el texto de la especificación es incorrecto y debe repararse (tal vez por el equivalente en el lenguaje de especificación de "el compilador puede reemplazar el bucle con código que no tiene efecto ", no estoy seguro).
Steve Jessop
@SteveJessop: ¿Qué pensaría de decir simplemente que la ejecución de cualquier fragmento de código, incluidos los bucles infinitos, puede posponerse hasta el momento en que algo que el fragmento de código afecte a un comportamiento observable del programa, y ​​que a los efectos de eso Por regla general, el tiempo requerido para ejecutar un fragmento de código, incluso si es infinito, no es un "efecto secundario observable". Si un compilador puede demostrar que un bucle no puede salir sin una variable que contenga un cierto valor, se puede considerar que la variable contiene ese valor, incluso se podría demostrar que el bucle no puede salir con ese valor.
supercat
@supercat: como has dicho esa conclusión, no creo que mejore las cosas. Si el bucle probablemente nunca sale, entonces para cualquier objeto Xy patrón de bits x, el compilador puede demostrar que el bucle no sale sin Xmantener el patrón de bits x. Es vacuamente cierto. Por Xlo tanto, podría considerarse que tiene cualquier patrón de bits, y eso es tan malo como UB en el sentido de que por el error Xy xrápidamente causará algunos. Así que creo que debes ser más preciso en tu estándar. Es difícil hablar sobre lo que sucede "al final de" un ciclo infinito, y mostrarlo equivalente a una operación finita.
Steve Jessop
8

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 produjera código de máquina sin terminación para el bucle infinito.

Creo que este es el enfoque correcto. La especificación del lenguaje define formas de imponer el orden de ejecución. Si desea un bucle infinito que no se puede reordenar, escriba esto:

volatile int dummy_side_effect;

while (1) {
    dummy_side_effect = 0;
}

printf("Never prints.\n");
Daniel Newby
fuente
2
@ JohannesSchaub-litb: si un bucle, interminable o no, no lee ni escribe ninguna variable volátil durante la ejecución, y no llama a ninguna función que pueda hacerlo, un compilador es libre de diferir cualquier parte del bucle hasta El primer esfuerzo para acceder a algo calculado en él. Dado unsigned int dummy; while(1){dummy++;} fprintf(stderror,"Hey\r\n"); fprintf(stderror,"Result was %u\r\n",dummy);, el primero fprintfpodría ejecutarse, pero el segundo no (el compilador podría mover el cálculo dummyentre los dos fprintf, pero no más allá del que imprime su valor).
supercat
1

Creo que el problema tal vez podría plantearse mejor como: "Si un código posterior no depende de un código anterior y el código anterior no tiene efectos secundarios en ninguna otra parte del sistema, la salida del compilador puede ejecutar el último código antes, después o entremezclado con la ejecución del primero, incluso si el primero contiene bucles, independientemente de cuándo o si el código anterior realmente se completaría . Por ejemplo, el compilador podría reescribir:

nulo testfermat (int n)
{
  int a = 1, b = 1, c = 1;
  while (pow (a, n) + pow (b, n)! = pow (c, n))
  {
    si (b> a) a ++; si no (c> b) {a = 1; b ++}; más {a = 1; b = 1; c ++};
  }
  printf ("El resultado es");
  printf ("% d /% d /% d", a, b, c);
}

como

nulo 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))
    {
      si (b> a) a ++; si no (c> b) {a = 1; b ++}; más {a = 1; b = 1; c ++};
    }
    signal_other_thread_and_die ();
  }
  else // Segundo hilo
  {
    printf ("El resultado es");
    wait_for_other_thread ();
  }
  printf ("% d /% d /% d", a, b, c);
}

En general, no es irrazonable, aunque me preocuparía que:

  int total = 0;
  para (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 ())
  {
    para (i = 0; num_reps> i; i ++)
      total + = do_something_slow_with_no_side_effects (i);
    signal_other_thread_and_die ();
  }
  más
  {
    para (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 otra maneje las actualizaciones de la barra de progreso, la reescritura mejoraría la eficiencia. Desafortunadamente, las actualizaciones de la barra de progreso serían menos útiles de lo que deberían ser.

Super gato
fuente
Creo que su caso de barra de progreso no se pudo separar, porque mostrar una barra de progreso es una llamada de E / S de la biblioteca. Las optimizaciones no deberían cambiar el comportamiento visible de esta manera.
Philip Potter
@Philip Potter: Si la rutina lenta tuviera efectos secundarios, eso ciertamente sería cierto. En mi ejemplo anterior, no tendría sentido si no fuera así, así que lo cambié. Mi interpretación de la especificación es que el sistema puede diferir la ejecución del código lento hasta el momento en que sus efectos (que no sean el tiempo que lleva ejecutar) se vuelvan visibles, es decir, la llamada show_result (). Si el código de barras de progreso utilizara el total acumulado, o al menos pretendiera hacerlo, eso lo obligaría a sincronizarse con el código lento.
supercat
1
Esto explica todas esas barras de progreso que van rápido de 0 a 100 y luego se cuelgan durante siglos;)
Paul
0

No es decidible para el compilador para casos no triviales si es un bucle infinito.

En diferentes casos, puede suceder que su optimizador alcance una mejor clase de complejidad para su código (por ejemplo, fue O (n ^ 2) y obtendrá O (n) u O (1) después de la optimización).

Por lo tanto, incluir una 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 bastante a tu pregunta.


Otra cosa: nunca he visto ningún ejemplo válido en el que necesite un bucle infinito que no hace nada.

El único ejemplo que escuché fue un hack feo que realmente debería resolverse de otra manera: se trataba de sistemas embebidos donde la única forma de activar un reinicio era congelar el dispositivo para que el perro guardián lo reinicie automáticamente.

Si conoce algún ejemplo válido / bueno donde necesita un bucle infinito que no hace nada, por favor dígame.

Albert
fuente
1
Ejemplo de dónde puede querer un bucle infinito: ¿un sistema integrado en el que no desea dormir por razones de rendimiento y todo el código cuelga de una interrupción o dos?
JCx
@JCx en el Estándar C, las interrupciones deben establecer un indicador que el bucle principal verifica, por lo tanto, el bucle principal tendrá un comportamiento observable en el caso de que se establezcan los indicadores. Ejecutar código sustancial en interrupciones no es portátil.
MM
-1

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 a través de variables no volátiles y no sincronizadas, ahora pueden generar un comportamiento incorrecto con un nuevo compilador.

En otras palabras, haga que sus globales sean volátiles, así como los argumentos pasados ​​a ese bucle a través de un puntero / referencia.

rociar
fuente
Si están interactuando con otros hilos, no debe hacerlos volátiles, hacerlos atómicos o protegerlos con un candado.
BCoates
1
Este es un consejo terrible. Haciéndolos volatileno es ni necesaria ni suffiicent, y duele el rendimiento de forma espectacular.
David Schwartz