La chasse à la mise en œuvre la plus rapide de Hamming Distance C

Vous pouvez faire en sorte que votre comparaison compare plus d’octets à la fois en effectuant un opérateur au niveau du bit sur la taille de l’entier natif.

Dans votre code, vous comparez l’égalité d’un octet à la fois, mais votre processeur peut comparer au moins un mot dans un seul cycle et 8 octets s’il s’agit de x86-64. Les performances exactes dépendent bien sûr de l’architecture de la CPU.

Mais si vous parcouriez les deux pointeurs avec une foulée de 8, cela pourrait certainement être plus rapide dans certains scénarios. Quand il doit lire les chaînes de la mémoire principale, le temps de chargement de la mémoire va réellement dominer la performance. Mais si les chaînes se trouvent dans le cache de la CPU, vous pouvez peut-être effectuer un XOR et interpréter les résultats en testant où, dans la valeur 64 bits, les bits sont modifiés.

Il est possible de compter les compartiments non nuls avec une variante de l’algorithme SWAR à partir de 0x33333333 au lieu de 0x55555555.

L’algorithme sera plus difficile à utiliser car il nécessitera l’utilisation de pointeurs uint64_t dotés d’un alignement correct de la mémoire. Vous aurez besoin d’un préambule et d’un post-scriptum couvrant les octets restants. Peut-être devriez-vous lire l’assembly des sorties du compilateur et voir s’il ne fait pas quelque chose de plus intelligent avant d’essayer quelque chose de plus compliqué en code.

Au lieu de

 if (*a != *b) ++num_mismatches; 

cela serait plus rapide sur certaines architectures (avec des octets de 8 bits) car cela évite la twig:

 int bits = *a ^ *b; bits |= bits >> 4; bits |= bits >> 2; bits |= bits >> 1; num_mismatches += bits & 1; 

Que diriez-vous du déroulement de la boucle:

 while (na >= 8){ num_mismatches += (a[0] != b[0]); num_mismatches += (a[1] != b[1]); num_mismatches += (a[2] != b[2]); num_mismatches += (a[3] != b[3]); num_mismatches += (a[4] != b[4]); num_mismatches += (a[5] != b[5]); num_mismatches += (a[6] != b[6]); num_mismatches += (a[7] != b[7]); a += 8; b += 8; na -= 8; } if (na >= 4){ num_mismatches += (a[0] != b[0]); num_mismatches += (a[1] != b[1]); num_mismatches += (a[2] != b[2]); num_mismatches += (a[3] != b[3]); a += 4; b += 4; na -= 4; } if (na >= 2){ num_mismatches += (a[0] != b[0]); num_mismatches += (a[1] != b[1]); a += 2; b += 2; na -= 2; } if (na >= 1){ num_mismatches += (a[0] != b[0]); a += 1; b += 1; na -= 1; } 

De plus, si vous savez qu’il y a de longues étendues de caractères égaux, vous pouvez lancer les pointeurs sur long* et les comparer 4 à la fois, et ne regarder que les caractères individuellement. Ce code est basé sur le fait que memset et memcpy soient rapides. Il copie les chaînes dans de long tableaux pour 1) éliminer les problèmes d’alignement et 2) append des zéros à un nombre entier de s long . Lorsqu’il compare chaque paire de s long , s’ils ne sont pas égaux, il pointe les pointeurs sur char* et compte les caractères inégaux. La boucle principale pourrait également être déroulée, semblable à la précédente.

 long la[BIG_ENOUGH]; long lb[BIG_ENOUGH]; memset(la, 0, sizeof(la)); memset(lb, 0, sizeof(lb)); memcpy(la, a, na); memcpy(lb, b, nb); int nla = (na + 3) & ~3; // assuming sizeof(long) = 4 long *pa = la, *pb = lb; while(nla >= 1){ if (pa[0] != pb[0]){ num_mismatches += (((char*)pa[0])[0] != ((char*)pb[0])[0]) + (((char*)pa[0])[1] != ((char*)pb[0])[1]) + (((char*)pa[0])[2] != ((char*)pb[0])[2]) + (((char*)pa[0])[3] != ((char*)pb[0])[3]) ; } pa += 1;pb += 1; nla -= 1; } 

Si les chaînes sont complétées avec zéro pour toujours être 32 octets et que leurs adresses sont alignées sur 16, vous pouvez faire quelque chose comme ceci: (code ni testé ni profilé)

 movdqa xmm0, [a] movdqa xmm1, [a + 16] pcmpeqb xmm0, [b] pcmpeqb xmm1, [b + 16] pxor xmm2, xmm2 psadbw xmm0, xmm2 psadbw xmm1, xmm2 pextrw ax, xmm0, 0 pextrw dx, xmm1, 0 add ax, dx movsx eax, ax neg eax 

Mais si les cordes sont généralement minuscules, cela fera beaucoup de travail inutile et pourrait ne pas être plus rapide. Cela devrait être plus rapide si les chaînes sont généralement (presque) 32 octets cependant.

edit: j’ai écrit cette réponse avant d’avoir vu votre commentaire mis à jour – si les chaînes sont si minuscules, ce n’est probablement pas très bon. Une version de 16 octets pourrait (peut-être) être utile (exécutez la deuxième itération de manière conditionnelle, la twig pour cela devrait être bien prédite car elle sera rarement prise). Mais avec de telles chaînes courtes, le code normal est difficile à battre.

 movdqa xmm0, [a] pxor xmm1, xmm1 pcmpeqb xmm0, [b] psadbw xmm0, xmm1 pextrw ax, xmm0, 0 movsx eax, ax neg eax