O uso desse ponteiro causa uma desoptimização estranha no loop quente

122

Recentemente, deparei-me com uma estranha desoptimização (ou melhor, perdi uma oportunidade de otimização).

Considere esta função para descompactar com eficiência matrizes de números inteiros de 3 bits a números inteiros de 8 bits. Descompacta 16 ints em cada iteração de loop:

void unpack3bit(uint8_t* target, char* source, int size) {
   while(size > 0){
      uint64_t t = *reinterpret_cast<uint64_t*>(source);
      target[0] = t & 0x7;
      target[1] = (t >> 3) & 0x7;
      target[2] = (t >> 6) & 0x7;
      target[3] = (t >> 9) & 0x7;
      target[4] = (t >> 12) & 0x7;
      target[5] = (t >> 15) & 0x7;
      target[6] = (t >> 18) & 0x7;
      target[7] = (t >> 21) & 0x7;
      target[8] = (t >> 24) & 0x7;
      target[9] = (t >> 27) & 0x7;
      target[10] = (t >> 30) & 0x7;
      target[11] = (t >> 33) & 0x7;
      target[12] = (t >> 36) & 0x7;
      target[13] = (t >> 39) & 0x7;
      target[14] = (t >> 42) & 0x7;
      target[15] = (t >> 45) & 0x7;
      source+=6;
      size-=6;
      target+=16;
   }
}

Aqui está o assembly gerado para partes do código:

 ...
 367:   48 89 c1                mov    rcx,rax
 36a:   48 c1 e9 09             shr    rcx,0x9
 36e:   83 e1 07                and    ecx,0x7
 371:   48 89 4f 18             mov    QWORD PTR [rdi+0x18],rcx
 375:   48 89 c1                mov    rcx,rax
 378:   48 c1 e9 0c             shr    rcx,0xc
 37c:   83 e1 07                and    ecx,0x7
 37f:   48 89 4f 20             mov    QWORD PTR [rdi+0x20],rcx
 383:   48 89 c1                mov    rcx,rax
 386:   48 c1 e9 0f             shr    rcx,0xf
 38a:   83 e1 07                and    ecx,0x7
 38d:   48 89 4f 28             mov    QWORD PTR [rdi+0x28],rcx
 391:   48 89 c1                mov    rcx,rax
 394:   48 c1 e9 12             shr    rcx,0x12
 398:   83 e1 07                and    ecx,0x7
 39b:   48 89 4f 30             mov    QWORD PTR [rdi+0x30],rcx
 ...

Parece bastante eficaz. Simplesmente um shift rightseguido de um ande depois um storepara o targetbuffer. Mas agora, veja o que acontece quando altero a função para um método em uma struct:

struct T{
   uint8_t* target;
   char* source;
   void unpack3bit( int size);
};

void T::unpack3bit(int size) {
        while(size > 0){
           uint64_t t = *reinterpret_cast<uint64_t*>(source);
           target[0] = t & 0x7;
           target[1] = (t >> 3) & 0x7;
           target[2] = (t >> 6) & 0x7;
           target[3] = (t >> 9) & 0x7;
           target[4] = (t >> 12) & 0x7;
           target[5] = (t >> 15) & 0x7;
           target[6] = (t >> 18) & 0x7;
           target[7] = (t >> 21) & 0x7;
           target[8] = (t >> 24) & 0x7;
           target[9] = (t >> 27) & 0x7;
           target[10] = (t >> 30) & 0x7;
           target[11] = (t >> 33) & 0x7;
           target[12] = (t >> 36) & 0x7;
           target[13] = (t >> 39) & 0x7;
           target[14] = (t >> 42) & 0x7;
           target[15] = (t >> 45) & 0x7;
           source+=6;
           size-=6;
           target+=16;
        }
}

Eu pensei que o assembly gerado deveria ser o mesmo, mas não é. Aqui está uma parte:

...
 2b3:   48 c1 e9 15             shr    rcx,0x15
 2b7:   83 e1 07                and    ecx,0x7
 2ba:   88 4a 07                mov    BYTE PTR [rdx+0x7],cl
 2bd:   48 89 c1                mov    rcx,rax
 2c0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 2c3:   48 c1 e9 18             shr    rcx,0x18
 2c7:   83 e1 07                and    ecx,0x7
 2ca:   88 4a 08                mov    BYTE PTR [rdx+0x8],cl
 2cd:   48 89 c1                mov    rcx,rax
 2d0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 2d3:   48 c1 e9 1b             shr    rcx,0x1b
 2d7:   83 e1 07                and    ecx,0x7
 2da:   88 4a 09                mov    BYTE PTR [rdx+0x9],cl
 2dd:   48 89 c1                mov    rcx,rax
 2e0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 2e3:   48 c1 e9 1e             shr    rcx,0x1e
 2e7:   83 e1 07                and    ecx,0x7
 2ea:   88 4a 0a                mov    BYTE PTR [rdx+0xa],cl
 2ed:   48 89 c1                mov    rcx,rax
 2f0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 ...

