optimization - Optimizar un "while(1);" en C++0x




loops c++11 (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á!


Answers

¿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.


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

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 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 esto es similar a este tipo de question , que hace referencia a otro thread . La optimización puede ocasionalmente eliminar bucles vacíos.


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".


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.


La respuesta aquí no es trivial. Exactamente lo que sucede y lo que se entiende depende de muchas cosas. Para una comprensión básica de la coherencia / memoria del caché, quizás mis entradas recientes en el blog sean útiles:

Pero aparte de eso, déjame intentar responder algunas preguntas. En primer lugar, la siguiente instrucción tiene muchas esperanzas en cuanto a lo que se admite.

compare_swap( C& expected, C desired,
        memory_order success, memory_order failure )

Las arquitecturas no podrán implementar esto exactamente como lo solicitó. Cuando especifica memory_order, especifica cómo puede funcionar la reordenación. Para usar los términos de intel, especificará qué tipo de cercado desea, hay tres, la valla completa, la cerca de carga y la cerca de la tienda. El hecho de que desee una valla particular en esa operación no significa que sea compatible, en lo que espero que siempre vuelva a ser una valla completa.

Es probable que el compilador use la instrucción CMPXCHG para implementar la llamada. Si ha especificado algo más que relajado, marcará esto con un lock para indicar que la función debe ser atómica. Si esto es "libre de bloqueo" depende mucho de lo que está pensando en términos de un "bloqueo".

En términos de sincronización de memoria, debes entender cómo funciona la coherencia de caché (mi blog puede ayudar un poco). Las nuevas CPU utilizan una arquitectura ccNUMA (anteriormente SMP). Esencialmente, la "vista" en la memoria nunca se sale de sincronización. Las cercas utilizadas en el código no obligan a que se produzca ningún enrojecimiento per se. Si dos núcleos tienen la misma ubicación de memoria en caché en una línea de caché, uno se marcará como sucio y el otro se volverá a cargar según sea necesario. Una explicación muy simple para un proceso muy complejo

Para responder a su última pregunta, siempre debe usar la semántica de la memoria que lógicamente necesita para ser correcta. La mayoría de las arquitecturas no admitirán todas las combinaciones que use en su programa. Sin embargo, en muchos casos obtendrá excelentes optimizaciones, especialmente en los casos en que el pedido que solicitó está garantizado sin una valla (que es bastante común).

- Respuestas a algunos comentarios:

Debe distinguir entre lo que significa ejecutar una instrucción de escritura y escribir en una ubicación de memoria. Esto es lo que trato de explicar en mi blog. En el momento en que el "0" está comprometido con 0x100, todos los núcleos ven ese cero. Escribir enteros también es atómico, es decir, incluso sin un bloqueo, cuando escribe en una ubicación todos los núcleos tendrán inmediatamente ese valor si desean usarlo.

El problema es que para usar el valor que probablemente haya cargado en un registro primero, cualquier cambio en la ubicación después de eso obviamente no tocará el registro. Esta es la razón por la cual uno necesita mutexes a pesar de una memoria coherente de caché.

En cuanto a los reclamos contradictorios, generalmente verá todo tipo de reclamos. Si son contradictorios viene exactamente a lo que "ver" "cargar" significa "ejecutar" en el contexto. Si escribe "1" a 0x100, ¿significa eso que usted ejecutó la instrucción de escritura o la CPU realmente confirmó ese valor? La diferencia proviene de la reordenación. La CPU puede retrasar la escritura del "1", pero puede estar seguro de que en el momento en que finalmente confirma que "1" todos los núcleos lo ven. Las vallas controlan este orden.







c++ optimization loops c++11