Skip to content

Sottrazione di interi a 8 bit impacchettati in un intero a 64 bit per 1 in parallelo, SWAR senza SIMD hardware

Non dimenticare che in informatica qualsiasi problema ha quasi sempre risoluzioni diverse, allo stesso modo qui condividiamo il più ottimale e il migliore.

Soluzione:

Se si dispone di una CPU con istruzioni SIMD efficienti, SSE/MMX paddb (_mm_add_epi8) è anche praticabile. La risposta di Peter Cordes descrive anche la sintassi vettoriale di GNU C (gcc/clang) e la sicurezza per lo strict-aliasing UB. Invito caldamente a leggere anche questa risposta.

Fare da soli con uint64_t è completamente portabile, ma richiede comunque attenzione per evitare problemi di allineamento e UB strict-aliasing quando si accede a un elemento uint8_t con un array uint64_t*. Si è tralasciata questa parte della questione iniziando con i dati in un file uint64_t ma per GNU C un may_alias risolve il problema (si veda la risposta di Peter per questo oppure memcpy).

Altrimenti si potrebbero allocare/dichiarare i dati come uint64_t e accedervi tramite uint8_t* quando si vogliono i singoli byte. unsigned char* può essere alias di qualsiasi cosa, quindi evita il problema per il caso specifico degli elementi a 8 bit. (Se uint8_t esiste, si può presumere che si tratti di un elemento unsigned char.)


Si noti che questo è un cambiamento rispetto a un precedente algoritmo errato (si veda la cronologia delle revisioni).

Questo è possibile senza looping per una sottrazione arbitraria e diventa più efficiente per una costante nota come 1 in ogni byte. Il trucco principale consiste nel prevenire il carry-out da ogni byte impostando il bit alto, quindi correggere il risultato della sottrazione.

Ottimizzeremo leggermente la tecnica di sottrazione qui descritta. Si definiscono:

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

con H definito come 0x8080808080808080U (cioè gli MSB di ogni intero impacchettato). Per un decremento, y è 0x0101010101010101U.

Sappiamo che y ha tutti i suoi MSB liberi, quindi possiamo saltare uno dei passaggi di mascheramento (ovvero y & ~H è uguale a y nel nostro caso). Il calcolo procede come segue:

  1. Impostiamo gli MSB di ciascun componente di x a 1, in modo che un prestito non possa propagarsi oltre l'MSB al componente successivo. Questo è l'ingresso corretto.
  2. Sottraiamo 1 da ogni componente, sottraendo 0x01010101010101 dall'ingresso corretto. Grazie al passo 1, questa operazione non provoca la perdita di peso tra i componenti. Questo è l'output corretto.
  3. Ora dobbiamo correggere l'MSB del risultato. Per correggere il risultato, si esegue uno xor tra l'uscita corretta e gli MSB invertiti dell'ingresso originale.

L'operazione può essere scritta come:

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

Preferibilmente, questa operazione è inlineata dal compilatore (usare le direttive del compilatore per forzarla), oppure l'espressione è scritta inline come parte di un'altra funzione.

Casi di prova:

in:  0000000000000000
out: ffffffffffffffff

in:  f200000015000013
out: f1ffffff14ffff12

in:  0000000000000100
out: ffffffffffff00ff

in:  808080807f7f7f7f
out: 7f7f7f7f7e7e7e7e

in:  0101010101010101
out: 0000000000000000

Dettagli sulle prestazioni

Ecco l'assembly x86_64 per una singola invocazione della funzione. Per ottenere prestazioni migliori, dovrebbe essere inlineata con la speranza che le costanti possano vivere in un registro il più a lungo possibile. In un ciclo stretto in cui le costanti vivono in un registro, il decremento effettivo richiede cinque istruzioni: or+not+e+add+xor dopo l'ottimizzazione. Non vedo alternative che possano battere l'ottimizzazione del compilatore.

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

Con alcuni test IACA del seguente frammento:

// 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;
}

possiamo dimostrare che su una macchina Skylake, l'esecuzione di decremento, xor e confronto+jump può essere eseguita a poco meno di 5 cicli per iterazione:

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  |
--------------------------------------------------------------------------------------------------

