Por que os compiladores perdem a vetorização aqui?

Parece que os compiladores não conseguem perceber (e não adicionam código para verificar) que data[i]nunca aponta para this->size. Isso tornaria a contagem de viagens de loop não calculável antes da primeira iteração, algo que nenhum compilador convencional, exceto o ICC, pode manipular.

Espero que os compiladores possam aprender a verificar possíveis sobreposições antes de aplicar sua lógica de vetorização, como (.data > this) || (.data+.size) < this, espero que haja uma maneira eficiente de fazer isso. Eles já inventaram código para verificar a sobreposição entre dois arrays em add2.

(Quanto mais código de verificação for necessário na inicialização, mais lucrativa será a vetorização para se pagar; os elementos escalares de 64 bits não são tão ruins com a linha de base x86-64 em comparação com vetores de 128 bits, especialmente quando o compilador não sei pelo PGO que o tamanho geralmente não é pequeno e que o loop é quente. Tentei gcc -march=icelake-clientnão -march=znver4apenas habilitar o AVX2, mas também definir heurísticas de ajuste para CPUs com taxa de transferência de vetor muito boa e largura de banda de cache/memória. Mas ainda sem alegria, então isso é possível aliasing é provavelmente um obstáculo completo, não uma decisão heurística.)

Asm evidências de que os compiladores estão preocupados com o aliasingthis->size

Observe como a ramificação do loop do GCC é cmp rax, QWORD PTR [rdi+8], onde raxdetém ie [rdi+8]é this->size(convenção de chamada x86-64 SysV), portanto, é recarregada a cada iteração. Se compilarmos com -O3 -fno-tree-vectorize, veremos que o GCC add2carrega o tamanho em um registro antes do loop, comparando com o que está dentro do loop. ou seja, içar a carga. O fato de o GCC não fazer isso add1é um sinal bastante claro de que ele pensa que data[i] += ...pode modificar arquivos this->size.

# GCC's add1 inner loop with -O3   -march=icelake-client
.L3:
        mov     rcx, QWORD PTR [rsi+rax*8]
        add     QWORD PTR [rdx+rax*8], rcx
        inc     rax
        cmp     rax, QWORD PTR [rdi+8]
        jb      .L3

Além disso, alterar o tipo para unsigned *data;ou qualquer coisa que não possa apontar para size_tpermite que GCC, Clang e ICC sejam vetorizados automaticamente de add1. O uso -fno-strict-aliasingdesativa a vetorização novamente. (E torna os compiladores mais "paranóicos", recarregando this->datae other.dataa cada iteração, como o MSVC sempre fazia. Também quebrando a vetorização add2desses compiladores.)

Alterar o tipo de ponteiro não ajuda o MSVC porque não faz análise de alias baseada em tipo; sempre age como gcc -fno-strict-aliasing. O MSVC add2já verifica mais do que apenas a sobreposição dos arrays apontados, eu acho; provavelmente algum desse cmp/jcc extra está verificando que this->data[i] += ...não mudará o .dataponteiro em thisou other.

std::vectornão tem size_tmembros, geralmente evitando isso

std::vector<size_t>não teria esse problema (pelo menos em compiladores não-MSVC) porque o aliasing baseado em tipo sabe que size_t *não pode apontar para outro ponteiro. std::vectornormalmente armazena três ponteiros: .begin, .end, e end_of_capacity, portanto, as informações de tamanho são end-begin, não um membro que armazena o tamanho diretamente.

Para iterar sobre uma matriz, normalmente é pelo menos tão eficiente incrementar um ponteiro quanto for (... ; ptr < endp ; ptr++) *ptrpara não usar modos de endereçamento indexados. Presumivelmente, é por isso que std::vectornormalmente é definido dessa maneira, em vez de um ponteiro e dois size_tmembros.

Algumas máquinas RISC nem sequer têm modos de endereçamento indexados de dois registradores. Para iterar duas matrizes, algumas CPUs se sairão melhor com menos instruções, apenas incrementando um índice em vez de dois incrementos de ponteiro, mas isso depende da microarquitetura, por exemplo, algumas CPUs x86 não laminam add reg, [reg + reg] em 2 uops no back-end, não o mantendo micro -fundido, especialmente com instruções AVX de 3 operandos.

