Em C ++, devo me preocupar em armazenar variáveis ​​em cache ou deixar que o compilador faça a otimização? (Aliasing)

Considere o seguinte código ( pé do tipo unsigned char*e bitmap->widthé de algum tipo inteiro, exatamente que é desconhecido e depende de qual versão de alguma biblioteca externa estamos usando):

for (unsigned x = 0;  x < static_cast<unsigned>(bitmap->width);  ++x)
{
    *p++ = 0xAA;
    *p++ = 0xBB;
    *p++ = 0xCC;
}

_{Vale a pena otimizá-lo [..]}

Pode haver um caso em que isso possa produzir resultados mais eficientes por escrito:

unsigned width(static_cast<unsigned>(bitmap->width));
for (unsigned x = 0;  x < width;  ++x)
{
    *p++ = 0xAA;
    *p++ = 0xBB;
    *p++ = 0xCC;
}

... ou isso é trivial para o compilador otimizar?

_{O que você considera um código "melhor"?}

_{Nota do editor (Ike): para aqueles que estão se perguntando sobre o texto tachado, a pergunta original, conforme formulada, estava perigosamente perto de um território fora do tópico e estava muito perto de ser fechada, apesar do feedback positivo. Estes foram eliminados. No entanto, por favor, não puna os respondentes que abordaram essas seções contundentes da pergunta.}

À primeira vista, pensei que o compilador poderia gerar assembly equivalente para ambas as versões com sinalizadores de otimização ativados. Quando verifiquei, fiquei surpreso ao ver o resultado:

Fonte unoptimized.cpp

nota: este código não deve ser executado.

struct bitmap_t
{
    long long width;
} bitmap;

int main(int argc, char** argv)
{
    for (unsigned x = 0 ; x < static_cast<unsigned>(bitmap.width) ; ++x)
    {
        argv[x][0] = '\0';
    }
    return 0;
}

Fonte optimized.cpp

nota: este código não deve ser executado.

struct bitmap_t
{
    long long width;
} bitmap;

int main(int argc, char** argv)
{
    const unsigned width = static_cast<unsigned>(bitmap.width);
    for (unsigned x = 0 ; x < width ; ++x)
    {
        argv[x][0] = '\0';
    }
    return 0;
}

Compilação

• $ g++ -s -O3 unoptimized.cpp
• $ g++ -s -O3 optimized.cpp

Montagem (unoptimized.s)

    .file   "unoptimized.cpp"
    .text
    .p2align 4,,15
.globl main
    .type   main, @function
main:
.LFB0:
    .cfi_startproc
    .cfi_personality 0x3,__gxx_personality_v0
    movl    bitmap(%rip), %eax
    testl   %eax, %eax
    je  .L2
    xorl    %eax, %eax
    .p2align 4,,10
    .p2align 3
.L3:
    mov %eax, %edx
    addl    $1, %eax
    movq    (%rsi,%rdx,8), %rdx
    movb    $0, (%rdx)
    cmpl    bitmap(%rip), %eax
    jb  .L3
.L2:
    xorl    %eax, %eax
    ret
    .cfi_endproc
.LFE0:
    .size   main, .-main
.globl bitmap
    .bss
    .align 8
    .type   bitmap, @object
    .size   bitmap, 8
bitmap:
    .zero   8
    .ident  "GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-16)"
    .section    .note.GNU-stack,"",@progbits

Montagem (otimizado.s)

    .file   "optimized.cpp"
    .text
    .p2align 4,,15
.globl main
    .type   main, @function
main:
.LFB0:
    .cfi_startproc
    .cfi_personality 0x3,__gxx_personality_v0
    movl    bitmap(%rip), %eax
    testl   %eax, %eax
    je  .L2
    subl    $1, %eax
    leaq    8(,%rax,8), %rcx
    xorl    %eax, %eax
    .p2align 4,,10
    .p2align 3
.L3:
    movq    (%rsi,%rax), %rdx
    addq    $8, %rax
    cmpq    %rcx, %rax
    movb    $0, (%rdx)
    jne .L3