Como você vê, introduzimos uma redundância adicional loadda memória antes de cada turno ( mov rdx,QWORD PTR [rdi]). Parece que o targetponteiro (que agora é um membro em vez de uma variável local) deve ser sempre recarregado antes de armazená-lo. Isso diminui consideravelmente o código (cerca de 15% nas minhas medidas).

Primeiro, pensei que talvez o modelo de memória C ++ imponha que um ponteiro de membro não possa ser armazenado em um registro, mas precise ser recarregado, mas isso parecia uma escolha incômoda, pois impossibilitaria muitas otimizações viáveis. Então, fiquei muito surpreso que o compilador não tenha armazenado targetem um registro aqui.

Tentei armazenar em cache o ponteiro de membro em uma variável local:

void T::unpack3bit(int size) {
    while(size > 0){
       uint64_t t = *reinterpret_cast<uint64_t*>(source);
       uint8_t* target = this->target; // << ptr cached in local variable
       target[0] = t & 0x7;
       target[1] = (t >> 3) & 0x7;
       target[2] = (t >> 6) & 0x7;
       target[3] = (t >> 9) & 0x7;
       target[4] = (t >> 12) & 0x7;
       target[5] = (t >> 15) & 0x7;
       target[6] = (t >> 18) & 0x7;
       target[7] = (t >> 21) & 0x7;
       target[8] = (t >> 24) & 0x7;
       target[9] = (t >> 27) & 0x7;
       target[10] = (t >> 30) & 0x7;
       target[11] = (t >> 33) & 0x7;
       target[12] = (t >> 36) & 0x7;
       target[13] = (t >> 39) & 0x7;
       target[14] = (t >> 42) & 0x7;
       target[15] = (t >> 45) & 0x7;
       source+=6;
       size-=6;
       this->target+=16;
    }
}

Esse código também gera o montador "bom" sem lojas adicionais. Então, meu palpite é: O compilador não pode elevar a carga de um ponteiro membro de uma estrutura, portanto, esse "ponteiro quente" deve sempre ser armazenado em uma variável local.

  • Então, por que o compilador não consegue otimizar essas cargas?
  • É o modelo de memória C ++ que proíbe isso? Ou é simplesmente uma falha do meu compilador?
  • Meu palpite está correto ou qual é o motivo exato pelo qual a otimização não pode ser executada?

O compilador em uso foi g++ 4.8.2-19ubuntu1com -O3otimização. Eu também tentei clang++ 3.4-1ubuntu3com resultados semelhantes: Clang é capaz de vetorizar o método com o targetponteiro local . No entanto, o uso do this->targetponteiro produz o mesmo resultado: Uma carga extra do ponteiro antes de cada loja.

Eu verifiquei o assembler de alguns métodos semelhantes e o resultado é o mesmo: parece que um membro thissempre precisa ser recarregado antes de uma loja, mesmo que essa carga possa ser içada simplesmente fora do loop. Terei que reescrever muito código para livrar-se desses armazenamentos adicionais, principalmente armazenando o ponteiro em cache em uma variável local declarada acima do código quente. Mas eu sempre pensei que mexer com detalhes como o cache de um ponteiro em uma variável local certamente se qualificaria para a otimização prematura nos dias de hoje em que os compiladores se tornaram tão inteligentes. Mas parece que estou errado aqui . O armazenamento em cache de um ponteiro de membro em um loop ativo parece ser uma técnica de otimização manual necessária.

gexicida
fonte
5
Não sei por que motivo houve uma votação negativa - é uma pergunta interessante. FWIW: Eu vi problemas semelhantes de otimização com variáveis ​​de membros que não são ponteiros, onde a solução foi semelhante, ou seja, armazenar em cache a variável de membro em uma variável local durante o tempo de vida do método. Eu estou supondo que é algo a ver com regras de aliasing?
Paul R
1
Parece que o compilador não otimiza porque ele não pode garantir que o membro não seja acessado através de algum código "externo". Portanto, se o membro puder ser modificado fora, ele deverá ser recarregado sempre que for acessado. Parece ser considerado como uma espécie de volátil ...
Jean-Baptiste Yunes
Não usar this->é apenas açúcar sintático. O problema está relacionado à natureza das variáveis ​​(local versus membro) e às coisas que o compilador deduz desse fato.
Jean-Baptiste Yunès 10/10
Algo a ver com alias de ponteiro?
Yves Daoust 10/10
3
Como uma questão mais semântica, a "otimização prematura" aplica-se apenas à otimização prematura, ou seja, antes que a criação de perfil tenha considerado um problema. Nesse caso, você elaborou um perfil e descompilou diligentemente e encontrou a fonte de um problema e formulou e definiu o perfil de uma solução. Não é absolutamente "prematuro" aplicar essa solução.
Raptortech97 12/12/14

