Otimizando um "tempo (1)"; em C ++ 0x

Atualizado, veja abaixo!

Ouvi e li que o C ++ 0x permite que um compilador imprima "Olá" para o seguinte trecho

#include <iostream>

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

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

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

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

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

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

Editar:

Este artigo esclarecedor diz sobre o texto dos Padrões

Infelizmente, as palavras "comportamento indefinido" não são usadas. No entanto, sempre que o padrão diz "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 pode imprimir "Tchau" para o programa acima?

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

endless:
  goto endless;

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

Ao escrever um loop, o programador está afirmando quer que o loop faz algo com o comportamento visível (executa E / S, acessa objetos voláteis, ou sincronização executa ou operações atômicas), ou que, eventualmente, termina. Se eu violar essa suposição escrevendo um loop infinito sem efeitos colaterais, minto para o compilador e o comportamento do meu programa é indefinido. (Se eu tiver sorte, o compilador poderá me avisar.) 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: o Comitê mudou o texto para 1.10 / 24 e diz

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

• terminar,
• faça uma chamada para uma função de E / S da biblioteca,
• acessar ou modificar um objeto volátil, ou
• executar uma operação de sincronização ou uma operação atômica.

O gototruque não vai mais funcionar!

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

Sim, Hans Boehm fornece uma justificativa para isso no N1528: Por que comportamento indefinido para loops infinitos? , embora este seja o documento do WG14, a lógica se aplica também ao C ++ e o documento se refere ao WG14 e WG21:

Como o N1509 corretamente aponta, o rascunho atual basicamente oferece um comportamento indefinido a loops infinitos em 6.8.5p6. Uma questão importante para fazer isso é que ele permite que o código se mova através de um loop potencialmente não terminável. Por exemplo, suponha que tenhamos os seguintes loops, em que count e count2 são variáveis ​​globais (ou tiveram seu endereço obtido) ep é uma variável local, cujo endereço não foi utilizado:

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

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

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

Sem a dispensação especial em 6.8.5p6 para 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, poderia ser executado em paralelo com outro encadeamento que acessa ou atualiza o count2. Isso não é mais seguro com a versão transformada, que acessa 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 o encerramento do loop; teria que entender que q aponta para uma lista acíclica, que acredito estar além da capacidade da maioria dos compiladores convencionais, e geralmente impossível sem informações completas do programa.

As restrições impostas pelos loops não termináveis ​​são uma restrição à otimização dos loops finais, para os quais o compilador não pode provar a finalização, bem como à otimização dos loops realmente não finais. Os primeiros são muito mais comuns que os segundos e, muitas vezes, mais interessantes para otimizar.

Claramente, existem também for-loops com uma variável de loop inteiro na qual seria difícil para um compilador provar a terminação e, portanto, seria difícil para o compilador reestruturar loops sem 6.8.5p6. Mesmo algo como

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. A quebra automática de números inteiros não assinados pode complicar ainda mais alguns desses raciocínios. )

Esse problema parece se aplicar a quase todas as transformações de reestruturação de loop, incluindo paralelismo de compilador e otimização de cache, as quais provavelmente ganharão importância e já são importantes para o código numérico. Parece provável que isso se transforme em um custo substancial pelo benefício de poder gravar loops infinitos da maneira mais natural possível, especialmente porque a maioria de nós raramente escreve loops infinitamente intencionais.

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

Para mim, a justificativa relevante é:

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

Presumivelmente, isso ocorre porque provar a terminação mecanicamente é difícil , e a incapacidade de provar a terminação dificulta os 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 um thread enquanto o loop é executado em outro e assim por diante. Sem essas transformações, um loop pode bloquear todos os outros encadeamentos enquanto eles esperam que um encadeamento termine o referido loop. (Eu uso "thread" livremente para significar qualquer forma de processamento paralelo, incluindo fluxos de instruções 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_operationmesmo 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 fazer a otimização: 1) que complex_io_operation()não depende dos resultados do loop e 2) que o loop será encerrado . A prova 1) é bem fácil, a prova 2) é o problema da parada. Com a cláusula, pode assumir que o loop termina e obter uma vitória 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 como loops controlados por eventos que acessam a E / S de alguma maneira. Como resultado, eles pessimizaram o caso raro (loops infinitos) em favor da otimização do caso mais comum (não-infinito, mas difícil de provar mecanicamente, loops não-infinitos).

No entanto, isso significa que loops infinitos usados ​​em exemplos de aprendizado sofrerão como resultado e aumentarão as pegadinhas no código para iniciantes. Não posso dizer que isso é uma coisa totalmente boa.

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

Considere um argumento semelhante: "o compilador pode assumir que uma variável x é atribuída apenas no máximo uma vez entre os pontos de sequência" é equivalente a "atribuir x mais de uma vez entre os pontos de sequência é indefinida".

Eu acho que a interpretação correta é a da sua edição: loops infinitos vazios são um comportamento indefinido.

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

Se loops infinitos forem UB, isso significa apenas que programas não termináveis ​​não são considerados significativos: de acordo com o C ++ 0x, eles não têm semântica.

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

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

O problema relevante é que o compilador pode reordenar códigos cujos efeitos colaterais não entrem em conflito. A ordem surpreendente de execução pode ocorrer mesmo que o compilador produza um código de máquina não-final para o loop infinito.

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

volatile int dummy_side_effect;

while (1) {
    dummy_side_effect = 0;
}

printf("Never prints.\n");

Eu acho que a questão talvez possa ser melhor declarada, como "Se um código posterior não depender de um código anterior e o código anterior não tiver efeitos colaterais em nenhuma outra parte do sistema, a saída do compilador pode executar o trecho de código posterior antes, depois ou misturado à execução do anterior, mesmo que o primeiro contenha loops, sem levar em consideração quando ou se o código anterior seria realmente concluído.Por exemplo, o compilador pode reescrever:

void testfermat (int n)
{
  int a = 1, b = 1, c = 1;
  while (pow (a, n) + pow (b, n)! = pow (c, n))
  {
    se (b> a) a ++; caso contrário, se (c> b) {a = 1; b ++}; mais {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 ())
  {
    int a = 1, b = 1, c = 1;
    while (pow (a, n) + pow (b, n)! = pow (c, n))
    {
      se (b> a) a ++; caso contrário, se (c> b) {a = 1; b ++}; mais {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 com isso:

  total int = 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

  total int = 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);

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

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

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

Portanto, incluir uma regra que não permita a remoção de um loop infinito no padrão C ++ tornaria muitas otimizações impossíveis. E a maioria das pessoas não quer isso. Eu acho que isso responde bastante à 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 que ouvi foi sobre um truque feio que realmente deveria ser resolvido de outra forma: tratava-se de sistemas embarcados em que a única maneira de acionar uma redefinição era congelar o dispositivo para que o cão de guarda o reinicias automaticamente.

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

Eu acho que vale ressaltar que os loops que seriam infinitos, exceto pelo fato de que eles interagem com outros threads por meio de variáveis ​​não voláteis e não sincronizadas, agora podem gerar comportamento incorreto com um novo compilador.

Em outras palavras, torne seus globais voláteis - assim como os argumentos passados ​​para esse loop via ponteiro / referência.