Uma maneira eficiente (no asm) de fazer um loop em duas matrizes em CPUs com endereçamento indexado é endereçar uma matriz em relação à outra. É UB fazer isso em C ++ e ofuscaria seu código, então é algo que os compiladores devem fazer por você. sub rsi, rdifora do loop (subtrair ponteiros), então o corpo do loop pode ser mov eax, [rsi + rdi](segundo array = diferença + primeiro) / add [rdi], eax(primeiro array) / add rdi, 8(incrementar o ponteiro que também é o índice para o outro array).

O MSVC realmente fará essa otimização que outros compiladores ainda não pegaram. ( Godbolt )

// Compilers still optimize without __restrict, but it gets rid of the noise of extra checking
void foo(int *__restrict a, int *__restrict b){
    for (int i=0 ; i<10240; i++){
        a[i] += b[i];
    }
}

void foo(int * __restrict,int * __restrict) PROC                              ; foo, COMDAT
        lea     rax, QWORD PTR [rcx+32]
        sub     rdx, rcx       ;;;; <---- Pointer subtraction
        mov     ecx, 320                      ; 00000140H
        npad    4
$LL4@foo:
        vmovdqu ymm1, YMMWORD PTR [rax-32]            ;; unrolled with 4 vectors
        vpaddd  ymm1, ymm1, YMMWORD PTR [rdx+rax-32]
        vmovdqu YMMWORD PTR [rax-32], ymm1

        vmovdqu ymm2, YMMWORD PTR [rax]
        vpaddd  ymm1, ymm2, YMMWORD PTR [rdx+rax]
        vmovdqu YMMWORD PTR [rax], ymm1

        vmovdqu ymm1, YMMWORD PTR [rax+32]
        vpaddd  ymm1, ymm1, YMMWORD PTR [rdx+rax+32]
        vmovdqu YMMWORD PTR [rax+32], ymm1

        vmovdqu ymm1, YMMWORD PTR [rax+64]
        vpaddd  ymm1, ymm1, YMMWORD PTR [rdx+rax+64]
        vmovdqu YMMWORD PTR [rax+64], ymm1

        lea     rax, QWORD PTR [rax+128]
        sub     rcx, 1
        jne     SHORT $LL4@foo
        vzeroupper
        ret     0

Infelizmente, o MSVC retrocedeu e está usando o modo de endereçamento de dois registros como o operando de fonte de memória para vpaddq. Ele será deslaminado em questão/renomeado para o ROB na família Intel Sandybridge, incluindo pelo menos Skylake, provavelmente um pouco mais tarde. Mas vpaddd ymm1, ymm1, [rdx]seria 1 up. A carga pura vmovdquseria sempre 1 up mesmo com um modo de endereçamento indexado.

As lojas indexadas também não são ideais (o endereço da loja uop não pode ser executado na porta 7 em Haswell / Skylake), e o MSVC evita isso. Mas ele poderia obter o melhor dos dois mundos fazendo a carga pura com b[]um modo de endereçamento indexado e, em seguida, fonte de memória vpadd+ armazenamento com o modo de endereçamento simples, como [rdx+32].

Portanto, o MSVC economizou algum tamanho de código e está obtendo algum benefício na taxa de transferência de back-end, precisando de apenas um incremento de sobrecarga de loop e na contenção de porta AGU, para que possa ser executado próximo a 1 vetor por clock com acessos de cache L1d para permitir fazer 2 cargas + 1 armazenar a cada ciclo. (O manual de otimização da Intel sugere que o Skylake não pode sustentar totalmente isso para carregamento/armazenamento de 32 bytes, por algum motivo desconhecido.)

Com um modo de endereçamento indexado para a loja, como uso de GCC e clang, ele só poderia ser executado em 1 vetor por 1,5 ciclos em Haswell / Skylake. (Ice Lake tem duas AGUs de carga e duas AGUs de armazenamento separadas, evitando esse gargalo, mas não sei se a deslaminação dos modos de endereçamento indexado ainda é uma coisa em Ice Lake ou Alder Lake.)

IDK o que há com o MSVC preferindo leaincrementar um ponteiro. Ou por preferir sub ecx/jneem vez de comparar com um ponteiro final leaantes do loop em vez de mov. Então o fim do loop poderia ser cmp rax, r8/ jneou algo assim, que se fundiria em um único uop na AMD, não apenas na Intel.