Respostas:

107

O aliasing de ponteiro parece ser o problema, ironicamente entre thise this->target. O compilador está levando em conta a possibilidade bastante obscena que você inicializou:

this->target = &this

Nesse caso, escrever para this->target[0]alteraria o conteúdo de this(e, portanto, this->target).

O problema de alias de memória não está restrito ao acima. Em princípio, qualquer uso de this->target[XX]um valor (in) apropriado de XXpode apontar this.

Eu sou melhor versado em C, onde isso pode ser remediado declarando variáveis ​​de ponteiro com a __restrict__palavra - chave.

Peter Boncz
fonte
18
Eu posso confirmar isso! Mudar targetde uint8_tpara uint16_t(para que regras estritas de aliasing entrem em ação) mudou. Com uint16_t, a carga é sempre otimizada.
Gexicide
1
Relevante: stackoverflow.com/questions/16138237/…
user541686 10/10
3
Alterar o conteúdo de thisnão é o que você quer dizer (não é uma variável); você quer dizer mudar o conteúdo de *this.
Marc van Leeuwen 12/10
@gexicide mente elaborando o quão estrito alias entra em ação e corrige o problema?
HCSF 21/12/19
33

Regras estritas de alias permitem char*alias qualquer outro ponteiro. Por isso, this->targetpode alias com this, e no seu método de código, a primeira parte do código,

target[0] = t & 0x7;
target[1] = (t >> 3) & 0x7;
target[2] = (t >> 6) & 0x7;

é de fato

this->target[0] = t & 0x7;
this->target[1] = (t >> 3) & 0x7;
this->target[2] = (t >> 6) & 0x7;

conforme thispode ser modificado quando você modifica o this->targetconteúdo.

Depois que this->targeté armazenado em cache em uma variável local, o alias não é mais possível com a variável local.

Jarod42
fonte
1
Então, podemos dizer como regra geral: sempre que você tiver um char*ou void*em sua estrutura, certifique-se de armazená-lo em cache em uma variável local antes de gravá-lo?
Gexicide
5
De fato, é quando você usa a char*, não necessário como membro.
Jarod42
24

O problema aqui é um aliasing estrito, que diz que podemos alias através de um caractere * e, portanto, impede a otimização do compilador no seu caso. Não é permitido alias através de um ponteiro de um tipo diferente, o que seria um comportamento indefinido, normalmente no SO, vemos esse problema: usuários tentando alias através de tipos de ponteiros incompatíveis .

Parece razoável implementar uint8_t como um caractere não assinado e, se observarmos o cstdint no Coliru, ele incluirá stdint.h, que typedefs uint8_t da seguinte maneira:

typedef unsigned char       uint8_t;

se você usou outro tipo que não seja char, o compilador poderá otimizar.

Isso é abordado na seção padrão do C ++ 3.10 Lvalues ​​e rvalues, que diz:

Se um programa tentar acessar o valor armazenado de um objeto por meio de um valor gl diferente de um dos seguintes tipos, o comportamento será indefinido

e inclui o seguinte marcador:

  • um caractere ou tipo de caractere não assinado.

Observe que eu postei um comentário sobre possíveis soluções alternativas em uma pergunta que pergunta Quando uint8_t char não é um caractere assinado? e a recomendação foi:

A solução trivial, no entanto, é usar a palavra-chave restringir ou copiar o ponteiro para uma variável local cujo endereço nunca é usado, para que o compilador não precise se preocupar se os objetos uint8_t podem usar o alias.

Como o C ++ não suporta a palavra-chave restringir, você deve confiar na extensão do compilador, por exemplo, o gcc usa __restrict__, portanto isso não é totalmente portátil, mas a outra sugestão deve ser.

Shafik Yaghmour
fonte
Este é um exemplo de um local em que o Padrão é pior para otimizadores do que seria uma regra permitiria a um compilador assumir que entre dois acessos a um objeto do tipo T, ou um acesso desse tipo, e o início ou fim de um loop / função em que ocorre, todos os acessos ao armazenamento usarão o mesmo objeto, a menos que uma operação interveniente use esse objeto (ou um ponteiro / referência a ele) para derivar um ponteiro ou referência a algum outro objeto . Essa regra eliminaria a necessidade da "exceção do tipo caractere", que pode prejudicar o desempenho do código que funciona com seqüências de bytes.
Supercat