Algoritmo SIMD para verificar se um bloco inteiro é "consecutivo".

Acho que sua primeira ideia provavelmente será melhor se for feita dentro de um loop que possa amortizar o custo de carregamento de uma constante vetorial. AVX-512 pode fazer isso de forma eficiente.

Ou com uma carga vetorial e depois transmitir separadamente o elemento baixo com vpbroadcastd, ou com uma carga vetorial e uma carga de transmissão. por exemplo vpaddd zmm16, zmm31, [rdi]{1to16}/ vpcmpeqd k1, zmm16, [rdi].

Hmm, mas verificando se todos os elementos são verdadeiros, acho que talvez kaddwcom uma constante 1e verifique se os 16 bits inferiores são zero com kortest? Ou apenas kmovpara um registro inteiro para comparação, 0xffffcomo faríamos com SSE/AVX pmovmskb. Eu tentei isso e o clang teve uma ideia melhor: compare se não é igual e verifique se a máscara é zero. (ou seja, verifique se todos os elementos são iguais, verificando se eles não são diferentes.) Isso permite kortesta própria máscara. Apliquei a ideia do clang aos meus intrínsecos para que o GCC também pudesse fazer um conjunto melhor.

Em C++:

#include <immintrin.h>

// compare for not-equal, checking the mask for 0
bool check_contig(int *p)
{
    __m512i bcast_first = _mm512_set1_epi32(*p);
    __m512i desired = _mm512_add_epi32(bcast_first, _mm512_setr_epi32(15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0));

    __m512i v = _mm512_loadu_si512(p);
    __mmask16 cmp = _mm512_cmpneq_epi32_mask(desired, v);
    return cmp == 0;
}

Godbolt - asm do GCC e clang:

# GCC
check_contig(int*):
        vmovdqa32       zmm0, ZMMWORD PTR .LC0[rip]
        vpaddd  zmm0, zmm0, DWORD PTR [rdi]{1to16}
        vpcmpd  k0, zmm0, ZMMWORD PTR [rdi], 4
        kortestw        k0, k0
        sete    al
        vzeroupper
        ret

# clang
check_contig(int*):
        vpbroadcastd    zmm0, dword ptr [rdi]
        vpaddd  zmm0, zmm0, zmmword ptr [rip + .LCPI0_0]
        vpcmpneqd       k0, zmm0, zmmword ptr [rdi]
        kortestw        k0, k0
        sete    al
        vzeroupper
        ret

Então, ambos optam por carregar duas vezes em vez de vpbroadcastd zmm1, xmm0, pelo menos quando não estão em um loop, então a constante do vetor também precisa ser carregada .rodata.

Talvez se eu escrevesse de forma diferente, como _mm512_broadcastd_epi32( _mm512_castsi512_si128(v)), eles prefeririam uma carga, ao custo de um embaralhamento extra. (O que provavelmente é pior quando você tem uops de 512 bits em vôo, então as CPUs Intel desligam o vetor ALU na porta 1, deixando apenas as portas 0 e 5. https://agner.org/optimize/ e https://uops .info/ )

Algo B - evitando uma constante vetorial não trivial

Talvez sua segunda maneira também possa ser feita de forma eficiente para valigndgirar o vetor; a única constante vetorial necessária são todas aquelas que podem ser geradas de maneira um pouco mais barata ( vpternlogd) em vez de carregadas.

Verificar a máscara de comparação provavelmente exigiria um kmovnúmero inteiro para um and+ cmpverificar todos os bits, exceto um, a menos que possamos usar o mesmo truque que o clang fez e organizar as coisas para que realmente queiramos que a máscara seja totalmente zero nos lugares que desejamos. Nesse caso, test eax, imm32podemos verificar os bits que queremos, ignorando os que não queremos.

O núcleo do meu código Rust atual agora é este código de macro:

    const LAST_INDEX: usize = <$simd>::lanes() - 1;
    let (expected, overflowed) = $chunk[0].overflowing_add(LAST_INDEX as $scalar);
    if overflowed || expected != $chunk[LAST_INDEX] {
        return false;
    }


    let a = unsafe { <$simd>::from_slice_aligned_unchecked($chunk) } + $decrease;
    let compare_mask = a.eq(<$simd>::splat(a.extract(0)));
    compare_mask.all()

Onde $scalar é u32, $simd é u32x16e $decrease é o bloco [15, 14 ... 0]. A primeira parte do código verifica se o último elemento é 15 a mais que o primeiro (e cuida dos estouros).

Pedi uma ferramenta inteligente para me ajudar a entender a montagem SIMD produzida. Diz:

• vmovdqa64: Esta instrução move um vetor de dados de 512 bits para um registrador ZMM. É usado aqui duas vezes: vmovdqa64 zmm0,zmmword ptr [...]: Carrega um vetor de 512 bits da memória para zmm0. vmovdqa64 zmm0,zmmword ptr [...] (posteriormente no código): Carrega um vetor diferente de 512 bits em zmm0. vpaddd:

• vpaddd zmm0,zmm0,zmmword ptr [rax+40h]: Executa adição de inteiros compactados de inteiros de 32 bits. Esta instrução adiciona o vetor de 512 bits em zmm0 a outro vetor de 512 bits (carregado do endereço de memória em rax + 40h) e armazena o resultado de volta em zmm0. vpbroadcastd:

• vpbroadcastd zmm1,xmm0: transmite um número inteiro de 32 bits de xmm0 (128 bits inferiores de zmm0) em todas as pistas de zmm1. Isso cria um vetor de 512 bits em zmm1 onde todos os elementos são iguais e iguais ao valor em xmm0. vpcmpeqd:

• vpcmpeqd k0,zmm0,zmm1: compara números inteiros de 32 bits em zmm0 e zmm1 quanto à igualdade. Os resultados são armazenados em um registrador máscara k0, onde cada bit representa o resultado da comparação para cada par de elementos. vpternlogd:

• vpternlogd zmm1,zmm1,zmm1,0FFh: Executa uma operação lógica ternária bit a bit em cada bit dos operandos. A operação específica é determinada pelo valor imediato 0xFF, que neste caso corresponde a um OR bit a bit. vpmovm2d:

• vpmovm2d zmm0,k0: Move a máscara de bits do registro de máscara k0 para um registro de uso geral zmm0. Cada bit de k0 se torna um elemento de 32 bits em zmm0. vpcmpd:

• vpcmpd k0,zmm0,zmm1,4: Compara números inteiros de 32 bits em zmm0 e zmm1 de acordo com o predicado fornecido como o último operando (aqui 4, que normalmente representa "menor que"). O resultado é armazenado no registro de máscara k0. vmovdqu64:

• vmovdqu64 zmmword ptr [rsp+50h],zmm0: Move o vetor de 512 bits em zmm0 para a memória no endereço rsp + 50h. curto:

• kortestw k0,k0: testa o conteúdo do registro de máscara k0 e define o sinalizador zero com base no resultado. Isso é frequentemente usado para ramificações condicionais com base nos resultados de comparação do SIMD.

• vzeroupper: Esta instrução é usada para limpar os 256 bits superiores de todos os registros YMM para evitar penalidades ao misturar AVX-512 e código SSE legado. É uma boa prática usar esta instrução antes de chamadas para funções que podem não estar cientes do AVX-512.