Soustraire des entiers 8 bits compressés dans un entier 64 bits par 1 en parallèle, SWAR sans carte SIMD matérielle

Si j'ai un entier 64 bits que j'interprète comme un tableau d'entiers 8 bits compressés avec 8 éléments. J'ai besoin de soustraire la constante 1de chaque entier compressé tout en gérant le débordement sans que le résultat d'un élément n'affecte le résultat d'un autre élément.

J'ai ce code pour le moment et cela fonctionne mais j'ai besoin d'une solution qui effectue la soustraction de chaque entier 8 bits compressé en parallèle et n'effectue pas d'accès à la mémoire. Sur x86, je pourrais utiliser des instructions SIMD comme psubbcelle-ci soustrait les entiers 8 bits compressés en parallèle, mais la plate-forme pour laquelle je code ne prend pas en charge les instructions SIMD. (RISC-V dans ce cas).

J'essaie donc de faire SWAR (SIMD dans un registre) pour annuler manuellement la propagation de report entre les octets d'un uint64_t, en faisant quelque chose d'équivalent à ceci:

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

Je pense que vous pourriez le faire avec des opérateurs au niveau du bit mais je ne suis pas sûr. Je recherche une solution qui n'utilise pas les instructions SIMD. Je cherche une solution en C ou C ++ qui soit assez portable ou juste la théorie derrière pour que je puisse implémenter ma propre solution.

Si vous avez un processeur avec des instructions SIMD efficaces, SSE / MMX paddb( _mm_add_epi8) est également viable. La réponse de Peter Cordes décrit également la syntaxe vectorielle GNU C (gcc / clang) et la sécurité pour UB à alias strict. J'encourage fortement à revoir également cette réponse.

Le faire vous-même uint64_test entièrement portable, mais nécessite toujours des précautions pour éviter les problèmes d'alignement et l'UB à alias strict lors de l'accès à un uint8_ttableau avec un uint64_t*. Vous avez laissé cette partie hors de question en commençant par vos données dans un uint64_tdéjà, mais pour GNU C un may_aliastypedef résout le problème (voir la réponse de Peter pour cela ou memcpy).

Sinon, vous pourriez allouer / déclarer vos données en tant que uint64_tet y accéder via uint8_t*quand vous voulez des octets individuels. unsigned char*est autorisé à alias n'importe quoi afin de contourner le problème pour le cas spécifique des éléments 8 bits. (S'il uint8_texiste, il est probablement sûr de supposer que c'est le cas unsigned char.)

Notez qu'il s'agit d'un changement par rapport à un algorithme incorrect antérieur (voir l'historique des révisions).

Ceci est possible sans boucle pour une soustraction arbitraire, et devient plus efficace pour une constante connue comme 1dans chaque octet. L'astuce principale consiste à empêcher l'exécution de chaque octet en définissant le bit haut, puis à corriger le résultat de la soustraction.

Nous allons optimiser légèrement la technique de soustraction donnée ici . Ils définissent:

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

avec Hdéfini comme 0x8080808080808080U(c'est-à-dire les MSB de chaque entier compressé). Pour une décrémentation, yest 0x0101010101010101U.

Nous savons que ytous ses MSB sont clairs, nous pouvons donc ignorer l'une des étapes du masque (c'est y & ~H-à- dire la même que ydans notre cas). Le calcul se déroule comme suit:

1. Nous définissons les MSB de chaque composant de xsur 1, afin qu'un emprunt ne puisse pas se propager au-delà du MSB vers le composant suivant. Appelez cela l'entrée ajustée.
2. Nous soustrayons 1 de chaque composant, en soustrayant 0x01010101010101de l'entrée corrigée. Cela n'entraîne pas d'emprunts entre composants grâce à l'étape 1. Appelez cela la sortie ajustée.
3. Nous devons maintenant corriger le MSB du résultat. Nous xor la sortie ajustée avec les MSB inversés de l'entrée d'origine pour finir de fixer le résultat.

L'opération peut s'écrire:

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

De préférence, cela est inséré par le compilateur (utilisez les directives du compilateur pour forcer cela), ou l'expression est écrite en ligne dans le cadre d'une autre fonction.

Testcases:

in:  0000000000000000
out: ffffffffffffffff

