c++ - tiempo - sentencia for

Bucle con un tiempo de ejecución cero

Question

¿Es posible tener un ciclo que tenga un tiempo de ejecución cero? Creo que incluso un ciclo vacío debería tener un tiempo de ejecución ya que hay una sobrecarga asociada a él.

Answer 1

El compilador no está obligado a evaluar la expresión, o una parte de una expresión, que no tiene efectos secundarios y cuyo resultado se descarta.

Harbison y Steele, C: Un manual de referencia

Answer 2

Además de las optimizaciones del compilador, algunas arquitecturas de CPU, particularmente los DSP, tienen cero bucle de bucle , por lo que el hardware optimiza de forma efectiva un bucle con un número fijo de iteraciones, véase, por ejemplo, http://www.dsprelated.com/showmessage/20681/1.php

Answer 3

Sí, bajo la regla de si-si el compilador solo está obligado a emular el comportamiento observable del código, por lo que si tiene un bucle que no tiene ningún comportamiento observable, entonces puede optimizarse completamente y, por lo tanto, tendrá efectivamente cero tiempo de ejecución .

Ejemplos

Por ejemplo, el siguiente código:

int main()
{
  int j = 0 ;
  for( int i = 0; i < 10000; ++i )
  {
    ++j ;
  }
}

compilado con gcc 4.9 usando la bandera -O3 básicamente termina reduciéndose a lo siguiente ( verlo en vivo ):

main:
  xorl  %eax, %eax  #
  ret

Prácticamente todas las optimizaciones permitidas caen bajo la regla de si-si , la única excepción de la que tengo conocimiento es la elisión de copia, que puede afectar el comportamiento observable.

Algunos otros ejemplos incluirían la eliminación del código muerto que puede eliminar el código que el compilador puede probar que nunca se ejecutará. Por ejemplo, aunque el siguiente ciclo sí contiene un efecto secundario, se puede optimizar ya que podemos probar que nunca se ejecutará ( véalo en vivo ):

#include <stdio.h>

int main()
{
  int j = 0 ;
  if( false ) // The loop will never execute
  {
    for( int i = 0; i < 10000; ++i )
    {
      printf( "%d/n", j ) ;
      ++j ;
    }
  }
}

El ciclo optimizará lo mismo que el ejemplo anterior. Un ejemplo más interesante sería el caso en el que un cálculo en un ciclo se puede deducir en una constante, evitando así la necesidad de un ciclo ( no estoy seguro de en qué categoría de optimización se trata ), por ejemplo:

int j = 0 ;
for( int i = 0; i < 10000; ++i )
{
  ++j ;
}
printf( "%d/n", j ) ;

puede optimizarse para ( verlo en vivo ):

movl    $10000, %esi    #,
movl    $.LC0, %edi #,
xorl    %eax, %eax  #
call    printf  #

Podemos ver que no hay lazo involucrado.

Dónde está la regla de "si-si" cubierta en la norma

La regla de si-si está cubierta en el borrador de la sección estándar C99 5.1.2.3 Ejecución del programa que dice:

En la máquina abstracta, todas las expresiones se evalúan según lo especificado por la semántica. Una implementación real no necesita evaluar parte de una expresión si puede deducir que su valor no se usa y que no se producen efectos secundarios necesarios (incluidos los causados ​​por llamar a una función o acceder a un objeto volátil).

La regla de si-si también se aplica a C ++, gcc producirá el mismo resultado en el modo C ++ también. El borrador del estándar de C ++ cubre esto en la sección 1.9 Ejecución del programa :

Las descripciones semánticas en este estándar internacional definen una máquina abstracta no determinista parametrizada. Esta Norma Internacional no exige ningún requisito sobre la estructura de implementaciones conformes. En particular, no necesitan copiar o emular la estructura de la máquina abstracta. Por el contrario, se requieren implementaciones conformes para emular (solo) el comportamiento observable de la máquina abstracta como se explica a continuación.5

Answer 4

Sí, si el compilador determina que el bucle es un código muerto (nunca se ejecutará), entonces no generará código para él. Ese bucle tendrá 0 tiempo de ejecución, aunque estrictamente hablando no existe en el nivel de código de máquina.