Subtraindo números inteiros de 8 bits em um número inteiro de 64 bits por 1 em paralelo, SWAR sem hardware SIMD

Se eu tiver um número inteiro de 64 bits, estou interpretando como uma matriz de números inteiros de 8 bits compactados com 8 elementos. Preciso subtrair a constante 1de cada número inteiro compactado enquanto lida com o estouro sem que o resultado de um elemento afete o resultado de outro elemento.

Eu tenho esse código no momento e funciona, mas preciso de uma solução que faça a subtração de cada número inteiro de 8 bits em paralelo e não faça acessos à memória. No x86, eu poderia usar instruções SIMD como psubbessa subtrai números inteiros de 8 bits em paralelo, mas a plataforma pela qual estou codificando não suporta instruções SIMD. (RISC-V neste caso).

Então, eu estou tentando fazer o SWAR (SIMD dentro de um registro) para cancelar manualmente a propagação entre bytes de a uint64_t, fazendo algo equivalente a isso:

uint64_t sub(uint64_t arg) {
    uint8_t* packed = (uint8_t*) &arg;

    for (size_t i = 0; i < sizeof(uint64_t); ++i) {
        packed[i] -= 1;
    }

    return arg;
}

Eu acho que você poderia fazer isso com operadores bit a bit, mas não tenho certeza. Estou procurando uma solução que não use instruções SIMD. Estou procurando uma solução em C ou C ++ que seja bastante portátil ou apenas a teoria por trás dela para que eu possa implementar minha própria solução.

Se você possui uma CPU com instruções SIMD eficientes, o SSE / MMX paddb( _mm_add_epi8) também é viável. A resposta de Peter Cordes também descreve a sintaxe do vetor GNU C (gcc / clang) e a segurança para UB com alias estrito. Eu recomendo fortemente a revisão dessa resposta também.

Fazer você mesmo uint64_té totalmente portátil, mas ainda requer cuidados para evitar problemas de alinhamento e UB com alias estrito ao acessar uma uint8_tmatriz com a uint64_t*. Você deixou essa parte fora de questão, começando com seus dados em um uint64_tjá, mas para o GNU C um may_aliastypedef resolve o problema (consulte a resposta de Peter para isso oumemcpy ).

Caso contrário, você poderá alocar / declarar seus dados uint64_te acessá-los uint8_t*quando quiser bytes individuais. unsigned char*é permitido alias qualquer coisa para evitar o problema no caso específico de elementos de 8 bits. (Se uint8_texiste, provavelmente é seguro assumir que é um unsigned char.)

Observe que isso é uma alteração de um algoritmo incorreto anterior (consulte o histórico de revisões).

Isso é possível sem loop para subtração arbitrária e fica mais eficiente para uma constante conhecida como 1em cada byte. O principal truque é impedir a execução de cada byte, definindo o bit alto e, em seguida, corrija o resultado da subtração.

Vamos otimizar um pouco a técnica de subtração fornecida aqui . Eles definem:

SWAR sub z = x - y
    z = ((x | H) - (y &~H)) ^ ((x ^~y) & H)

com Hdefinido como 0x8080808080808080U(ou seja, os MSBs de cada número inteiro compactado). Para um decremento, yé 0x0101010101010101U.

Sabemos que ytodos os seus MSBs estão limpos, para que possamos pular uma das etapas da máscara (ou seja, y & ~Hé a mesma ydo nosso caso). O cálculo prossegue da seguinte forma:

1. Definimos os MSBs de cada componente de x como 1, para que um empréstimo não possa se propagar além do MSB para o próximo componente. Chame isso de entrada ajustada.
2. Subtraímos 1 de cada componente, subtraindo 0x01010101010101da entrada corrigida. Isso não causa empréstimos entre componentes, graças à etapa 1. Chame isso de saída ajustada.
3. Agora precisamos corrigir o MSB do resultado. Nós realizamos a saída ajustada com os MSBs invertidos da entrada original para concluir a correção do resultado.

A operação pode ser escrita como:

#define U64MASK 0x0101010101010101U
#define MSBON 0x8080808080808080U
uint64_t decEach(uint64_t i){
      return ((i | MSBON) - U64MASK) ^ ((i ^ MSBON) & MSBON);
}

