Le moyen le plus rapide de voir combien d'octets sont égaux entre des tableaux de longueur fixe
https://stackoverflow.com/questions/116485
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai deux tableaux de 16 éléments (caractères) que je dois "comparer". et voyez combien d'éléments sont égaux entre les deux.
Cette routine va être utilisée des millions de fois (une course habituelle est d'environ 60 ou 70 millions de fois), j'ai donc besoin qu'elle soit aussi rapide que possible. Je travaille sur C ++ (C ++ Builder 2007, pour mémoire)
Pour l'instant, j'ai un simple:
matches += array1[0] == array2[0];
répété 16 fois (en tant que profileur, il semble être 30% plus rapide que de le faire avec une boucle for)
Existe-t-il un autre moyen de travailler plus rapidement?
Certaines données sur l'environnement et les données elles-mêmes:
- J'utilise C ++ Builder, qui n'a aucune optimisation de vitesse à prendre en compte. Je vais éventuellement essayer avec un autre compilateur, mais pour le moment je suis coincé avec celui-ci.
- Les données seront différentes la plupart du temps. 100% de données égales sont généralement très très rares (peut-être moins de 1%)
La solution
UPDATE: Cette réponse a été modifiée pour que mes commentaires correspondent au code source fourni ci-dessous.
Une optimisation est disponible si vous pouvez utiliser les instructions SSE2 et popcnt.
16 octets se trouvent bien dans un registre SSE. En utilisant c ++ et assembly / intrinsics, chargez les deux tableaux de 16 octets dans des registres xmm, puis cmp. Cela génère un masque binaire représentant la condition vrai / faux de la comparaison. Vous utilisez ensuite une instruction movmsk pour charger une représentation binaire du masque binaire dans un registre x86; cela devient alors un champ de bits où vous pouvez compter tous les 1 pour déterminer le nombre de valeurs vraies que vous aviez. Une instruction contextuelle matérielle peut être un moyen rapide de compter tous les 1 dans un registre.
Cela nécessite une connaissance de l’assemblage / des composants intrinsèques et de la SSE en particulier. Vous devriez pouvoir trouver des ressources Web pour les deux.
Si vous exécutez ce code sur une machine ne prenant pas en charge SSE2 ni popcnt, vous devez alors parcourir les tableaux et compter les différences avec votre approche en boucle déroulée.
Bonne chance
Modifier: Puisque vous avez indiqué que vous ne connaissiez pas l'assembly, voici un exemple de code pour illustrer ma réponse:
#include "stdafx.h"
#include <iostream>
#include "intrin.h"
inline unsigned cmpArray16( char (&arr1)[16], char (&arr2)[16] )
{
__m128i first = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr1 ) );
__m128i second = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr2 ) );
return _mm_movemask_epi8( _mm_cmpeq_epi8( first, second ) );
}
int _tmain( int argc, _TCHAR* argv[] )
{
unsigned count = 0;
char arr1[16] = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0 };
char arr2[16] = { 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0 };
count = __popcnt( cmpArray16( arr1, arr2 ) );
std::cout << "The number of equivalent bytes = " << count << std::endl;
return 0;
}
Quelques notes: Cette fonction utilise les instructions SSE2 et une instruction popcnt introduite dans le processeur Phenom (c’est la machine que j’utilise). Je crois que les processeurs Intel les plus récents avec SSE4 ont également popcnt. Cette fonction ne vérifie pas la prise en charge des instructions avec CPUID; la fonction n'est pas définie si elle est utilisée sur un processeur dépourvu de SSE2 ou de popcnt (vous obtiendrez probablement une instruction de code d'opération invalide). Ce code de détection est un thread séparé.
Je n'ai pas chronométré ce code; La raison pour laquelle je pense que c'est plus rapide, c'est parce qu'il compare 16 octets à la fois, sans branche. Vous devez le modifier pour l'adapter à votre environnement et le vérifier vous-même pour voir si cela fonctionne pour vous. J'ai écrit et testé ceci sur le VS1 SP1.
SSE préfère les données alignées sur une limite naturelle de 16 octets; si vous pouvez en garantir l’amélioration de la vitesse, modifiez les instructions _mm_loadu_si128 en _mm_load_si128, qui nécessite un alignement.
Autres conseils
La clé est de faire les comparaisons en utilisant le plus grand registre pris en charge par votre CPU, puis de revenir en octets si nécessaire.
Le code ci-dessous illustre l'utilisation d'entiers de 4 octets, mais si vous utilisez une architecture SIMD (toute puce Intel ou AMD moderne), vous pouvez comparer les deux tableaux en une seule instruction avant de revenir à une boucle basée sur des entiers. De nos jours, la plupart des compilateurs prennent en charge intrinsèquement les types 128 bits, ils n'exigeront donc pas d'ASM.
(Notez que pour les comparaisons SIMD, vos tableaux doivent être alignés sur 16 octets et que certains processeurs (par exemple, MIPS) exigent que les tableaux soient alignés sur 4 octets pour les comparaisons basées sur int.
ex.
int* array1 = (int*)byteArray[0];
int* array2 = (int*)byteArray[1];
int same = 0;
for (int i = 0; i < 4; i++)
{
// test as an int
if (array1[i] == array2[i])
{
same += 4;
}
else
{
// test individual bytes
char* bytes1 = (char*)(array1+i);
char* bytes2 = (char*)(array2+i);
for (int j = 0; j < 4; j++)
{
same += (bytes1[j] == bytes2[j];
}
}
}
Je ne me souviens pas de ce que le compilateur MSVC prend en charge pour SIMD, mais vous pouvez faire quelque chose comme:
// depending on compiler you may have to insert the words via an intrinsic
__m128 qw1 = *(__m128*)byteArray[0];
__m128 qw2 = *(__m128*)byteArray[1];
// again, depending on the compiler the comparision may have to be done via an intrinsic
if (qw1 == qw2)
{
same = 16;
}
else
{
// do int/byte testing
}
Si vous avez la possibilité de contrôler l'emplacement des baies, en plaçant les unes après les autres en mémoire, par exemple, elles pourraient être chargées dans le cache de la CPU lors du premier accès.
Cela dépend de la CPU et de sa structure de cache et varie d’une machine à l’autre.
Vous pouvez en savoir plus sur la hiérarchie de mémoire et le cache dans Henessy & amp; Architecture informatique de Patterson: une approche quantitative
Si vous avez besoin d'une empreinte minimale absolue, j'utiliserais le code d'assemblage. Je n’ai pas fait cela depuis longtemps, mais je parie que MMX (ou plus probablement SSE2 / 3) a des instructions qui peuvent vous permettre de faire exactement cela en très peu d’instructions.
Si les correspondances sont le cas habituel, essayez de charger les valeurs au format 32 bits au lieu de 16 afin de pouvoir comparer 2 en une fois (et le compter comme 2 correspondances).
Si les deux valeurs 32 bits sont différentes , vous devrez les tester séparément (ET sur les valeurs 16 bits supérieures et inférieures).
Le code sera plus complexe, mais devrait être plus rapide.
Si vous ciblez un système 64 bits, vous pouvez faire de même avec les inits 64 bits. Si vous voulez vraiment repousser vos limites, envisagez de passer en mode assembleur et d’utiliser les diverses instructions vectorielles qui vous permettraient de travailler. avec 128 bits à la fois.
Les options du compilateur magique varieront considérablement le temps. En particulier, le fait de générer une vectorisation SSE vous donnera probablement un gain de temps considérable.
Cela doit-il être indépendant de la plate-forme ou ce code sera-t-il toujours exécuté sur le même type de CPU? Si vous vous limitez aux processeurs x86 modernes, vous pourrez peut-être utiliser les instructions MMX . , ce qui devrait vous permettre d’opérer sur un tableau de 8 octets en un seul coup d’horloge. Si je comprends bien, gcc vous permet d’intégrer l’assemblage dans votre code C, et le compilateur d’Intel (icc) prend en charge les composants intrinsèques, des wrappers qui vous permettent d’appeler directement des instructions d’assemblage spécifiques. D'autres jeux d'instructions SIMD, tels que SSE, peuvent également être utiles à cet effet.
Existe-t-il un lien entre les valeurs des tableaux? Certains octets sont-ils plus susceptibles d'être les mêmes que d'autres? Peut-il y avoir un ordre intrinsèque dans les valeurs? Vous pourrez ensuite optimiser le cas le plus probable.
Si vous expliquez ce que les données représentent réellement, il pourrait exister une manière totalement différente de représenter les données en mémoire qui rendrait inutile ce type de comparaison de la force brute. Vous souhaitez préciser ce que les données représentent réellement?
Est-ce plus rapide qu'une déclaration?
matches += (array1[0] == array2[0]) + (array1[1] == array2[1]) + ...;
Si écrire 16 fois est plus rapide qu'une simple boucle, votre compilateur est nul ou l'optimisation n'est pas activée.
Réponse courte: il n'y a pas de moyen plus rapide, sauf si vous effectuez des opérations vectorielles sur du matériel parallèle.
Essayez d’utiliser des pointeurs au lieu de tableaux:
p1 = &array1[0];
p2 = &array2[0];
match += (*p1++ == *p2++);
// copy 15 times.
Bien sûr, vous devez le comparer à d’autres approches pour déterminer laquelle est la plus rapide.
Et êtes-vous sûr que cette routine est un goulot d'étranglement dans votre traitement? Accélérez-vous réellement les performances de votre application en l’optimisant? Encore une fois, seule la mesure nous le dira.
Existe-t-il un moyen de modifier le mode de stockage des tableaux? La comparaison d'un octet à la fois est extrêmement lente, car vous utilisez probablement un compilateur 32 bits. Si vous stockiez vos 16 octets dans 4 nombres entiers (32 bits) ou 2 longs (64 bits), il vous suffira d’effectuer respectivement 4 ou 2 comparaisons.
La question à se poser est de savoir combien coûte le stockage des données sous forme de tableaux de 4 ou de 2 entiers. À quelle fréquence devez-vous accéder aux données, etc.
Il y a toujours la bonne vieille instruction x86 REPNE CMPS.
Une optimisation supplémentaire possible: si vous vous attendez à ce que les tableaux soient identiques la plupart du temps, il sera peut-être un peu plus rapide de faire un memcmp () comme première étape, en définissant "16" comme réponse si le test renvoie true . Bien sûr, si vous ne vous attendez pas à ce que les tableaux soient identiques très souvent, cela ne ferait que ralentir les choses.
