Otimizando afastado um “while (1);” em C ++ 0x

Atualizado, veja abaixo!

Eu ouvi e li que o C ++ 0x permite que um compilador imprima “Olá” para o seguinte trecho

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

Aparentemente, tem algo a ver com encadeamentos e resources de otimização. Parece-me que isso pode surpreender muitas pessoas.

Alguém tem uma boa explicação de por que isso foi necessário para permitir? Para referência, o rascunho mais recente do C ++ 0x diz em 6.5/5

Um loop que, fora da instrução for-init, no caso de uma instrução for,

  • não faz chamadas para as funções de E / S da biblioteca e
  • não acessa ou modifica objects voláteis, e
  • não executa operações de synchronization (1.10) ou operações atômicas (Cláusula 29)

pode ser assumido pela implementação para terminar. [Nota: Isso se destina a permitir transformações do compilador, como a remoção de loops vazios, mesmo quando a terminação não pode ser comprovada. – nota final

Editar:

Este artigo perspicaz diz sobre esse texto dos Padrões

Infelizmente, as palavras “comportamento indefinido” não são usadas. No entanto, sempre que o padrão disser “o compilador pode assumir P”, está implícito que um programa que possui a propriedade not-P possui semântica indefinida.

Isso está correto, e o compilador tem permissão para imprimir “Bye” para o programa acima?


Há um tópico ainda mais perspicaz aqui , que é sobre uma mudança análoga ao C, iniciada pelo Guy que fez o artigo acima linkado. Entre outros fatos úteis, eles apresentam uma solução que parece se aplicar também ao C ++ 0x ( Update : Isso não funcionará mais com o n3225 – veja abaixo!)

 endless: goto endless; 

Um compilador não pode otimizar isso, parece, porque não é um loop, mas um salto. Outro cara resume a mudança proposta em C ++ 0x e C201X

Ao escrever um loop, o programador está afirmando que o loop faz algo com comportamento visível (executa E / S, acessa objects voláteis ou realiza operações de synchronization ou atômica) ou que, eventualmente, termina. Se eu violar essa suposição escrevendo um loop infinito sem efeitos colaterais, estou mentindo para o compilador, e o comportamento do meu programa é indefinido. (Se eu tiver sorte, o compilador pode me avisar sobre isso.) A linguagem não fornece (não fornece mais?) Uma maneira de expressar um loop infinito sem comportamento visível.


Atualização em 3.1.2011 com n3225: Comitê moveu o texto para 1.10 / 24 e diz

A implementação pode assumir que qualquer segmento acabará por fazer um dos seguintes procedimentos:

  • terminar,
  • fazer uma chamada para uma function de E / S da biblioteca,
  • acessar ou modificar um object volátil, ou
  • executar uma operação de synchronization ou uma operação atômica.

O truque do goto não funcionará mais!

Alguém tem uma boa explicação de por que isso foi necessário para permitir?

Sim, Hans Boehm fornece uma justificativa para isso em N1528: Por que o comportamento indefinido for loops infinitos? , embora este seja o documento WG14, o raciocínio também se aplica ao C ++ e o documento se refere tanto ao WG14 quanto ao WG21:

Como N1509 corretamente aponta, o rascunho atual essencialmente dá um comportamento indefinido a loops infinitos em 6.8.5p6. Uma questão importante para isso é permitir que o código se mova em um loop potencialmente sem terminação. Por exemplo, suponha que temos os loops a seguir, em que count e count2 são variables ​​globais (ou tiveram seus endereços escolhidos) e p é uma variável local cujo endereço não foi obtido:

 for (p = q; p != 0; p = p -> next) { ++count; } for (p = q; p != 0; p = p -> next) { ++count2; } 

Esses dois loops podem ser mesclados e substituídos pelo loop seguinte?

 for (p = q; p != 0; p = p -> next) { ++count; ++count2; } 

Sem a dispensação especial em 6.8.5p6 for loops infinitos, isso não seria permitido: se o primeiro loop não terminar porque q aponta para uma lista circular, o original nunca grava em count2. Assim, pode ser executado em paralelo com outro thread que acesse ou atualize o count2. Isso não é mais seguro com a versão transformada que acessa o count2 apesar do loop infinito. Assim, a transformação potencialmente introduz uma corrida de dados.

Em casos como esse, é muito improvável que um compilador seja capaz de provar a finalização do loop; ele teria que entender que q aponta para uma lista acíclica, que, acredito, está além da capacidade da maioria dos compiladores mainstream, e muitas vezes impossível sem a informação completa do programa.

As restrições impostas por loops de terminação não são uma restrição na otimização de loops de terminação para os quais o compilador não pode provar a finalização, bem como na otimização de loops realmente sem terminação. Os primeiros são muito mais comuns do que os últimos e, muitas vezes, mais interessantes para otimizar.

Claramente há também loops for-loops com uma variável de loop inteiro em que seria difícil para um compilador provar a terminação, e seria, portanto, difícil para o compilador reestruturar os loops sem o 6.8.5p6. Até algo parecido

 for (i = 1; i != 15; i += 2) 

ou

 for (i = 1; i < = 10; i += j) 

parece não trivial de lidar. (No primeiro caso, é necessária alguma teoria básica dos números para provar a terminação, no último caso, precisamos saber algo sobre os possíveis valores de j para fazê-lo. O envoltório para números inteiros sem sinal pode complicar ainda mais esse raciocínio. )

Esse problema parece se aplicar a quase todas as transformações de reestruturação de loop, incluindo as transformações de paralelização e otimização de cache do compilador, que provavelmente ganharão importância e já são importantes para o código numérico. Isso parece se transformar em um custo substancial para o benefício de ser capaz de escrever loops infinitos da maneira mais natural possível, especialmente porque a maioria de nós raramente escreve loops infinitos intencionalmente.

A principal diferença com C é que C11 fornece uma exceção para controlar expressões que são expressões constantes que diferem de C ++ e tornam seu exemplo específico bem definido em C11.

Para mim, a justificativa relevante é:

Isso se destina a permitir transformações do compilador, como a remoção de loops vazios, mesmo quando a terminação não pode ser comprovada.

Presumivelmente, isso ocorre porque provar a terminação mecanicamente é difícil , e a incapacidade de provar a terminação dificulta compiladores que poderiam fazer transformações úteis, como mover operações não dependentes de antes do loop para depois ou vice-versa, executando operações pós-loop em uma thread enquanto o loop é executado em outro e assim por diante. Sem essas transformações, um loop pode bloquear todos os outros threads enquanto aguardam o thread terminar o loop. (Eu uso “thread” livremente para significar qualquer forma de parallel processing, incluindo streams de instrução VLIW separados.)

EDIT: exemplo idiota:

 while (complicated_condition()) { x = complicated_but_externally_invisible_operation(x); } complex_io_operation(); cout < < "Results:" << endl; cout << x << endl; 

Aqui, seria mais rápido para um thread fazer o complex_io_operation enquanto o outro está fazendo todos os cálculos complexos no loop. Mas sem a cláusula que você citou, o compilador precisa provar duas coisas antes de poder fazer a otimização: 1) que complex_io_operation() não depende dos resultados do loop, e 2) que o loop terminará . Provar 1) é bem fácil, provando que 2) é o problema da parada. Com a cláusula, pode assumir que o loop termina e obtém um ganho de paralelização.