De preferência, isso é incorporado pelo compilador (use as diretivas do compilador para forçar isso) ou a expressão é escrita embutida como parte de outra função.

Casos de teste:

in:  0000000000000000
out: ffffffffffffffff

in:  f200000015000013
out: f1ffffff14ffff12

in:  0000000000000100
out: ffffffffffff00ff

in:  808080807f7f7f7f
out: 7f7f7f7f7e7e7e7e

in:  0101010101010101
out: 0000000000000000

Detalhes de desempenho

Aqui está o assembly x86_64 para uma única chamada da função. Para um melhor desempenho, ele deve ser alinhado com a esperança de que as constantes possam viver em um registro o maior tempo possível. Em um loop restrito em que as constantes vivem em um registro, o decremento real leva cinco instruções: ou + não + e + adiciona + xor após a otimização. Não vejo alternativas que superariam a otimização do compilador.

uint64t[rax] decEach(rcx):
    movabs  rcx, -9187201950435737472
    mov     rdx, rdi
    or      rdx, rcx
    movabs  rax, -72340172838076673
    add     rax, rdx
    and     rdi, rcx
    xor     rdi, rcx
    xor     rax, rdi
    ret

Com alguns testes da IACA do seguinte trecho:

// Repeat the SWAR dec in a loop as a microbenchmark
uint64_t perftest(uint64_t dummyArg){
    uint64_t dummyCounter = 0;
    uint64_t i = 0x74656a6d27080100U; // another dummy value.
    while(i ^ dummyArg) {
        IACA_START
        uint64_t naive = i - U64MASK;
        i = naive + ((i ^ naive ^ U64MASK) & U64MASK);
        dummyCounter++;
    }
    IACA_END
    return dummyCounter;
}

podemos mostrar que em uma máquina Skylake, a execução do decremento, xor e compare + jump pode ser realizada em pouco menos de 5 ciclos por iteração:

Throughput Analysis Report
--------------------------
Block Throughput: 4.96 Cycles       Throughput Bottleneck: Backend
Loop Count:  26
Port Binding In Cycles Per Iteration:
--------------------------------------------------------------------------------------------------
|  Port  |   0   -  DV   |   1   |   2   -  D    |   3   -  D    |   4   |   5   |   6   |   7   |
--------------------------------------------------------------------------------------------------
| Cycles |  1.5     0.0  |  1.5  |  0.0     0.0  |  0.0     0.0  |  0.0  |  1.5  |  1.5  |  0.0  |
--------------------------------------------------------------------------------------------------

(Obviamente, no x86-64 você apenas carregaria ou movqem um registro XMM paddb, portanto, pode ser mais interessante ver como ele é compilado para um ISA como o RISC-V.)

Para o RISC-V, você provavelmente está usando o GCC / clang.

Curiosidade: O GCC conhece alguns desses truques de bithack do SWAR (mostrados em outras respostas) e pode usá-los para você ao compilar código com vetores nativos do GNU C para destinos sem instruções SIMD de hardware. (Mas o clang para o RISC-V apenas o desenrola ingenuamente para operações escalares, então você precisa fazer isso sozinho se quiser um bom desempenho entre os compiladores).

Uma vantagem da sintaxe do vetor nativo é que, ao direcionar uma máquina com o hardware SIMD, ela será usada em vez de vetorizar automaticamente seu bithack ou algo horrível assim.

Isso facilita a gravação de vector -= scalaroperações; a sintaxe Just Works, transmitindo implicitamente, ou seja, dividindo o escalar para você.

Observe também que uma uint64_t*carga de a uint8_t array[]é UB com alias estrito; portanto, tenha cuidado com isso. (Veja também Por que o strlen da glibc precisa ser tão complicado para ser executado rapidamente? Re: tornando os bithacks do SWAR com alias estrito seguro em C puro). Você pode querer que algo assim declare um uint64_tque possa ser convertido em ponteiro para acessar outros objetos, como o char*funcionamento em ISO C / C ++.

use-os para obter dados do uint8_t em um uint64_t para uso com outras respostas:

// GNU C: gcc/clang/ICC but not MSVC
typedef uint64_t  aliasing_u64 __attribute__((may_alias));  // still requires alignment
typedef uint64_t  aliasing_unaligned_u64 __attribute__((may_alias, aligned(1)));