in:  f200000015000013
out: f1ffffff14ffff12

in:  0000000000000100
out: ffffffffffff00ff

in:  808080807f7f7f7f
out: 7f7f7f7f7e7e7e7e

in:  0101010101010101
out: 0000000000000000

Détails des performances

Voici l'assemblage x86_64 pour une seule invocation de la fonction. Pour de meilleures performances, il doit être aligné dans l'espoir que les constantes puissent vivre dans un registre aussi longtemps que possible. Dans une boucle étroite où les constantes vivent dans un registre, le décrément réel prend cinq instructions: ou + pas + et + ajouter + xor après optimisation. Je ne vois pas d'alternatives qui pourraient battre l'optimisation du compilateur.

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

Avec certains tests IACA de l'extrait suivant:

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

nous pouvons montrer que sur une machine Skylake, effectuer la décrémentation, le xor et la comparaison + le saut peut être effectué à un peu moins de 5 cycles par itération:

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

(Bien sûr, sur x86-64, vous devez simplement charger ou movqdans un reg XMM pour paddb, il pourrait donc être plus intéressant de voir comment il se compile pour un ISA comme RISC-V.)

Pour RISC-V, vous utilisez probablement GCC / clang.

Fait amusant: GCC connaît certaines de ces astuces SWAR bithack (présentées dans d'autres réponses) et peut les utiliser pour vous lors de la compilation de code avec des vecteurs natifs GNU C pour des cibles sans instructions SIMD matérielles. (Mais clang pour RISC-V le déroulera naïvement en opérations scalaires, vous devez donc le faire vous-même si vous voulez de bonnes performances entre les compilateurs).

Un avantage de la syntaxe vectorielle native est que lors du ciblage d'une machine avec un SIMD matériel, il l'utilisera au lieu de vectoriser automatiquement votre bithack ou quelque chose d'horrible comme ça.

Il facilite l'écriture d' vector -= scalaropérations; la syntaxe Just Works, diffusant implicitement aka éclaboussant le scalaire pour vous.

Notez également qu'une uint64_t*charge provenant d'unuint8_t array[] UB à alias strict, soyez donc prudent. (Voir aussi Pourquoi le strlen de glibc doit-il être si compliqué pour s'exécuter rapidement? Re: rendre le bithacks SWAR strict-aliasing sûr en C pur). Vous voudrez peut-être quelque chose comme ça pour déclarer un uint64_tque vous pouvez casté par pointeur pour accéder à d'autres objets, comme la façon dont char*fonctionne dans ISO C / C ++.

utilisez-les pour obtenir des données uint8_t dans un uint64_t à utiliser avec d'autres réponses:

// 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'autre façon de faire des charges de sécurité aliasing est avec memcpyenuint64_t , ce qui supprime également l' alignof(uint64_texigence d'alignement). Mais sur les ISA sans charges non alignées efficaces, gcc / clang ne s'alignent pas et ne s'optimisent pas memcpylorsqu'ils ne peuvent pas prouver que le pointeur est aligné, ce qui serait désastreux pour les performances.

TL: DR: votre meilleur pari est de déclarer vos données commeuint64_t array[...] ou de les allouer dynamiquement commeuint64_t , ou de préférencealignas(16) uint64_t array[]; Cela garantit l'alignement sur au moins 8 octets, ou 16 si vous spécifiez alignas.

Puisque uint8_tc'est presque certainement unsigned char*, il est sûr d'accéder aux octets d'une uint64_tviauint8_t* (mais pas l'inverse pour un tableau uint8_t). Donc, pour ce cas spécial où le type d'élément étroit est unsigned char, vous pouvez contourner le problème d'alias strict car il charest spécial.

Exemple de syntaxe vectorielle native GNU C:

Les vecteurs natifs GNU C sont toujours autorisés à alias avec leur type sous-jacent (par exemple, int __attribute__((vector_size(16)))peuvent alias en toute sécurité, intmais pas floatouuint8_t ou autre chose.

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

Pour RISC-V sans HW SIMD, vous pouvez utiliser vector_size(8)pour exprimer uniquement la granularité que vous pouvez utiliser efficacement et faire deux fois plus de vecteurs plus petits.

Mais vector_size(8) compile très bêtement pour x86 avec GCC et clang: GCC utilise des bithacks SWAR dans les registres d'entiers GP, clang décompresse en éléments de 2 octets pour remplir un registre XMM de 16 octets puis recompresse. (MMX est tellement obsolète que GCC / clang ne prend même pas la peine de l'utiliser, du moins pas pour x86-64.)

Mais avec vector_size (16)( Godbolt ) on obtient le movdqa/ attendu paddb. (Avec un vecteur tout-en-un généré par pcmpeqd same,same). Avec-march=skylake nous obtenons toujours deux opérations XMM distinctes au lieu d'un YMM, donc malheureusement les compilateurs actuels ne "vectorisent" pas automatiquement les opérations vectorielles en vecteurs plus larges: /

Pour AArch64, ce n'est pas si mal à utiliser vector_size(8)( Godbolt ); ARM / AArch64 peut fonctionner de manière native en blocs de 8 ou 16 octets avec dou qregistres.

Donc, vous voulez probablement vector_size(16)compiler avec si vous voulez des performances portables sur x86, RISC-V, ARM / AArch64 et POWER . Cependant, certains autres ISA font SIMD dans des registres entiers 64 bits, comme MIPS MSA je pense.

vector_size(8)facilite la lecture de l'asm (un seul registre de données): 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

Je pense que c'est la même idée de base que les autres réponses sans boucle; empêchant le report puis fixant le résultat.

Ceci est 5 instructions ALU, pire que la réponse du haut je pense. Mais il semble que la latence du chemin critique ne soit que de 3 cycles, avec deux chaînes de 2 instructions menant chacune au XOR. La réponse de @Reinstate Monica - ζ - se compile en une chaîne dep à 4 cycles (pour x86). Le débit de boucle à 5 cycles est goulot d'étranglement en incluant également unsub sur le chemin critique, et la boucle fait goulot d'étranglement sur la latence.

Cependant, cela est inutile avec clang. Il n'ajoute et ne stocke même pas dans le même ordre qu'il a chargé, donc il ne fait même pas de bons pipelining logiciels!

# 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

Je voudrais souligner que le code que vous avez écrit est effectivement vectorisé une fois que vous commencez à traiter plus d'un uint64_t.

https://godbolt.org/z/J9DRzd

Vous pouvez vous assurer que la soustraction ne déborde pas, puis corriger le bit élevé:

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

Je ne sais pas si c'est ce que vous voulez mais il fait les 8 soustractions en parallèle:

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

Explication: Le masque binaire commence par un 1 dans chacun des nombres à 8 bits. Nous le xor avec notre argument. Si nous avions un 1 à cet endroit, nous avons soustrait 1 et nous devons arrêter. Cela se fait en mettant le bit correspondant à 0 dans new_mask. Si nous avions un 0, nous le mettons à 1 et devons effectuer le report, donc le bit reste à 1 et nous décalons le masque vers la gauche. Vous feriez mieux de vérifier par vous-même si la génération du nouveau masque fonctionne comme prévu, je pense que oui, mais un deuxième avis ne serait pas mauvais.

PS: je ne sais pas vraiment si la vérification mask_cp non-nullité dans la boucle peut ralentir le programme. Sans cela, le code serait toujours correct (puisque le masque 0 ne fait rien) et il serait beaucoup plus facile pour le compilateur de faire le déroulement de la boucle.

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
} 

Vous pouvez le faire avec des opérations au niveau du bit en utilisant ce qui précède, et il vous suffit de diviser votre entier en morceaux de 8 bits pour envoyer 8 fois dans cette fonction. La partie suivante est tirée de Comment diviser un nombre 64 bits en huit valeurs 8 bits? avec moi en ajoutant la fonction ci-dessus

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

C'est du C ou du C ++ valide quelle que soit la façon dont quelqu'un rencontre ce

Je ne vais pas essayer de trouver le code, mais pour une décrémentation de 1, vous pouvez décrémenter par le groupe de 8 1 et vérifier ensuite que les LSB des résultats ont "basculé". Tout LSB qui n'a pas basculé indique qu'un report s'est produit à partir des 8 bits adjacents. Il devrait être possible d'élaborer une séquence de AND / OR / XOR pour gérer cela, sans aucune branche.

Concentrez le travail sur chaque octet entièrement seul, puis remettez-le à sa place.

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