Comment scanner efficacement 2 masques de bits en alternant à chaque itération

Question

Donnés sont 2 masques de bits, qui devraient être accessibles en alternance (0,1,0,1...). J'essaie d'obtenir une solution efficace en termes de temps d'exécution, mais je ne trouve pas de meilleure façon que l'exemple suivant.

uint32_t masque[2] { ... };
uint8_t indice_masque = 0;
uint32_t f = _tzcnt_u32(masque[indice_masque]);
while (f < 32) {
    // élément ajouté au vecteur de résultat supprimé, car non pertinent pour la question elle-même
    masque[0] >>= f + 1;
    masque[1] >>= f + 1;
    indice_masque ^= 1;
    f = _tzcnt_u32(masque[indice_masque]);
}

La sortie ASM (MSVC, x64) semble assez encombrée.

inc         r9  
add         r9,rcx  
mov         eax,esi  
mov         qword ptr [rdi+rax*8],r9  
inc         esi  
lea         rax,[rcx+1]  
shrx        r11d,r11d,eax  
mov         dword ptr [rbp],r11d  
shrx        r8d,r8d,eax  
mov         dword ptr [rbp+4],r8d  
xor         r10b,1  
movsx       rax,r10b  
tzcnt       ecx,dword ptr [rbp+rax*4]  
mov         ecx,ecx  
cmp         rcx,20h  
jb          main+240h (07FF632862FD0h)  
cmp         r9,20h  
jb          main+230h (07FF632862FC0h) 

Est-ce que quelqu'un a un conseil?

(Ceci est une suite à Résoudre la dépendance des données de boucle avec SIMD - trouver les transitions entre -1 et +1 dans un tableau int8_t de valeurs sgn en utilisant SIMD pour créer les masques de bits)

Mise à jour

Je me demande si une solution potentielle pourrait utiliser SIMD en chargeant des morceaux des deux flux de bits dans un registre (AVX2 dans mon cas) comme ceci:

|m0[0]|m1[0]|m0[1]|m1[1]|m0[2]|m1[2]|m0[n+1]|m1[n+1]|

ou

1 registre avec des morceaux par flux

|m0[0]|m0[1]|m0[2]|m0[n+1]|

|m1[0]|m1[1]|m1[2]|m1[n+1]|

ou diviser le flux en morceaux de même taille et traiter autant de voies que possible dans le registre à la fois. Supposons que nous ayons 256*10 éléments qui pourraient se retrouver dans 10 itérations comme ceci: |m0[0]|m0[256]|m0[512]|...| |m1[0]|m1[256]|m1[512]|...| et traiter la jointure séparément

Je ne suis pas sûr si cela pourrait être une manière d'obtenir plus d'itérations par cycle et de limiter le besoin de balayages de bits horizontaux, d'opérations de décalage/nettoyage et d'éviter les branches.

Answer 1

C'est assez difficile d'optimiser cette boucle. Le principal problème est que chaque itération de la boucle dépend de la précédente et même les instructions dans les boucles sont dépendantes. Cela crée une longue chaîne pratiquement séquentielle d'instructions à exécuter. En conséquence, le processeur ne peut pas exécuter cela efficacement. De plus, certaines instructions dans cette chaîne ont une latence assez élevée: tzcnt a une latence de 3 cycles sur les processeurs Intel et les accès L1 ont une latence de 3 cycles.

Une solution consiste à travailler directement avec des registres au lieu d'un tableau avec des accès indirects afin de réduire la longueur de la chaîne et surtout les instructions avec la latence la plus élevée. Cela peut être fait en déroulant la boucle deux fois et en divisant le problème en deux parties distinctes :

uint32_t m0 = mask[0];
uint32_t m1 = mask[1];
uint8_t mask_index = 0;