.L2:
    xorl    %eax, %eax
    ret
    .cfi_endproc
.LFE0:
    .size   main, .-main
.globl bitmap
    .bss
    .align 8
    .type   bitmap, @object
    .size   bitmap, 8
bitmap:
    .zero   8
    .ident  "GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-16)"
    .section    .note.GNU-stack,"",@progbits

diferença

$ diff -uN unoptimized.s optimized.s
--- unoptimized.s   2015-11-24 16:11:55.837922223 +0000
+++ optimized.s 2015-11-24 16:12:02.628922941 +0000
@@ -1,4 +1,4 @@
-   .file   "unoptimized.cpp"
+   .file   "optimized.cpp"
    .text
    .p2align 4,,15
 .globl main
@@ -10,16 +10,17 @@
    movl    bitmap(%rip), %eax
    testl   %eax, %eax
    je  .L2
+   subl    $1, %eax
+   leaq    8(,%rax,8), %rcx
    xorl    %eax, %eax
    .p2align 4,,10
    .p2align 3
 .L3:
-   mov %eax, %edx
-   addl    $1, %eax
-   movq    (%rsi,%rdx,8), %rdx
+   movq    (%rsi,%rax), %rdx
+   addq    $8, %rax
+   cmpq    %rcx, %rax
    movb    $0, (%rdx)
-   cmpl    bitmap(%rip), %eax
-   jb  .L3
+   jne .L3
 .L2:
    xorl    %eax, %eax
    ret

O assembly gerado para a versão otimizada realmente carrega ( lea) a widthconstante, ao contrário da versão não otimizada que calcula o widthdeslocamento em cada iteração ( movq).

Quando eu tiver tempo, eventualmente postarei alguns benchmarks sobre isso. Boa pergunta.

Na verdade, não há informações suficientes em seu snippet de código para ser capaz de dizer, e a única coisa que posso pensar é em aliasing. Do nosso ponto de vista, é bastante claro que você não quer pe bitmapapontar para o mesmo local na memória, mas o compilador não sabe disso e (porque pé do tipo char*) o compilador tem que fazer esse código funcionar mesmo que pebitmap sobrepõem.

Isso significa que, neste caso, se o loop muda bitmap->widthatravés do ponteiro, pentão isso deve ser visto ao relerbitmap->width mais tarde, o que por sua vez significa que armazená-lo em uma variável local seria ilegal.

Dito isso, acredito que alguns compiladores às vezes geram duas versões do mesmo código (vi evidências circunstanciais disso, mas nunca busquei informações diretamente sobre o que o compilador está fazendo neste caso) e verificam rapidamente se os ponteiros alias e executar o código mais rápido se determinar que está tudo bem.

Dito isso, mantenho meu comentário sobre simplesmente medir o desempenho das duas versões, meu dinheiro está em não ver qualquer diferença de desempenho consistente entre as duas versões do código.

Na minha opinião, perguntas como essas são aceitáveis ​​se seu objetivo é aprender sobre teorias e técnicas de otimização de compiladores, mas é uma perda de tempo (uma micro-otimização inútil) se seu objetivo final aqui é fazer o programa rodar mais rápido.

Ok, pessoal, então eu medi, com GCC -O3(usando GCC 4.9 no Linux x64).

Acontece que a segunda versão é 54% mais rápida!

Então, eu acho que o aliasing é a coisa, eu não tinha pensado nisso.

[Editar]

Tentei novamente a primeira versão com todos os ponteiros definidos com __restrict__e os resultados são os mesmos. Estranho .. Ou o aliasing não é o problema ou, por algum motivo, o compilador não o otimiza bem, mesmo com __restrict__.

[Editar 2]

Ok, acho que consegui provar que o aliasing é o problema. Repeti meu teste original, desta vez usando uma matriz em vez de um ponteiro:

const std::size_t n = 0x80000000ull;
bitmap->width = n;
static unsigned char d[n*3];
std::size_t i=0;
for (unsigned x = 0;  x < static_cast<unsigned>(bitmap->width);  ++x)
{
    d[i++] = 0xAA;
    d[i++] = 0xBB;
    d[i++] = 0xCC;
}

E medido (teve que usar "-mcmodel = large" para vinculá-lo). Então eu tentei:

const std::size_t n = 0x80000000ull;
bitmap->width = n;
static unsigned char d[n*3];
std::size_t i=0;
unsigned width(static_cast<unsigned>(bitmap->width));
for (unsigned x = 0;  x < width;  ++x)
{
    d[i++] = 0xAA;
    d[i++] = 0xBB;
    d[i++] = 0xCC;
}

Os resultados da medida foram os mesmos - parece que o compilador foi capaz de otimizá-lo sozinho.

Então tentei os códigos originais (com um ponteiro p), desta vez quando pé do tipo std::uint16_t*. Novamente, os resultados foram os mesmos - devido ao aliasing estrito. Em seguida, tentei construir com "-fno-strict-aliasing" e novamente vi uma diferença no tempo.

Outras respostas apontaram que içar a operação do ponteiro para fora do loop pode alterar o comportamento definido devido às regras de aliasing que permitem que char faça alias de qualquer coisa e, portanto, não é uma otimização permitida para um compilador, embora na maioria dos casos seja obviamente correto para um humano programador.

Eles também apontaram que içar a operação para fora do loop é geralmente, mas nem sempre, uma melhoria do ponto de vista do desempenho e, muitas vezes, é negativo do ponto de vista da legibilidade.

Gostaria de salientar que muitas vezes existe uma "terceira via". Em vez de contar até o número de iterações desejado, você pode contar até zero. Isso significa que o número de iterações só é necessário uma vez no início do loop, não precisa ser armazenado depois disso. Melhor ainda, no nível do montador, muitas vezes elimina a necessidade de uma comparação explícita, pois a operação de decremento normalmente definirá sinalizadores que indicam se o contador era zero antes (sinalizador de transporte) e depois (sinalizador zero) do decréscimo.

for (unsigned x = static_cast<unsigned>(bitmap->width);x > 0;  x--)
{
    *p++ = 0xAA;
    *p++ = 0xBB;
    *p++ = 0xCC;
}

Observe que esta versão do loop fornece valores de x na faixa 1 .. largura em vez de na faixa 0 .. (largura-1). Isso não importa no seu caso, porque você não está usando x para nada, mas é algo que você deve estar ciente. Se você quiser um ciclo de contagem regressiva com valores de x no intervalo 0 .. (largura-1), você pode fazer.

for (unsigned x = static_cast<unsigned>(bitmap->width); x-- > 0;)
{
    *p++ = 0xAA;
    *p++ = 0xBB;
    *p++ = 0xCC;
}

Você também pode se livrar dos casts nos exemplos acima se quiser, sem se preocupar com o impacto nas regras de comparação, já que tudo o que você está fazendo com bitmap-> largura é atribuí-lo diretamente a uma variável.

A única coisa aqui que pode impedir a otimização é a regra de aliasing estrita . Resumindo :

"Aliasing estrito é uma suposição, feita pelo compilador C (ou C ++), de que ponteiros de desreferenciamento para objetos de tipos diferentes nunca se referirão ao mesmo local de memória (ou seja, alias uns aos outros)."

[…]

A exceção à regra é a char*, que pode apontar para qualquer tipo.

A exceção também se aplica a unsignedesigned char ponteiros.

Este é o caso do seu código: você está modificando *ppor meio de pqual é um unsigned char*, portanto, o compilador deve presumir que ele pode apontar para bitmap->width. Portanto, o armazenamento em cache de bitmap->widthé uma otimização inválida. Este comportamento de prevenção de otimização é mostrado na resposta de YSC .

Se e somente se papontado para um não char- decltype(bitmap->width)tipo e não- tipo, o cache seria uma otimização possível.

A pergunta feita originalmente:

Vale a pena otimizá-lo?

