c++ - Loop com tempo de execução zero




optimization execution-time (3)

É possível ter um loop com tempo de execução zero? Eu acho que mesmo um loop vazio deve ter um tempo de execução, pois há uma sobrecarga associada a ele.


O compilador não é obrigado a avaliar a expressão, ou parte de uma expressão, que não possui efeitos colaterais e cujo resultado é descartado.

Harbison e Steele, C: Um Manual de Referência


Além das otimizações do compilador, algumas arquiteturas de CPU, particularmente DSPs, têm zero loop overhead , pelo qual um loop com um número fixo de iterações é efetivamente otimizado pelo hardware, veja, por exemplo, http://www.dsprelated.com/showmessage/20681/1.php


Sim, sob a regra do tipo " como se", o compilador é obrigado apenas a emular o comportamento observável do código; portanto, se você tiver um loop que não tenha nenhum comportamento observável, ele poderá ser completamente otimizado e, portanto, terá efetivamente zero tempo de execução. .

Exemplos

Por exemplo, o seguinte código:

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

compilado com o gcc 4.9 usando o sinalizador -O3 basicamente reduz para o seguinte ( veja ao vivo ):

main:
  xorl  %eax, %eax  #
  ret

Praticamente todas as otimizações permitidas se enquadram na regra como se , a única exceção que eu conheço é a cópia elison, que pode afetar o comportamento observável.

Alguns outros exemplos incluem a eliminação de código morto, que pode remover o código que o compilador pode provar nunca será executado. Por exemplo, embora o loop a seguir realmente contenha um efeito colateral, ele pode ser otimizado, pois podemos provar que nunca será executado ( veja ao 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 ;
    }
  }
}

O loop otimizará o mesmo que no exemplo anterior. Um exemplo mais interessante seria o caso em que um cálculo em um loop pode ser deduzido em uma constante, evitando a necessidade de um loop ( não tendo certeza de qual categoria de otimização se enquadra ), por exemplo:

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

pode ser otimizado para ( veja ao vivo ):

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

Podemos ver que não há loop envolvido.

Onde está como se Regra coberta no padrão

A regra como se é abordada no rascunho da seção 5.1.2.3 norma C99, que diz:

Na máquina abstrata, todas as expressões são avaliadas conforme especificado pela semântica. Uma implementação real não precisa avaliar parte de uma expressão se puder deduzir que seu valor não é usado e que nenhum efeito colateral necessário é produzido (incluindo os causados ​​pela chamada de uma função ou pelo acesso a um objeto volátil).

A regra como se também se aplica ao C ++, o gcc também produzirá o mesmo resultado no modo C ++. O rascunho do padrão C ++ cobre isso na seção 1.9 Execução do programa :

As descrições semânticas nesta Norma definem uma máquina abstrata não-determinística parametrizada. Esta Norma não impõe requisitos à estrutura de implementações em conformidade. Em particular, eles não precisam copiar ou emular a estrutura da máquina abstrata. Em vez disso, implementações conformes são necessárias para emular (apenas) o comportamento observável da máquina abstrata, conforme explicado abaixo.5





as-if