Mathieu GAILLARD

Accélération du calcul de la distance de Hamming

Dans le cadre d’un projet spécifique, j’ai besoin de calculer des distances de Hamming entre des entiers 64 bits. Pour optimiser le temps de calcul j’ai utilisé l’instruction POPCOUNT des processeurs Intel. J’ai pu observer un gain de performance significatif.

Introduction

Le but de mon projet spécifique est de benchmarker les systèmes de reverse image search. Pour mener mes tests, j’ai implémenté mon propre prototype en C++ avec la librairie pHash. Cette dernière me permet, à partir du contenu d’une image, de calculer un perceptual hash. La principale propriété de ce type de hash est de ne pas trop changer pour des images similaires. Dans le cadre de mon prototype j’indexe un grand nombre d’image, donc lorsque j’effectue une recherche, je compare le perceptual hash de mon image requête avec tous les perceptual hash de toutes les images indexées. La distance utilisée est celle de Hamming, c’est à dire que la distance entre deux perceptual hash est le nombre de bits sur lesquels les hashs sont différents. Pour accélérer le calcul de cette distance j’ai utilisé l’instruction POPCOUNT des processeurs Intel.

Optimisation du calcul

Comme la librairie pHash est sous licence GPLv3, j’ai pu accéder au code source pour vérifier comment est implémentée la fonction de calcul de la distance de Hamming. La voici :

// Implémentation de ph_hamming_distance dans pHash.cpp

int ph_hamming_distance(const ulong64 hash1,const ulong64 hash2) {
    ulong64 x = hash1^hash2;
    const ulong64 m1  = 0x5555555555555555ULL;
    const ulong64 m2  = 0x3333333333333333ULL;
    const ulong64 h01 = 0x0101010101010101ULL;
    const ulong64 m4  = 0x0f0f0f0f0f0f0f0fULL;
    x -= (x >> 1) & m1;
    x = (x & m2) + ((x >> 2) & m2);
    x = (x + (x >> 4)) & m4;
    return (x * h01)>>56;
}

Je me suis rappelé que les processeurs Intel avaient une instruction pour compter le nombre de bits à 1 dans un nombre et j’ai pensé que c’était possible de l’utiliser pour calculer la distance de Hamming. Je n’ai pas eu besoin de chercher longtemps sur internet, d’autres l’avaient déjà fait.

// Implémentation de la distance de Hamming grâce à l'instruction POPCOUNT.

unsigned int popcount_hamming_distance(uint64_t hash1, uint64_t hash2)
{
    return __builtin_popcountll(hash1 ^ hash2);
}

Attention lors de la compilation il est nécessaire de préciser l’architecture pour laquelle compiler sinon gcc va émuler l’instruction, ce qui est encore moins performant que la solution de pHash. Voici le code assembleur généré :

00000000004008dd <popcount_hamming_distance>:
  4008dd:	55                   	push   %rbp
  4008de:	48 89 e5             	mov    %rsp,%rbp
  4008e1:	48 83 ec 10          	sub    $0x10,%rsp
  4008e5:	48 89 7d f8          	mov    %rdi,-0x8(%rbp)
  4008e9:	48 89 75 f0          	mov    %rsi,-0x10(%rbp)
  4008ed:	48 8b 45 f8          	mov    -0x8(%rbp),%rax
  4008f1:	48 33 45 f0          	xor    -0x10(%rbp),%rax
  4008f5:	48 89 c7             	mov    %rax,%rdi
  4008f8:	e8 03 00 00 00       	callq  400900 <__popcountdi2>
  4008fd:	c9                   	leaveq 
  4008fe:	c3                   	retq   
  4008ff:	90                   	nop

0000000000400900 <__popcountdi2>:
  400900:	48 89 fa             	mov    %rdi,%rdx
  400903:	48 b8 55 55 55 55 55 	movabs $0x5555555555555555,%rax
  40090a:	55 55 55 
  40090d:	48 d1 ea             	shr    %rdx
  400910:	48 21 d0             	and    %rdx,%rax
  400913:	48 ba 33 33 33 33 33 	movabs $0x3333333333333333,%rdx
  40091a:	33 33 33 
  40091d:	48 29 c7             	sub    %rax,%rdi
  400920:	48 89 f8             	mov    %rdi,%rax
  400923:	48 c1 ef 02          	shr    $0x2,%rdi
  400927:	48 21 d0             	and    %rdx,%rax
  40092a:	48 21 fa             	and    %rdi,%rdx
  40092d:	48 01 d0             	add    %rdx,%rax
  400930:	48 89 c2             	mov    %rax,%rdx
  400933:	48 c1 ea 04          	shr    $0x4,%rdx
  400937:	48 01 d0             	add    %rdx,%rax
  40093a:	48 ba 0f 0f 0f 0f 0f 	movabs $0xf0f0f0f0f0f0f0f,%rdx
  400941:	0f 0f 0f 
  400944:	48 21 d0             	and    %rdx,%rax
  400947:	48 ba 01 01 01 01 01 	movabs $0x101010101010101,%rdx
  40094e:	01 01 01 
  400951:	48 0f af c2          	imul   %rdx,%rax
  400955:	48 c1 e8 38          	shr    $0x38,%rax
  400959:	c3                   	retq   
  40095a:	66 0f 1f 44 00 00    	nopw   0x0(%rax,%rax,1)

Je n’ai pas vraiment analysé en détail le code ci-dessus, ce que je sais c’est qu’à aucun moment l’instruction POPCOUNT n’est utilisée donc il n’y a pas vraiment d’accélération matérielle.