E minha resposta a isso (obtendo uma boa combinação de votos positivos e negativos ...)

Deixe o compilador se preocupar com isso.

O compilador quase certamente fará um trabalho melhor do que você. E não há garantia de que sua 'otimização' seja melhor do que o código 'óbvio' - você mediu ??

Mais importante, você tem alguma prova de que o código que está otimizando tem algum impacto no desempenho de seu programa?

Apesar dos votos negativos (e agora vendo o problema do aliasing), ainda estou feliz com essa resposta válida. Se você não sabe se vale a pena otimizar algo, provavelmente não é.

Uma questão bem diferente, é claro, seria esta:

Como posso saber se vale a pena otimizar um fragmento de código?

Primeiro, seu aplicativo ou biblioteca precisa ser executado mais rápido do que atualmente? O usuário ficou esperando muito tempo? O seu software prevê o tempo de ontem em vez de amanhã?

Só você pode realmente dizer isso, com base na finalidade do seu software e nas expectativas dos usuários.

Supondo que seu software precise de alguma otimização, a próxima coisa a fazer é começar a medir. Os criadores de perfil dirão a você onde seu código gasta o tempo. Se o seu fragmento não estiver sendo mostrado como um gargalo, é melhor deixá-lo sozinho. Perfiladores e outras ferramentas de medição também dirão se suas alterações fizeram a diferença. É possível passar horas tentando otimizar o código, apenas para descobrir que você não fez nenhuma diferença perceptível.

O que você quer dizer com 'otimizar', afinal?

Se você não está escrevendo código 'otimizado', então seu código deve ser tão claro, limpo e conciso quanto possível. O argumento "Otimização prematura é má" não é desculpa para código desleixado ou ineficiente.

O código otimizado normalmente sacrifica alguns dos atributos acima para desempenho. Pode envolver a introdução de variáveis ​​locais adicionais, tendo objetos com escopo mais amplo do que o esperado ou até mesmo a reversão da ordem normal do loop. Tudo isso pode ser menos claro ou conciso, então documente o código (resumidamente!) Sobre por que você está fazendo isso.

Mas frequentemente, com código 'lento', essas micro-otimizações são o último recurso. O primeiro lugar a olhar é para algoritmos e estruturas de dados. Existe alguma maneira de evitar fazer o trabalho? As pesquisas lineares podem ser substituídas por binárias? Uma lista vinculada seria mais rápida aqui do que um vetor? Ou uma mesa de hash? Posso armazenar os resultados em cache? Tomar boas decisões 'eficientes' aqui muitas vezes pode afetar o desempenho em uma ordem de magnitude ou mais!

Eu uso o seguinte padrão em situações como esta. É quase tão curto quanto o primeiro caso seu, e é melhor do que o segundo caso, porque mantém a variável temporária local para o loop.

for (unsigned int x = 0, n = static_cast<unsigned>(bitmap->width); x < n; ++x)
{
  *p++ = 0xAA;
  *p++ = 0xBB;
  *p++ = 0xCC;
}

Isso será mais rápido com um compilador menos inteligente, build de depuração ou certos sinalizadores de compilação.

Edit1 : Colocar uma operação constante fora de um loop é uma boa padrão de programação. Mostra a compreensão dos fundamentos da operação da máquina, especialmente em C / C ++. Eu diria que o esforço para se provar deve ser feito em pessoas que não seguem essa prática. Se o compilador punir por um bom padrão, é um bug no compilador.

Edit2:: Eu medi minha sugestão contra o código original no vs2013, obtive% 1 melhoria. Podemos fazer melhor? Uma otimização manual simples oferece 3 vezes uma melhoria em relação ao loop original na máquina x64, sem recorrer a instruções exóticas. O código a seguir assume o sistema little endian e um bitmap alinhado corretamente. O TESTE 0 é original (9 segundos), o TESTE 1 é mais rápido (3 segundos). Aposto que alguém poderia tornar isso ainda mais rápido, e o resultado do teste dependeria do tamanho do bitmap. Definitivamente, em breve, no futuro, o compilador será capaz de produzir código consistentemente mais rápido. Temo que este seja o futuro, quando o compilador também for um programador AI, então estaríamos sem trabalho. Mas, por enquanto, apenas escreva um código que mostre que você sabe que não é necessária uma operação extra no loop.