(Naturalmente, su x86-64 basterebbe caricare o movq in un reg XMM per paddbquindi potrebbe essere più interessante vedere come si compila per un'ISA come RISC-V).

Per RISC-V probabilmente si usa GCC/clang.

Fatto curioso: GCC conosce alcuni di questi trucchi di SWAR bithack (mostrati in altre risposte) e può usarli per voi quando compilate codice con vettori nativi GNU C per target senza istruzioni SIMD hardware. (Ma clang per RISC-V lo srotola ingenuamente in operazioni scalari, quindi dovete farlo da soli se volete buone prestazioni tra i compilatori).

Un vantaggio della sintassi vettoriale nativa è che, quando si punta a una macchina con SIMD hardware, userà questa invece di auto-vettorizzare il bithack o qualcosa di orribile come questo.

Rende facile scrivere vector -= scalar la sintassi funziona e basta, trasmettendo implicitamente lo scalare al posto dell'utente.


Si noti anche che un uint64_t* da un oggetto uint8_t array[] è strict-aliasing UB, quindi bisogna fare attenzione. (Si veda anche Perché lo strlen di glibc deve essere così complicato per funzionare velocemente? per rendere i bithack SWAR sicuri per lo strict-aliasing in puro C). Potreste volere qualcosa di simile per dichiarare un oggetto uint64_t con cui si può fare un pointer-cast per accedere a qualsiasi altro oggetto, come nel caso di char* funziona in ISO C / C++.

si usano per ottenere dati uint8_t in un uint64_t da usare con altre risposte:

// 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)));

L'altro modo per fare carichi sicuri per gli alias è con memcpy in un oggetto uint64_tche rimuove anche l'elemento alignof(uint64_t), il requisito di allineamento. Ma sulle ISA prive di carichi non allineati efficienti, gcc/clang non inlinizzano e ottimizzano memcpy quando non possono dimostrare che il puntatore è allineato, il che sarebbe disastroso per le prestazioni.

TL:DR: la cosa migliore è dichiarare i dati come uint64_t array[...] o allocarli dinamicamente come uint64_t, o preferibilmente alignas(16) uint64_t array[]; In questo modo si garantisce l'allineamento ad almeno 8 byte, o 16 se si specifica alignas.

Da uint8_t è quasi certamente unsigned char*è sicuro accedere ai byte di un elemento uint64_t tramite uint8_t* (ma non viceversa per un array uint8_t). Quindi, per questo caso speciale in cui il tipo di elemento stretto è unsigned charè possibile evitare il problema dello strict-aliasing perché char è speciale.


Esempio di sintassi vettoriale nativa GNU C:

I vettori nativi GNU C possono sempre avere un alias con il loro tipo sottostante (ad esempio, int __attribute__((vector_size(16))) ).int __attribute__((vector_size(16)))può tranquillamente avere un alias con int ma non float o uint8_t o qualsiasi altra cosa.

#include 
#include 

// 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.
}

Per RISC-V senza HW SIMD, si potrebbe usare vector_size(8) per esprimere solo la granularità che si può usare in modo efficiente e fare il doppio dei vettori più piccoli.

Ma vector_size(8) compila in modo molto stupido per x86 sia con GCC che con clang: GCC usa i bithack SWAR nei registri GP-integer, clang scompatta in elementi da 2 byte per riempire un registro XMM da 16 byte e poi ricompatta. (MMX è così obsoleto che GCC/clang non si preoccupano nemmeno di usarlo, almeno non per x86-64).

Ma con vector_size (16) (Godbolt) otteniamo l'atteso movdqa / paddb. (Con un vettore all-ones generato da pcmpeqd same,same). Con -march=skylake otteniamo ancora due operazioni XMM separate invece di una YMM, quindi sfortunatamente i compilatori attuali non "auto-vettorizzano" le operazioni vettoriali in vettori più ampi :/

Per AArch64, non è così male usare vector_size(8) (Godbolt); ARM/AArch64 può lavorare nativamente in pezzi da 8 o 16 byte con d o q registri.

Quindi probabilmente si vuole vector_size(16) con cui compilare se si vogliono prestazioni portabili tra x86, RISC-V, ARM/AArch64 e POWER.. Tuttavia, alcune altre ISA fanno SIMD all'interno dei registri interi a 64 bit, come MIPS MSA, credo.

vector_size(8) rende più facile guardare l'asm (un solo registro di dati): Esploratore del compilatore Godbolt

# 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

Penso che sia la stessa idea di base delle altre risposte non in loop: prevenire il carry e poi correggere il risultato.

Si tratta di 5 istruzioni ALU, peggio della prima risposta, credo. Ma sembra che la latenza del percorso critico sia di soli 3 cicli, con due catene di 2 istruzioni ciascuna che portano allo XOR. @Reinstate Monica - La risposta di ζ-- si compila con una catena dep di 4 cicli (per x86). Il throughput del ciclo a 5 cicli è ostacolato dall'inclusione di un'ingenua istruzione sub sul percorso critico, e il ciclo ha un collo di bottiglia sulla latenza.

Tuttavia, questo è inutile con clang. Non aggiunge e memorizza nemmeno nello stesso ordine in cui è stato caricato, quindi non sta nemmeno facendo un buon pipelining 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

Vorrei far notare che il codice che avete scritto in realtà vettorializza una volta che iniziate a trattare più di un singolo uint64_t.

https://godbolt.org/z/J9DRzd



Utilizzate il nostro motore di ricerca

Ricerca
Generic filters

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.