Por que o compilador não pode (ou não) otimizar um loop de adição previsível em uma multiplicação?

133

Esta é uma pergunta que veio à mente ao ler a brilhante resposta de Mysticial à pergunta: por que é mais rápido processar uma matriz classificada do que uma matriz não classificada ?

Contexto para os tipos envolvidos:

const unsigned arraySize = 32768;
int data[arraySize];
long long sum = 0;

Em sua resposta, ele explica que o Intel Compiler (ICC) otimiza isso:

for (int i = 0; i < 100000; ++i)
    for (int c = 0; c < arraySize; ++c)
        if (data[c] >= 128)
            sum += data[c];

... em algo equivalente a isso:

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

O otimizador está reconhecendo que eles são equivalentes e, portanto, está trocando os loops , movendo o ramo para fora do loop interno. Muito esperto!

Mas por que não faz isso?

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000 * data[c];

Esperemos que Mysticial (ou qualquer outra pessoa) possa dar uma resposta igualmente brilhante. Eu nunca aprendi sobre as otimizações discutidas nessa outra pergunta antes, então estou muito agradecido por isso.

jhabbott
fonte
14
Isso é algo que provavelmente apenas a Intel sabe. Não sei em que ordem ele executa seus passes de otimização. E, aparentemente, ele não executa uma passagem de colapso de loop após o intercâmbio de loop.
Mysticial
7
Essa otimização é válida apenas se os valores contidos na matriz de dados forem imutáveis. Por exemplo, se o são memória mapeada para um dispositivo de entrada / saída de cada vez que você ler dados [0] irá produzir um valor diferente ...
Thomas CG de Vilhena
2
Que tipo de dados é esse, inteiro ou ponto flutuante? A adição repetida no ponto flutuante fornece resultados muito diferentes da multiplicação.
precisa
6
@ Thomas: Se os dados fossem volatile, o intercâmbio de loop também seria uma otimização inválida.
precisa
3
O GNAT (compilador Ada com GCC 4.6) não alterna os loops no O3, mas se os loops forem alterados, ele será convertido em uma multiplicação.
Prosfilaes

Respostas:

105

O compilador geralmente não pode transformar

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

para dentro

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000 * data[c];

porque o último pode levar ao estouro de números inteiros assinados onde o primeiro não. Mesmo com um comportamento de empacotamento garantido para o estouro de números inteiros de complemento de dois assinados, ele alteraria o resultado (se data[c]for 30000, o produto se tornaria -1294967296para os ints de 32 bits típicos com empacotamento, enquanto 100000 vezes adicionando 30000 a sum, se isso não exceda, aumente sumem 3000000000). Observe que o mesmo vale para quantidades não assinadas, com números diferentes, o excesso de quantidade 100000 * data[c]normalmente introduziria um módulo de redução2^32 que não deve aparecer no resultado final.

Poderia transformá-lo em

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000LL * data[c];  // resp. 100000ull

embora, como sempre, long longseja suficientemente maior queint .

Por que não faz isso, não sei dizer, acho que foi o que Mysticial disse : "aparentemente, ele não executa um passe de colapso de loop após intercâmbio de loop".

Observe que o próprio intercâmbio de loop geralmente não é válido (para números inteiros assinados), pois

for (int c = 0; c < arraySize; ++c)
    if (condition(data[c]))
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

pode levar ao estouro, onde

for (int i = 0; i < 100000; ++i)
    for (int c = 0; c < arraySize; ++c)
        if (condition(data[c]))
            sum += data[c];

não faria. É kosher aqui, pois a condição garante que todosdata[c] que adicionados tenham o mesmo sinal; portanto, se um transbordar, os dois terão.

Eu não teria muita certeza de que o compilador levasse isso em consideração (@Mysticial, você poderia tentar com uma condição semelhante à data[c] & 0x80que pode ser verdadeira para valores positivos e negativos?). Os compiladores fizeram otimizações inválidas (por exemplo, há alguns anos, eu tive uma ICC (11.0, iirc) usando uma conversão assinado de 32 bits-int-dupla no local 1.0/nonde nestava um unsigned int. Era duas vezes mais rápido que o do gcc Mas errado, muitos valores eram maiores que 2^31, ops.).