#include <memory>
#include <time.h>

struct Bitmap_line
{
  int blah;
  unsigned int width;
  Bitmap_line(unsigned int w)
  {
    blah = 0;
    width = w;
  }
};

#define TEST 0 //define 1 for faster test

int main(int argc, char* argv[])
{
  unsigned int size = (4 * 1024 * 1024) / 3 * 3; //makes it divisible by 3
  unsigned char* pointer = (unsigned char*)malloc(size);
  memset(pointer, 0, size);
  std::unique_ptr<Bitmap_line> bitmap(new Bitmap_line(size / 3));
  clock_t told = clock();
#if TEST == 0
  for (int iter = 0; iter < 10000; iter++)
  {
    unsigned char* p = pointer;
    for (unsigned x = 0; x < static_cast<unsigned>(bitmap->width); ++x)
    //for (unsigned x = 0, n = static_cast<unsigned>(bitmap->width); x < n; ++x)
    {
      *p++ = 0xAA;
      *p++ = 0xBB;
      *p++ = 0xCC;
    }
  }
#else
  for (int iter = 0; iter < 10000; iter++)
  {
    unsigned char* p = pointer;
    unsigned x = 0;
    for (const unsigned n = static_cast<unsigned>(bitmap->width) - 4; x < n; x += 4)
    {
      *(int64_t*)p = 0xBBAACCBBAACCBBAALL;
      p += 8;
      *(int32_t*)p = 0xCCBBAACC;
      p += 4;
    }

    for (const unsigned n = static_cast<unsigned>(bitmap->width); x < n; ++x)
    {
      *p++ = 0xAA;
      *p++ = 0xBB;
      *p++ = 0xCC;
    }
  }
#endif
  double ms = 1000.0 * double(clock() - told) / CLOCKS_PER_SEC;
  printf("time %0.3f\n", ms);

  {
    //verify
    unsigned char* p = pointer;
    for (unsigned x = 0, n = static_cast<unsigned>(bitmap->width); x < n; ++x)
    {
      if ((*p++ != 0xAA) || (*p++ != 0xBB) || (*p++ != 0xCC))
      {
        printf("EEEEEEEEEEEEERRRRORRRR!!!\n");
        abort();
      }
    }
  }

  return 0;
}

Existem duas coisas a serem consideradas.

A) Com que frequência a otimização será executada?

Se a resposta não for muito frequente, como apenas quando um usuário clica em um botão, não se preocupe se isso tornar seu código ilegível. Se a resposta for 1000 vezes por segundo, provavelmente você desejará ir com a otimização. Se for um pouco complexo, certifique-se de colocar um comentário explicando o que está acontecendo para ajudar o próximo cara que aparecer.

B) Isso tornará o código mais difícil de manter / solucionar problemas?

Se você não está vendo um grande ganho no desempenho, tornar seu código enigmático simplesmente para economizar alguns tique-taques não é uma boa ideia. Muitas pessoas dirão que qualquer bom programador deve ser capaz de olhar o código e descobrir o que está acontecendo. Isso é verdade. O problema é que, no mundo dos negócios, o tempo extra para descobrir isso custa dinheiro. Portanto, se você pode torná-lo mais bonito de ler, faça-o. Seus amigos vão agradecer por isso.

Dito isso, eu usaria pessoalmente o exemplo B.

O compilador é capaz de otimizar muitas coisas. Para seu exemplo, você deve ir para a legibilidade, manutenção e o que segue o seu padrão de código. Para obter mais informações sobre o que pode ser otimizado (com o GCC), consulte esta postagem do blog .