Também imagino que os projetistas consideraram que os casos em que ocorrem loops infinitos no código de produção são muito raros e geralmente são coisas como loops acionados por events que acessam E / S de alguma maneira. Como resultado, eles pessimiram o caso raro (loops infinitos) em favor de otimizar o caso mais comum (não-infinito, mas difícil de provar mecanicamente, não-infinito, loops).

Isso significa, no entanto, que os loops infinitos usados ​​nos exemplos de aprendizado sofrerão como resultado e aumentarão as pegadinhas no código iniciante. Eu não posso dizer que isso seja uma coisa boa.

EDIT: com relação ao artigo perspicaz você agora link, eu diria que "o compilador pode assumir X sobre o programa" é logicamente equivalente a "se o programa não satisfaz X, o comportamento é indefinido". Podemos mostrar isso da seguinte maneira: suponha que exista um programa que não satisfaça a propriedade X. Onde o comportamento desse programa seria definido? O Padrão só define o comportamento assumindo que a propriedade X é verdadeira. Embora o Padrão não declare explicitamente o comportamento indefinido, ele declarou indefinido por omissão.

Considere um argumento similar: "o compilador pode assumir que uma variável x só é designada para no máximo uma vez entre pontos de sequência" é equivalente a "designar a x mais de uma vez entre pontos de seqüência é indefinida".

Eu acho que a interpretação correta é aquela da sua edição: loops infinitos vazios são comportamentos indefinidos.

Eu não diria que é um comportamento particularmente intuitivo, mas essa interpretação faz mais sentido do que a alternativa, que o compilador é arbitrariamente permitido ignorar loops infinitos sem invocar o UB.

Se os loops infinitos forem UB, isso significa apenas que os programas que não terminam não são considerados significativos: de acordo com o C ++ 0x, eles não possuem semântica.