Daniel Fischer
fonte
4
Lembro-me de uma versão do compilador MPW que adicionou uma opção para permitir quadros de pilha maiores que 32K [versões anteriores eram limitadas usando o endereçamento @ A7 + int16 para variáveis ​​locais]. Ele acertou tudo para quadros de pilha abaixo de 32K ou mais de 64K, mas para um quadro de pilha de 40K ele usaria ADD.W A6,$A000, esquecendo que as operações de palavras com registradores de endereço estendem a palavra para 32 bits antes da adição. Demorou algum tempo para solucionar problemas, já que a única coisa que o código fez entre isso ADDe a próxima vez que retirou o A6 da pilha foi restaurar os registros dos chamadores que ele salvou nesse quadro ... #
31813
3
... e o único registro com o qual o chamador se importava era o endereço [constante de tempo de carregamento] de uma matriz estática. O compilador sabia que o endereço da matriz era salvo em um registro para que ele pudesse otimizar com base nisso, mas o depurador simplesmente sabia o endereço de uma constante. Assim, antes de uma declaração, MyArray[0] = 4;eu poderia verificar o endereço de MyArraye olhar para esse local antes e depois da declaração executada; isso não mudaria. Código era algo parecido move.B @A3,#4e A3 deveria sempre apontar para MyArrayqualquer momento em que a instrução fosse executada, mas não. Diversão.
supercat
então por que o clang executa esse tipo de otimização?
Jason S
O compilador pode executar essa reescrita em suas representações intermediárias internas, porque é permitido ter um comportamento menos indefinido em suas representações intermediárias internas.
User253751 6/01
48

Esta resposta não se aplica ao caso específico vinculado, mas se aplica ao título da pergunta e pode ser interessante para futuros leitores:

Devido à precisão finita, a adição repetida de ponto flutuante não é equivalente à multiplicação . Considerar:

float const step = 1e-15;
float const init = 1;
long int const count = 1000000000;

float result1 = init;
for( int i = 0; i < count; ++i ) result1 += step;

float result2 = init;
result2 += step * count;

cout << (result1 - result2);

Demo

Ben Voigt
fonte
10
Esta não é uma resposta para a pergunta. Apesar de informações interessantes (e um conhecimento obrigatório para qualquer programador de C / C ++), este não é um fórum e não pertence a este.
orlp
30
@ nightcracker: O objetivo declarado do StackOverflow é criar uma biblioteca pesquisável de respostas úteis para futuros usuários. E esta é uma resposta para a pergunta feita ... acontece que há algumas informações não declaradas que fazem com que essa resposta não se aplique ao pôster original. Ainda pode ser aplicado a outros com a mesma pergunta.
precisa
12
É poderia ser uma resposta para a pergunta título , mas não a pergunta, não.
orlp
7
Como eu disse, é uma informação interessante . No entanto, ainda me parece errado que não bene a resposta principal da pergunta não responda à pergunta como está agora . Simplesmente não é por isso que o Intel Compiler decidiu não otimizar, basta.
orlp
4
@ nightcracker: Parece-me errado também que esta é a resposta principal. Espero que alguém poste uma resposta realmente boa para o caso inteiro que ultrapassa este na pontuação. Infelizmente, não acho que exista uma resposta para "não posso" para o caso inteiro, porque a transformação seria legal, então ficamos com "por que não", que realmente afeta o " muito próximo "motivo próximo, porque é peculiar a uma versão específica do compilador. A pergunta que respondi é a mais importante, a IMO.
precisa
6

O compilador contém várias passagens que fazem a otimização. Geralmente, em cada passagem, é feita uma otimização nas instruções ou otimizações de loop. No momento, não há modelo que faça uma otimização do corpo do loop com base nos cabeçalhos do loop. Isso é difícil de detectar e menos comum.

A otimização realizada foi o movimento invariante do código. Isso pode ser feito usando um conjunto de técnicas.

Cavaleiro
fonte
4

Bem, eu acho que alguns compiladores podem fazer esse tipo de otimização, assumindo que estamos falando sobre aritmética de números inteiros.

Ao mesmo tempo, alguns compiladores podem se recusar a fazê-lo, porque substituir a adição repetitiva pela multiplicação pode alterar o comportamento de estouro do código. Para tipos inteiros não assinados, não deve fazer diferença, pois o comportamento do estouro é totalmente especificado pelo idioma. Mas para os assinados, pode ser (provavelmente não na plataforma de complemento do 2). É verdade que o estouro assinado realmente leva a um comportamento indefinido em C, o que significa que seria perfeitamente bom ignorar completamente a semântica do estouro, mas nem todos os compiladores são corajosos o suficiente para fazer isso. Muitas vezes, recebe muitas críticas da multidão "C é apenas uma linguagem assembly de nível superior". (Lembre-se do que aconteceu quando o GCC introduziu otimizações com base na semântica de alias estrito?)