Como regra geral, deixe o compilador fazer a otimização para você, até que você determine que deve assumir. A lógica para isso não tem nada a ver com desempenho, mas sim com legibilidade humana. No vasto maioria dos casos, a legibilidade de seu programa é mais importante do que seu desempenho. Você deve ter como objetivo escrever um código que seja mais fácil de ser lido por um ser humano e só se preocupar com a otimização quando estiver convencido de que o desempenho é mais importante do que a manutenção do código.

Depois de ver que o desempenho é importante, você deve executar um criador de perfil no código para determinar quais loops estão sendo ineficientes e otimizá-los individualmente. De fato, pode haver casos em que você deseja fazer essa otimização (especialmente se você migrar para C ++, onde os contêineres STL são envolvidos), mas o custo em termos de legibilidade é grande.

Além disso, posso pensar em situações patológicas em que isso poderia realmente desacelerar o código. Por exemplo, considere o caso em que o compilador não conseguiu provar que bitmap->widthera constante durante o processo. Ao adicionar a widthvariável, você força o compilador a manter uma variável local nesse escopo. Se, por algum motivo específico da plataforma, essa variável extra impediu alguma otimização do espaço de pilha, pode ser necessário reorganizar como está emitindo bytecodes e produzir algo menos eficiente.

A título de exemplo, no Windows x64, é obrigado a chamar uma chamada API especial, __chkstkno preâmbulo da função, se a função for usar mais de 1 página de variáveis ​​locais. Esta função dá às janelas a chance de gerenciar as páginas de proteção que usam para expandir a pilha quando necessário. Se sua variável extra aumenta o uso da pilha de menos de 1 página para mais ou menos de 1 página, sua função agora é obrigada a chamar __chkstktoda vez que for inserida. Se você quisesse otimizar esse loop em um caminho lento, na verdade poderia desacelerar o caminho rápido mais do que economizou no caminho lento!

Claro, é um pouco patológico, mas o ponto desse exemplo é que você pode realmente desacelerar o compilador. Isso apenas mostra que você precisa definir o perfil de seu trabalho para determinar para onde vão as otimizações. Enquanto isso, não sacrifique a legibilidade de forma alguma por uma otimização que pode ou não ser importante.

A comparação está errada, pois os dois trechos de código

for (unsigned x = 0;  x < static_cast<unsigned>(bitmap->width);  ++x)

e

unsigned width(static_cast<unsigned>(bitmap->width));
for (unsigned x = 0;  x<width ;  ++x)

não são equivalentes

No primeiro caso, widthé dependente e não const, e não se pode presumir que não pode mudar entre as iterações subsequentes. Portanto, não pode ser otimizado, mas deve ser verificado em cada loop .

No seu caso otimizado, uma variável local recebe o valor de bitmap->widthem algum ponto durante a execução do programa. O compilador pode verificar se isso realmente não muda.

Você pensou em multiencadeamento ou talvez o valor possa ser dependente externamente, de forma que seu valor seja volátil. Como se esperaria que o compilador descobrisse todas essas coisas se você não contasse?

O compilador só pode fazer o melhor que seu código permitir.

A menos que você saiba exatamente como o compilador otimiza o código, é melhor fazer suas próprias otimizações, mantendo a legibilidade e o design do código. Praticamente é difícil verificar o código assembly para cada função que escrevemos para novas versões do compilador.

O compilador não pode otimizar bitmap->widthporque o valor de widthpode ser alterado entre as iterações. Existem alguns motivos mais comuns:

1. Multi-threading. O compilador não pode prever se outro encadeamento está prestes a mudar o valor.
2. Modificação dentro do loop, às vezes não é simples dizer se a variável será alterada dentro do loop.
3. É uma chamada de função, por exemplo, iterator::end()ou container::size()então é difícil prever se sempre retornará o mesmo resultado.

Resumindo (minha opinião pessoal) para locais que requerem alto nível de otimização você precisa fazer isso sozinho, em outros locais apenas deixe, o compilador pode otimizá-lo ou não, se não houver grande diferença a legibilidade do código é o alvo principal.