Registre AVX2 compact pour que les entiers sélectionnés soient contigus selon le masque [duplicata]

Question

Cette question a déjà des réponses ici:

AVX2, quel est le moyen le plus efficace de faire ses valises à gauche grâce à un masque ? (4 réponses)

Fermé il y a 3 ans.

Dans la question Optimisation du compactage du réseau, la première réponse indique :

Les registres SSE/AVX avec les derniers jeux d'instructions permettent une meilleure approche.Nous pouvons utiliser directement le résultat de PMOVMSKB, en le transformant en registre de contrôle pour quelque chose comme PSHUFB.

Est-ce possible avec Haswell (AVX2) ?Ou nécessite-t-il l'une des versions de l'AVX512 ?

J'ai un vecteur AVX2 contenant des int32 et un vecteur correspondant du résultat d'une comparaison.Je veux le mélanger d'une manière ou d'une autre pour que les éléments avec le msb correspondant défini dans le masque (comparer vrai) soient contigus dans l'extrémité inférieure du vecteur.

Le mieux que je puisse voir est d'obtenir un masque de bits avec _mm256_movemask_ps/vmovmskps (pas de variante *d ?), puis de l'utiliser dans une table de recherche de vecteurs 256 AVX2 pour obtenir un masque de lecture aléatoire pour la voie croisée _mm256_permutevar8x32_epi32/vpermd

Answer 1

La première chose à faire est de trouver une fonction scalaire rapide.Voici une version qui n'utilise pas de branche.

inline int compact(int *x, int *y, const int n) {
    int cnt = 0;
    for(int i=0; i<n; i++) {
        int cut = x[i]!=0;
        y[cnt] = cut*x[i];
        cnt += cut;
    }
    return cnt;
}

Le meilleur résultat avec SIMD dépend probablement de la distribution des zéros.Si c'est clairsemé ou dense.Le code suivant devrait bien fonctionner pour les distributions clairsemées ou denses.Par exemple de longues séries de zéros et de non-zéros.Si la répartition est plus uniforme, je ne sais pas si ce code aura un quelconque avantage.Mais cela donnera quand même le résultat correct.

Voici une version AVX2 que j'ai testée.

int compact_AVX2(int *x, int *y, int n) {
    int i =0, cnt = 0;
    for(i=0; i<n-8; i+=8) {
        __m256i x4 = _mm256_loadu_si256((__m256i*)&x[i]);
        __m256i cmp = _mm256_cmpeq_epi32(x4, _mm256_setzero_si256());
        int mask = _mm256_movemask_epi8(cmp);
        if(mask == -1) continue; //all zeros
        if(mask) {
            cnt += compact(&x[i],&y[cnt], 8);
        }
        else {
            _mm256_storeu_si256((__m256i*)&y[cnt], x4);
            cnt +=8;
        }       
    }
    cnt += compact(&x[i], &y[cnt], n-i); // cleanup for n not a multiple of 8
    return cnt;
}

Voici la version SSE2 que j'ai testée.

int compact_SSE2(int *x, int *y, int n) {
    int i =0, cnt = 0;
    for(i=0; i<n-4; i+=4) {
        __m128i x4 = _mm_loadu_si128((__m128i*)&x[i]);
        __m128i cmp = _mm_cmpeq_epi32(x4, _mm_setzero_si128());
        int mask = _mm_movemask_epi8(cmp);
        if(mask == 0xffff) continue; //all zeroes
        if(mask) {
            cnt += compact(&x[i],&y[cnt], 4);
        }
        else {
            _mm_storeu_si128((__m128i*)&y[cnt], x4);
            cnt +=4;
        }       
    }
    cnt += compact(&x[i], &y[cnt], n-i); // cleanup for n not a multiple of 4
    return cnt;
}

Voici un test complet

#include <stdio.h>
#include <stdlib.h>
#if defined (__GNUC__) && ! defined (__INTEL_COMPILER)
#include <x86intrin.h>                
#else
#include <immintrin.h>                
#endif

#define N 50

inline int compact(int *x, int *y, const int n) {
    int cnt = 0;
    for(int i=0; i<n; i++) {
        int cut = x[i]!=0;
        y[cnt] = cut*x[i];
        cnt += cut;
    }
    return cnt;
}

int compact_SSE2(int *x, int *y, int n) {
        int i =0, cnt = 0;
        for(i=0; i<n-4; i+=4) {
            __m128i x4 = _mm_loadu_si128((__m128i*)&x[i]);
            __m128i cmp = _mm_cmpeq_epi32(x4, _mm_setzero_si128());
            int mask = _mm_movemask_epi8(cmp);
            if(mask == 0xffff) continue; //all zeroes
            if(mask) {
                cnt += compact(&x[i],&y[cnt], 4);
            }
            else {
                _mm_storeu_si128((__m128i*)&y[cnt], x4);
                cnt +=4;
            }       
        }
        cnt += compact(&x[i], &y[cnt], n-i); // cleanup for n not a multiple of 4
        return cnt;
    }

int compact_AVX2(int *x, int *y, int n) {
    int i =0, cnt = 0;
    for(i=0; i<n-8; i+=8) {
        __m256i x4 = _mm256_loadu_si256((__m256i*)&x[i]);
        __m256i cmp = _mm256_cmpeq_epi32(x4, _mm256_setzero_si256());
        int mask = _mm256_movemask_epi8(cmp);
        if(mask == -1) continue; //all zeros
        if(mask) {
            cnt += compact(&x[i],&y[cnt], 8);
        }
        else {
            _mm256_storeu_si256((__m256i*)&y[cnt], x4);
            cnt +=8;
        }       
    }
    cnt += compact(&x[i], &y[cnt], n-i); // cleanup for n not a multiple of 8
    return cnt;
}

int main() {
    int x[N], y[N];
    for(int i=0; i<N; i++) x[i] = rand()%10;
    //int cnt = compact_SSE2(x,y,N);
    int cnt = compact_AVX2(x,y,N);
    for(int i=0; i<N; i++) printf("%d ", x[i]); printf("\n");
    for(int i=0; i<cnt; i++) printf("%d ", y[i]); printf("\n");
}