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 131072Ré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.004sLes 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
- Zauner, Christoph. Master’s thesis, Upper Austria University of Applied Sciences, Hagenberg Campus, 2010. Implementation and Benchmarking of Perceptual Image Hash Functions [en ligne].
- Perceptual hashing dans Wikipédia, l’encyclopédie libre [en ligne]. https://en.wikipedia.org/wiki/Perceptual_hashing [Consulté le 14 Décembre 2016]