A outra maneira de realizar cargas seguras para serrilhado é com memcpy a uint64_t, que também remove o alignof(uint64_t) requisito de alinhamento. Mas em ISAs sem cargas eficientes e desalinhadas, o gcc / clang não memcpyse alinha e otimiza quando não pode provar que o ponteiro está alinhado, o que seria desastroso para o desempenho.

TL: DR: sua melhor aposta é declarar seus dados como uint64_t array[...] ou alocá-los dinamicamente como uint64_t, ou de preferênciaalignas(16) uint64_t array[]; Isso garante alinhamento a pelo menos 8 bytes ou 16, se você especificar alignas.

Como uint8_té quase certo unsigned char*, é seguro acessar os bytes de umuint64_t via uint8_t*(mas não vice-versa para uma matriz uint8_t). Portanto, neste caso especial em que o tipo de elemento estreito é unsigned char, você pode contornar o problema de alias estrito porque charé especial.

Exemplo de sintaxe de vetor nativo GNU C:

Os vetores nativos do GNU C sempre têm permissão para usar o alias com seu tipo subjacente (por exemplo, int __attribute__((vector_size(16)))podem com segurança alias, intmas nãofloat ou uint8_tou qualquer outra coisa.

#include <stdint.h>
#include <stddef.h>

// assumes array is 16-byte aligned
void dec_mem_gnu(uint8_t *array) {
    typedef uint8_t v16u8 __attribute__ ((vector_size (16), may_alias));
    v16u8 *vecs = (v16u8*) array;
    vecs[0] -= 1;
    vecs[1] -= 1;   // can be done in a loop.
}

Para o RISC-V sem nenhum HW SIMD, você pode vector_size(8)expressar apenas a granularidade que pode usar com eficiência e fazer o dobro de vetores menores.

Mas vector_size(8) compila de maneira estúpida para o x86 com o GCC e o clang: o GCC usa bithacks SWAR em registros de número inteiro GP, clang descompacta elementos de 2 bytes para preencher um registro XMM de 16 bytes e depois repete. (A MMX é tão obsoleta que o GCC / clang nem se importa em usá-lo, pelo menos não para x86-64.)

Mas com vector_size (16)( Godbolt ) obtemos o esperado movdqa/ paddb. (Com um vetor tudo gerado por pcmpeqd same,same). Como -march=skylakeainda temos duas operações XMM separadas em vez de uma YMM, infelizmente os compiladores atuais também não "auto-vectorizam" as operações vetoriais em vetores mais amplos: /

Para o AArch64, não é tão ruim de usar vector_size(8)( Godbolt ); O ARM / AArch64 pode trabalhar nativamente em blocos de 8 ou 16 bytes comd ou qregistradores.

Portanto, você provavelmente deseja vector_size(16)compilar se deseja desempenho portátil em x86, RISC-V, ARM / AArch64 e POWER . No entanto, alguns outros ISAs fazem SIMD em registros inteiros de 64 bits, como MIPS MSA, eu acho.

vector_size(8)facilita a análise do asm (apenas um registro de dados): Godbolt compiler explorer

# GCC8.2 -O3 for RISC-V for vector_size(8) and only one vector

dec_mem_gnu(unsigned char*):
        lui     a4,%hi(.LC1)           # generate address for static constants.
        ld      a5,0(a0)                 # a5 = load from function arg
        ld      a3,%lo(.LC1)(a4)       # a3 = 0x7F7F7F7F7F7F7F7F
        lui     a2,%hi(.LC0)
        ld      a2,%lo(.LC0)(a2)       # a2 = 0x8080808080808080
                             # above here can be hoisted out of loops
        not     a4,a5                  # nx = ~x
        and     a5,a5,a3               # x &= 0x7f... clear high bit
        and     a4,a4,a2               # nx = (~x) & 0x80... inverse high bit isolated
        add     a5,a5,a3               # x += 0x7f...   (128-1)
        xor     a5,a4,a5               # x ^= nx  restore high bit or something.

        sd      a5,0(a0)               # store the result
        ret

Eu acho que é a mesma idéia básica que as outras respostas sem loop; impedindo o transporte e fixando o resultado.

Estas são 5 instruções da ULA, pior que a resposta principal, eu acho. Mas parece que a latência do caminho crítico é de apenas 3 ciclos, com duas cadeias de 2 instruções, cada uma levando ao XOR. A resposta de @Reinstate Monica - ζ - é compilada em uma cadeia dep de 4 ciclos (para x86). A taxa de transferência de loop de 5 ciclos é um gargalo, incluindo também um ingênuosub no caminho crítico, e o loop afunila na latência.

No entanto, isso é inútil com o clang. Ele nem adiciona e armazena na mesma ordem em que foi carregado, por isso não está fazendo um bom pipelining de software!

# RISC-V clang (trunk) -O3
dec_mem_gnu(unsigned char*):
        lb      a6, 7(a0)
        lb      a7, 6(a0)
        lb      t0, 5(a0)
...
        addi    t1, a5, -1
        addi    t2, a1, -1
        addi    t3, a2, -1
...
        sb      a2, 7(a0)
        sb      a1, 6(a0)
        sb      a5, 5(a0)
...
        ret

Eu apontaria que o código que você escreveu realmente vetoriza quando você começa a lidar com mais de um único uint64_t.

https://godbolt.org/z/J9DRzd

Você pode garantir que a subtração não transborde e conserte o bit alto:

uint64_t sub(uint64_t arg) {
    uint64_t x1 = arg | 0x80808080808080;
    uint64_t x2 = ~arg & 0x80808080808080;
    // or uint64_t x2 = arg ^ x1; to save one instruction if you don't have an andnot instruction
    return (x1 - 0x101010101010101) ^ x2;
}

Não tenho certeza se é isso que você deseja, mas ele faz as 8 subtrações em paralelo entre si:

#include <cstdint>

constexpr uint64_t mask = 0x0101010101010101;

uint64_t sub(uint64_t arg) {
    uint64_t mask_cp = mask;
    for(auto i = 0; i < 8 && mask_cp; ++i) {
        uint64_t new_mask = (arg & mask_cp) ^ mask_cp;
        arg = arg ^ mask_cp;
        mask_cp = new_mask << 1;
    }
    return arg;
}

Explicação: A máscara de bit começa com 1 em cada um dos números de 8 bits. Nós concordamos com nosso argumento. Se tivéssemos um 1 nesse local, subtraímos 1 e temos que parar. Isso é feito configurando o bit correspondente como 0 em new_mask. Se tivéssemos um 0, definimos como 1 e temos que realizar o transporte, para que o bit permaneça 1 e deslocamos a máscara para a esquerda. É melhor você verificar se a geração da nova máscara funciona como pretendido, acho que sim, mas uma segunda opinião não seria ruim.

PS: Na verdade, não tenho certeza se a verificação de mask_cpnão ser nulo no loop pode atrasar o programa. Sem ele, o código ainda estaria correto (uma vez que a máscara 0 simplesmente não faz nada) e seria muito mais fácil para o compilador desenrolar o loop.

int subtractone(int x) 
{
    int f = 1; 

    // Flip all the set bits until we find a 1 at position y
    while (!(x & f)) { 
        x = x^f; 
        f <<= 1; 
    } 

    return x^f; // return answer but remember to flip the 1 at y
} 

Você pode fazer isso com operações bit a bit usando o descrito acima, e basta dividir seu número inteiro em partes de 8 bits para enviar 8 vezes para esta função. A parte a seguir foi retirada de Como dividir um número de 64 bits em oito valores de 8 bits? comigo adicionando na função acima

uint64_t v= _64bitVariable;
uint8_t i=0,parts[8]={0};
do parts[i++] = subtractone(v&0xFF); while (v>>=8);

É válido C ou C ++, independentemente de como alguém se deparar com isso

Não tentando criar o código, mas para um decréscimo de 1, você pode diminuir pelo grupo de 8 1s e depois verificar se os LSBs dos resultados foram "invertidos". Qualquer LSB que não tenha sido alternado indica que ocorreu uma transferência dos 8 bits adjacentes. Deve ser possível elaborar uma sequência de ANDs / ORs / XORs para lidar com isso, sem ramificações.

Concentre o trabalho em cada byte completamente sozinho e coloque-o de volta onde estava.

uint64_t sub(uint64_t arg) {
   uint64_t res = 0;

   for (int i = 0; i < 64; i+=8) 
     res += ((arg >> i) - 1 & 0xFFU) << i;

    return res;
   }