Historicamente, o GCC tem se mostrado um compilador que tem o necessário para executar etapas tão drásticas, mas outros compiladores podem preferir manter o comportamento "pretendido pelo usuário", mesmo que não seja definido pelo idioma.

Formiga
fonte
Prefiro saber se estou acidentalmente dependendo de um comportamento indefinido, mas acho que o compilador não tem como saber, pois o estouro seria um problema de tempo de execução: /
jhabbott 30/12/12
2
@ jhabbott: se o estouro ocorrer, haverá um comportamento indefinido. Se o comportamento é definido é desconhecido até o tempo de execução (assumindo que os números sejam inseridos no tempo de execução): P.
orlp
3

Agora - pelo menos, o clang :

long long add_100k_signed(int *data, int arraySize)
{
    long long sum = 0;

    for (int c = 0; c < arraySize; ++c)
        if (data[c] >= 128)
            for (int i = 0; i < 100000; ++i)
                sum += data[c];
    return sum;
}

compila com -O1 para

add_100k_signed:                        # @add_100k_signed
        test    esi, esi
        jle     .LBB0_1
        mov     r9d, esi
        xor     r8d, r8d
        xor     esi, esi
        xor     eax, eax
.LBB0_4:                                # =>This Inner Loop Header: Depth=1
        movsxd  rdx, dword ptr [rdi + 4*rsi]
        imul    rcx, rdx, 100000
        cmp     rdx, 127
        cmovle  rcx, r8
        add     rax, rcx
        add     rsi, 1
        cmp     r9, rsi
        jne     .LBB0_4
        ret
.LBB0_1:
        xor     eax, eax
        ret

Estouro inteiro não tem nada a ver com isso; se houver um excesso de número inteiro que cause comportamento indefinido, isso poderá ocorrer nos dois casos. Aqui está o mesmo tipo de função usando em intvez delong :

int add_100k_signed(int *data, int arraySize)
{
    int sum = 0;

    for (int c = 0; c < arraySize; ++c)
        if (data[c] >= 128)
            for (int i = 0; i < 100000; ++i)
                sum += data[c];
    return sum;
}

compila com -O1 para

add_100k_signed:                        # @add_100k_signed
        test    esi, esi
        jle     .LBB0_1
        mov     r9d, esi
        xor     r8d, r8d
        xor     esi, esi
        xor     eax, eax
.LBB0_4:                                # =>This Inner Loop Header: Depth=1
        mov     edx, dword ptr [rdi + 4*rsi]
        imul    ecx, edx, 100000
        cmp     edx, 127
        cmovle  ecx, r8d
        add     eax, ecx
        add     rsi, 1
        cmp     r9, rsi
        jne     .LBB0_4
        ret
.LBB0_1:
        xor     eax, eax
        ret
Jason S
fonte
2

Há uma barreira conceitual para esse tipo de otimização. Os autores do compilador investem muito em redução de força - por exemplo, substituindo multiplicações por adições e trocas. Eles se acostumam a pensar que as multiplicações são ruins. Portanto, um caso em que alguém deveria seguir o outro caminho é surpreendente e contra-intuitivo. Então, ninguém pensa em implementá-lo.

zwol
fonte
3
Substituir um loop por um cálculo em forma fechada também reduz a força, não é?
precisa
Formalmente, sim, suponho, mas nunca ouvi ninguém falar dessa maneira. (Eu sou um pouco fora de data na literatura, no entanto.)
Zwol
1

As pessoas que desenvolvem e mantêm compiladores têm uma quantidade limitada de tempo e energia para gastar em seu trabalho; portanto, geralmente desejam se concentrar no que seus usuários mais gostam: transformar código bem escrito em código rápido. Eles não querem gastar seu tempo tentando encontrar maneiras de transformar código tolo em código rápido - é para isso que serve a revisão de código. Em uma linguagem de alto nível, pode haver um código "bobo" que expressa uma idéia importante, valendo a pena o tempo dos desenvolvedores para fazer isso rapidamente - por exemplo, o desmatamento de atalho e a fusão de fluxos permitem que os programas Haskell estruturem em torno de certos tipos de preguiçoso estruturas de dados produzidas para serem compiladas em loops estreitos que não alocam memória. Mas esse tipo de incentivo simplesmente não se aplica a transformar a adição em loop em multiplicação. Se você quer que seja rápido,

dfeuer
fonte