Laquelle de ces deux boucles est plus rapide?

Je dois parcourir un ensemble d’octets, en recherchant une valeur de 4 octets (tous les 4 octets sont identiques). La longueur des données est variable et ces octets peuvent se trouver n’importe où dans les données. Je cherche la première instance. J’essaie de trouver la mise en œuvre la plus rapide possible car cette logique s’exécute dans une partie critique de mon code.

Cela ne fonctionnera que sur x86 et x64, sous Windows.

typedef unsigned char Byte; typedef Byte* BytePtr; typedef unsigned int UInt32; typedef UInt32* UInt32Ptr; const Byte MARKER_BYTE = 0xAA; const UInt32 MARKER = 0xAAAAAAAA; UInt32 nDataLength = ...; BytePtr pData = ...; BytePtr pEnd = pData + nDataLength - sizeof ( UInt32 ); // Option 1 ------------------------------------------- while ( pData < pEnd ) { if ( *( (UInt32Ptr) pData ) == MARKER ) { ... // Do something here break; } pData++; } // Option 2 ------------------------------------------- while ( pData < pEnd ) { if ( ( *pData == MARKER_BYTE ) && ( *( (UInt32Ptr) pData ) == MARKER ) ) { ... // Do something here break; } pData++; }

Je pense que l’ Option 2 est plus rapide mais je ne sais pas si mon raisonnement est correct.

Option 1 lit d’abord 4 octets de la mémoire, la vérifie par rapport à la constante de 4 octets et, si elle n’est pas trouvée, passe à l’octet suivant et recommence. Le prochain 4 octets prêt à partir de la mémoire va chevaucher 3 octets déjà lus, de sorte que les mêmes octets doivent être récupérés à nouveau. La plupart des octets avant mon marqueur de 4 octets seront lus deux fois.

Option 2 ne lit que 1 octet à la fois et si cet octet unique est une correspondance, il lit la valeur complète de 4 octets de cette adresse. De cette façon, tous les octets sont en lecture seule et seuls les 4 octets correspondants sont lus deux fois.

Est-ce que mon raisonnement est correct ou est-ce que j’oublie quelque chose?

Et avant que quelqu’un l’apporte, oui, je dois vraiment effectuer ce type d’optimisation. 🙂

Edit : notez que ce code ne fonctionnera que sur les ordinateurs Intel / AMD. Je ne m’inquiète pas du fait que d’autres architectures ne parviennent pas à l’exécuter, tant que les ordinateurs x86 / x64 (ordinateurs de bureau / serveurs) normaux l’exécutent sans problèmes ou pénalités de performance.

Edit 2 : le compilateur est VC ++ 2008, si cela vous aide.

Vous pourriez aussi essayer l’approche de Boyer-Moore.

 pData = start + 3; int i; while(pData < pEnd) { for(i = 0; i < 4; ++i) { if (*(pData-i) != MARKER_BYTE) { pData += 4-i; break; } } if (i == 4) { /* do something here with (pData-3) */ break; } }

Si vous êtes chanceux, cela ne teste que tous les quatre octets jusqu'à ce que vous trouviez une correspondance.

Que ce soit plus rapide ou plus lent que le fait de tester chaque octet, on peut se demander si les patrons sont courts.

L’option 1 fera beaucoup d’access à la mémoire non alignée. Je ne sais pas si cela est même possible pour le matériel. Au moins sur certains matériels, Windows interceptera l’exception résultante et, très lentement, émulera l’access à la mémoire. Un désastre total pour la performance.

De toute façon, vous avez déjà le code. Pourquoi ne le mesurez-vous pas et soyez sûr à 100%?

Option 2. Il n’ya aucune raison de récupérer 4 octets si 255 sur 256 fois le premier ne sera pas celui que vous voulez.

Et pour l’amour de Pete, déroulez la boucle.

EDIT: Dérouler. La longueur est nDataLength . Vous pourriez dire ceci:

 pEnd1 = pData + (nDataLength & -8); while (pData < pEnd1){ if (pData[0] == theByteIWant){ ... } if (pData[1] == theByteIWant){ ... } ... if (pData[7] == theByteIWant){ ... } pData += 8; } while(pData < pEnd){ if (pData[0] == theByteIWant){ ... } pData++; }

Voir ce que ça fait? Vous ne passez pas la moitié de votre temps à poser une question (pData < pEnd) pour laquelle la réponse est presque toujours la même.

Cette approche n’est pas complète, mais l’idée essentielle est de rechercher huit (8) octets à la fois pour le motif 0xAA. Si trouvé, vous pouvez alors effectuer une recherche secondaire pour le motif MARKER.

Phase 1: Effectuez un test octet par octet jusqu’à ce que votre masortingce soit alignée sur 8 octets.

Phase 2: #define HAS_NUL_BYTE (x) ((x) – 0x0101010101010101ull) & ~ x & 0x8080808080808080ull)

 uint64_t value; for (...) { value = *(uint64_t *) array[i] ^ 0xAAAAAAAAAAAAAAAAull; if (HAS_NUL_BYTE (value) != 0) { perform secondary search for the MARKER pattern } i += 8; }

Cette approche devrait (espérons-le) avoir les avantages suivants.

1 comparaison par 8 octets au lieu de 8 lorsque 0xAA n’est pas dans la fenêtre.
Moins d’access à la mémoire mal alignés.

Les inconvénients comprennent …

C’est plus compliqué
Si le tableau contient beaucoup d’octets 0xAA (mais pas le marqueur), les faux positifs dans la recherche primaire auront un impact sur les performances.

Une autre chose – puisque vous mentionnez que cela ne fonctionnera que sur un x86-64 sous Windows, avez-vous envisagé d’écrire ceci en assemblée? Si tel est le cas, l’instruction PCMPEQB peut s’avérer utile.

J’espère que cela t’aides.