Isso faz uma certa quantidade de sentido também. Eles são um caso especial, em que vários efeitos colaterais não ocorrem mais (por exemplo, nada é retornado do main ), e várias otimizações do compilador são prejudicadas pela necessidade de preservar loops infinitos. Por exemplo, mover computações através do loop é perfeitamente válido se o loop não tiver efeitos colaterais, porque, eventualmente, o cálculo será executado em qualquer caso. Mas se o loop nunca terminar, não podemos reorganizar o código com segurança, porque podemos estar apenas alterando quais operações realmente são executadas antes que o programa seja interrompido. A menos que tratemos de um programa suspenso como UB, isso é.

Eu acho que isso é ao longo das linhas deste tipo de pergunta , que faz referência a outro segmento . A otimização pode ocasionalmente remover loops vazios.

A questão relevante é que o compilador tem permissão para reordenar o código cujos efeitos colaterais não entram em conflito. A surpreendente ordem de execução pode ocorrer mesmo se o compilador produzir código de máquina não finalizante para o loop infinito.

Eu acredito que esta é a abordagem correta. A especificação de linguagem define maneiras de impor a ordem de execução. Se você quiser um loop infinito que não pode ser reordenado, escreva isto:

 volatile int dummy_side_effect; while (1) { dummy_side_effect = 0; } printf("Never prints.\n"); 

Eu acho que a questão poderia ser melhor declarada, como “Se um pedaço de código posterior não depende de um pedaço de código anterior, e o pedaço de código anterior não tem efeitos colaterais em qualquer outra parte do sistema, a saída do compilador pode executar a parte posterior do código antes, depois ou misturada com a execução da primeira, mesmo se a primeira contiver loops, sem considerar quando ou se o código antigo seria realmente concluído.Por exemplo, o compilador poderia rewrite:

 void testfermat (int n)
 {
   inta = 1, b = 1, c = 1;
   while (pow (a, n) + pow (b, n)! = pow (c, n))
   {
     if (b> a) um ++;  mais se (c> b) {a = 1;  b ++};  else {a = 1;  b = 1;  c ++};
   }
   printf ("O resultado é");
   printf ("% d /% d /% d", a, b, c);
 }

Como

 void testfermat (int n)
 {
   if (fork_is_first_thread ())
   {
     inta = 1, b = 1, c = 1;
     while (pow (a, n) + pow (b, n)! = pow (c, n))
     {
       if (b> a) um ++;  mais se (c> b) {a = 1;  b ++};  else {a = 1;  b = 1;  c ++};
     }
     signal_other_thread_and_die ();
   }
   else // Segunda discussão
   {
     printf ("O resultado é");
     wait_for_other_thread ();
   }
   printf ("% d /% d /% d", a, b, c);
 }

Geralmente não é irracional, embora eu possa me preocupar 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 tornaria

   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 ();
   }
   outro
   {
     para (i = 0; num_reps> i; i ++)
       update_progress_bar (i);
     wait_for_other_thread ();
   }
   show_result (total);

Com uma CPU lidando com os cálculos e outra lidando com as atualizações da barra de progresso, a reescrita melhoraria a eficiência. Infelizmente, isso tornaria as atualizações da barra de progresso menos úteis do que deveriam ser.

Não é decidível para o compilador para casos não-triviais se é um loop infinito em tudo.

Em casos diferentes, pode acontecer que o seu otimizador atinja uma class de complexidade melhor para o seu código (por exemplo: O (n ^ 2) e você obtém O (n) ou O (1) após a otimização).

Portanto, include essa regra que não permite a remoção de um loop infinito no padrão C ++ tornaria impossível muitas otimizações. E a maioria das pessoas não quer isso. Eu acho que isso responde à sua pergunta.


Outra coisa: nunca vi nenhum exemplo válido em que você precise de um loop infinito que não faça nada.

O único exemplo de que eu ouvi falar foi um hack feio que realmente deveria ser resolvido de outra forma: era sobre sistemas embarcados onde a única maneira de acionar um reset era congelar o dispositivo para que o watchdog o reiniciasse automaticamente.

Se você conhece algum exemplo válido / bom onde você precisa de um loop infinito que não faz nada, por favor me diga.

Eu acho que vale a pena ressaltar que loops que seriam infinitos, exceto pelo fato de que eles interagem com outros threads através de variables ​​não-voláteis, não-sincronizadas, podem agora produzir um comportamento incorreto com um novo compilador.

Eu, em outras palavras, deixo seus globals voláteis – assim como os argumentos passados ​​para tal loop via pointer / reference.