Pour préciser à gcc que l’ordinateur sur lequel va tourner l’application est capable d’exécuter les instructions POPCOUNT, il faut lui donner l’architecture pour laquelle compiler. Mon ordinateur étant équipé d’un i7 de seconde génération je mets le paramètre -march=corei7. Pendant qu’on y est on lui demande aussi de compiler en 64 bits avec le paramètre -m64. Je ne suis pas certain mais je pense que ça peut l’encourager à faire directement les traitements sur les hash 64 bits avec un registre 64 bits plutôt que deux de 32 bits. J’ai aussi utilisé le paramètre -O3 qui permet d’optimiser le code. Dans le cas de la fonction calculant la distance de Hamming, ce paramètre permet d’appliquer l’instruction POPCOUNT directement sur les registres contenant les paramètres de la fonction plutôt que de les enregistrer inutilement sur la pile. Finalement voici le code assembleur de la fonction :

0000000000400e30 <popcount_hamming_distance>:
  400e30:	48 31 f7             	xor    %rsi,%rdi
  400e33:	f3 48 0f b8 c7       	popcnt %rdi,%rax
  400e38:	c3                   	retq   
  400e39:	0f 1f 80 00 00 00 00 	nopl   0x0(%rax)

Benchmark

Pour benchmarker le temps d’exécution de ces deux fonctions je génère un tableau de N entiers non signés 64 bits et je calcule toutes les distances entre eux, il y en a donc 2 parmi N. Voici le code utilisé pour le benchmark :

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

uint64_t* GenerateArray(int n);
void FreeArray(uint64_t* array);
double MeanDistance(uint64_t* array, int n);

unsigned int ph_hamming_distance(uint64_t hash1, uint64_t hash2);
unsigned int popcount_hamming_distance(uint64_t hash1, uint64_t hash2);

int main(int argc, char *argv[])
{
    int n;
    uint64_t* array;
    double mean;
    
    if (argc != 2)
    {
        printf("Unknow parameters\n");
        printf("The only parameter is the number of integer to generate for the benchmark.\n");
        return 1;
    }
    
    n = strtol(argv[1], NULL, 10);
    
    if (n <= 0)
    {
        printf("The parameter should be a positive number.\n");
        return 1;
    }
    
    array = GenerateArray(n);
    mean = MeanDistance(array, n);
    FreeArray(array);
    
    printf("Mean distance = %f\n", mean);
    
    return 0;
}

uint64_t* GenerateArray(int n)
{
    int i;
    uint64_t* array;
    
    array = (uint64_t*)malloc(n*sizeof(uint64_t));
    
    for (i = 0;i < n;i++)
    {
        array[i] = i;
    }
    
    return array;
}

void FreeArray(uint64_t* array)
{
    free(array);
}

double MeanDistance(uint64_t* array, int n)
{
    int i, j;
    uint64_t sum = 0;
    
    for (i = 0;i < n;i++)
    {
        for (j = i + 1;j < n;j++)
        {
            #ifdef POPCNT
            sum += popcount_hamming_distance(array[i], array[j]);
            #else
            sum += ph_hamming_distance(array[i], array[j]);
            #endif
        }
    }
    
    return (double)sum / n;
}

unsigned int ph_hamming_distance(uint64_t hash1, uint64_t hash2)
{
    uint64_t x = hash1^hash2;
    const uint64_t m1  = 0x5555555555555555ULL;
    const uint64_t m2  = 0x3333333333333333ULL;
    const uint64_t h01 = 0x0101010101010101ULL;
    const uint64_t m4  = 0x0f0f0f0f0f0f0f0fULL;
    x -= (x >> 1) & m1;
    x = (x & m2) + ((x >> 2) & m2);
    x = (x + (x >> 4)) & m4;
    return (x * h01)>>56;
}

unsigned int popcount_hamming_distance(uint64_t hash1, uint64_t hash2)
{
    return __builtin_popcountll(hash1 ^ hash2);
}

Pour compiler et tester j’utilise les lignes de commande suivantes :

$ gcc -m64 -march=corei7 -O3 -o hamming hamming.c
$ time ./hamming 131072
$ gcc -m64 -march=corei7 -O3 -D POPCNT -o hamming hamming.c
$ time ./hamming 131072

Résultats

Mean distance = 557056.000000

real	0m21.573s
user	0m21.372s
sys	0m0.012s
Mean distance = 557056.000000

real	0m8.668s
user	0m8.584s
sys	0m0.004s

Les deux versions retournent la même distance moyenne, on a donc une bonne confiance quant à la validité de la nouvelle implémentation de la fonction. La version utilisant l’instruction POPCOUNT est au moins deux fois plus rapide que la version de pHash. Puisque ces deux temps d’exécution contiennent une partie constante liée à la génération des données de test, on peut en déduire que la version utilisant l’instruction POPCOUNT doit être au moins deux fois plus rapide que la version de pHash.

Discussion

La méthode de test n’est pas vraiment menée parfaitement. Je n’ai lancé le test que deux fois, les cas que je teste ne sont pas exhaustifs, je mesure le temps d’exécution du programme complet, j’ai effectué les tests dans une machine virtuelle et potentiellement d’autres biais que je n’ai pas imaginé. D’un autre côté, le résultat m’a l’air très significatif par rapport aux biais possibles.

Conclusion

La version utilisant l’instruction POPCOUNT est significativement plus rapide que la version fournie dans la librairie pHash.

Pour en savoir plus