if(mask_index == 0) {
    uint32_t f = _tzcnt_u32(m0);

    while (f < 32) {
        m1 >>= f + 1;
        m0 >>= f + 1;
        f = _tzcnt_u32(m1);

        if(f >= 32)
            break;

        m0 >>= f + 1;
        m1 >>= f + 1;
        f = _tzcnt_u32(m0);
    }
}
else {
    uint32_t f = _tzcnt_u32(m1);

    while (f < 32) {
        m0 >>= f + 1;
        m1 >>= f + 1;
        f = _tzcnt_u32(m1);

        if(f >= 32)
            break;

        m0 >>= f + 1;
        m1 >>= f + 1;
        f = _tzcnt_u32(m0);
    }
}

// Si le masque est nécessaire, m0 et m1 doivent être stockés à nouveau dans le masque.

Cela devrait être un peu plus rapide, surtout en raison d'un chemin critique plus court mais aussi parce que les deux décalages peuvent être exécutés en parallèle. Voici le code d'assemblage résultant :

$loop:
        inc     ecx
        shr     edx, cl
        shr     eax, cl
        tzcnt   ecx, edx

        cmp     ecx, 32
        jae     SHORT $end_loop

        inc     ecx
        shr     eax, cl
        shr     edx, cl
        tzcnt   ecx, eax

        cmp     ecx, 32
        jb      SHORT $loop

Remarquez que les processeurs x86 modernes peuvent fusionner les instructions cmp+jae et cmp+jb et la prédiction de branchement peut supposer que la boucle va se poursuivre donc elle se trompera simplement sur le dernier saut conditionnel. Sur les processeurs Intel, le chemin critique est composé d'une latence de 1 cycle pour inc, une latence de 1 cycle pour shr, une latence de 3 cycles pour tzcnt, ce qui donne 5 cycles par tour (1 tour = 1 itération de la boucle initiale). Sur les processeurs AMD de type Zen, c'est de 1+1+2=4 cycles, ce qui est très bon. Optimiser cela davantage semble être très difficile.

Une optimisation possible pourrait être d'utiliser une table de recherche pour calculer les bits de poids faible de m0 et m1 en plus grands pas. Cependant, une récupération de table de recherche a une latence de 3 cycles, peut entraîner des miss coûteux dans le cache en pratique, nécessite plus de mémoire et rend le code significativement plus complexe étant donné que le nombre de bits de zéro de traînée peut être assez important (par exemple 28 bits). Ainsi, je ne suis pas sûr que ce soit une bonne idée même si cela vaut certainement la peine d'essayer.

Answer 2

Voici une autre façon, non testée. Des gens de partout sur internet recommandent de ne pas utiliser goto, mais parfois, comme pour votre cas d'utilisation, la fonctionnalité est utile.

// Prenez 2 autres de ces masques, ou si vous n'en avez pas, renvoyez false
bool loadMasks( uint32_t& mask1, uint32_t& mask2 );
// Consommez la valeur trouvée
void consumeIndex( size_t index );

void processMasks()
{
    size_t sourceOffset = 0;
    uint32_t mask0, mask1;
    // Sautez les zéros initiaux
    while( true )
    {
        if( !loadMasks( mask0, mask1 ) )
            return;
        if( 0 != ( mask0 | mask1 ) )
            break;
        sourceOffset += 32;
    }

    constexpr uint32_t minusOne = ~(uint32_t)0;
    uint32_t idx;

    // Déterminez l'état initial et sautez
    if( _tzcnt_u32( mask0 ) > _tzcnt_u32( mask1 ) )
        goto testMask1;

    // Boucle principale ci-dessous
testMask0:
    idx = _tzcnt_u32( mask0 );
    if( idx >= 32 )
    {
        sourceOffset += 32;
        if( !loadMasks( mask0, mask1 ) )
            return;
        goto testMask0;
    }
    consumeIndex( sourceOffset + idx );
    mask1 &= minusOne << ( idx + 1 );

testMask1:
    idx = _tzcnt_u32( mask1 );
    if( idx >= 32 )
    {
        sourceOffset += 32;
        if( !loadMasks( mask0, mask1 ) )
            return;
        goto testMask1;
    }
    consumeIndex( sourceOffset + idx );
    mask0 &= minusOne << ( idx + 1 );
    goto testMask0;
}