Performances de la dissortingbution de size_t à double

TL; DR : Pourquoi la multiplication / diffusion de données dans size_t lente et pourquoi cela varie-t-il par plate-forme?

J’ai des problèmes de performances que je ne comprends pas bien. Le contexte est une carte d’acquisition de la caméra dans laquelle une image 128×128 uint16_t est lue et post-traitée à une fréquence de plusieurs centaines de Hz.

Dans le post-traitement, je génère un histogramme- frame->histo qui est de uint32_t et qui a thismaxval = 2 ^ 16 éléments, ce qui correspond fondamentalement à toutes les valeurs d’intensité. En utilisant cet histogramme, je calcule la sum et la sum au carré:

 double sum=0, sumsquared=0; size_t thismaxval = 1 << 16; for(size_t i = 0; i histo[i]; sumsquared += (double)(i * i) * frame->histo[i]; } 

En profilant le code avec le profil, j’ai obtenu ce qui suit (échantillons, pourcentage, code):

  58228 32.1263 : sum += (double)i * frame->histo[i]; 116760 64.4204 : sumsquared += (double)(i * i) * frame->histo[i]; 

ou, la première ligne occupe 32% du temps CPU, la seconde ligne 64%.

J’ai fait des parsings comparatives et il semble que le type de données / la conversion pose problème. Quand je change le code en

 uint_fast64_t isum=0, isumsquared=0; for(uint_fast32_t i = 0; i histo[i]; isumsquared += (i * i) * frame->histo[i]; } 

il court environ 10 fois plus vite. Cependant, cette performance varie également selon les plates-formes. Sur le poste de travail, un processeur Core i7 950 @ 3,07 GHz, le code est 10 fois plus rapide. Sur mon Macbook8,1, doté d’un processeur Intel Core i7 Sandy Bridge 2,7 GHz (2620M), le code n’est que 2x plus rapide.

Maintenant je me demande:

  1. Pourquoi le code original est-il si lent et rapide?
  2. Pourquoi cela varie-t-il autant par plate-forme?

Mettre à jour:

J’ai compilé le code ci-dessus avec

 g++ -O3 -Wall cast_test.cc -o cast_test 

Update2:

J’ai exécuté les codes optimisés via un profileur ( Instruments sur Mac, comme Shark ) et découvert deux choses:

1) Le bouclage lui-même prend un temps considérable dans certains cas. thismaxval est du type size_t .

  1. for(size_t i = 0; i < thismaxval; i++) prend 17% de mon temps d’exécution total
  2. for(uint_fast32_t i = 0; i < thismaxval; i++) prend 3,5%
  3. for(int i = 0; i < thismaxval; i++) n’apparaît pas dans le profileur, je suppose qu’il est inférieur à 0,1%

2) Les types de données et les matières à mouler comme suit:

  1. sumsquared += (double)(i * i) * histo[i]; 15% (avec size_t i )
  2. sumsquared += (double)(i * i) * histo[i]; 36% (avec uint_fast32_t i )
  3. isumsquared += (i * i) * histo[i]; 13% (avec uint_fast32_t i , uint_fast64_t isumsquared )
  4. isumsquared += (i * i) * histo[i]; 11% (avec int i , uint_fast64_t isumsquared )

Étonnamment, int est plus rapide que uint_fast32_t ?

Update4:

J’ai effectué quelques tests supplémentaires avec différents types de données et différents compilateurs, sur une seule machine. Les résultats sont les suivants.

Pour testd 0 – 2, le code pertinent est

  for(loop_t i = 0; i < thismaxval; i++) sumsquared += (double)(i * i) * histo[i]; 

avec sumsquared un double, et loop_t size_t , uint_fast32_t et int pour les tests 0, 1 et 2.

Pour les tests 3 à 5, le code est

  for(loop_t i = 0; i < thismaxval; i++) isumsquared += (i * i) * histo[i]; 

avec isumsquared de type uint_fast64_t et loop_t nouveau size_t , uint_fast32_t et int pour les tests 3, 4 et 5.

Les compilateurs que j’ai utilisés sont gcc 4.2.1, gcc 4.4.7, gcc 4.6.3 et gcc 4.7.0. Les timings sont exprimés en pourcentage du temps total du processeur du code, de sorte qu’ils affichent des performances relatives et non absolues (bien que le temps d’exécution ait été relativement constant à 21 secondes). Le temps de calcul est pour les deux lignes, car je ne suis pas tout à fait sûr si le profileur a correctement séparé les deux lignes de code.

 gcc: 4.2.1 4.4.7 4.6.3 4.7.0
 ----------------------------------
 test 0: 21.85 25.15 22.05 21.85
 test 1: 21,9 25,05 22 22
 test 2: 26,35 25,1 21,95 19,2
 essai 3: 7,15 8,35 18,55 19,95
 test 4: 11,1 8,45 7,35 7,1
 test 5: 7.1 7.8 6.9 7.05

ou:

performance de casting

Sur cette base, il semble que le casting est coûteux, quel que soit le type d’entier que j’utilise.

En outre, il semble que les versions 4.6 et 4.7 de gcc ne soient pas en mesure d’optimiser correctement la boucle 3 (size_t et uint_fast64_t).

Pour vos questions originales:

  1. Le code est lent car il implique la conversion de type de données entier en type de données flottant. C’est pourquoi il est facilement accéléré lorsque vous utilisez également un type de données entier pour les variables de sum, car il ne nécessite plus de conversion flottante.
  2. La différence est le résultat de plusieurs facteurs. Par exemple, cela dépend de l’efficacité avec laquelle une plate-forme est capable d’effectuer une conversion int-> float. En outre, cette conversion pourrait également gâcher les optimisations internes au processeur dans le stream de programme et le moteur de prédiction, les caches, etc., ainsi que les fonctions de parallélisation interne des processeurs pouvant avoir une influence considérable sur ces calculs.

Pour les questions supplémentaires:

  • “Étonnamment, int est plus rapide que uint_fast32_t”? Quelle est la taille de sizeof (size_t) et sizeof (int) sur votre plate-forme? Une hypothèse que je peux faire est que les deux sont probablement à 64 bits et donc une conversion en 32 bits peut non seulement vous donner des erreurs de calcul, mais inclut également une pénalité de conversion de taille différente.

En général, essayez d’éviter autant que possible les conversions visibles et cachées si elles ne sont pas vraiment nécessaires. Par exemple, essayez de trouver quel type de données réel est caché derrière “size_t” sur votre environnement (gcc) et utilisez-le pour la variable de boucle. Dans votre exemple, le carré d’uint ne peut pas être un type de données float, il est donc inutile d’utiliser double ici. S’en tenir à des types entiers pour atteindre des performances maximales.

Sur x86, la conversion de uint64_t en virgule flottante est plus lente car il n’y a que des instructions pour convertir int64_t , int32_t et int16_t . int16_t et en mode 32 bits, int64_t peut uniquement être converti à l’aide d’instructions x87, pas de SSE.

Lors de la conversion de uint64_t en virgule flottante, GCC 4.2.1 convertit d’abord la valeur comme s’il s’agissait d’un int64_t , puis ajoute 2 64 si elle était négative pour compenser. (Si vous utilisez x87, sous Windows et * BSD ou si vous avez modifié le contrôle de précision, sachez que la conversion ignore le contrôle de précision mais que l’ajout le respecte.)

Un uint32_t est d’abord étendu à int64_t .

Lors de la conversion d’entiers 64 bits en mode 32 bits sur des processeurs dotés de certaines fonctionnalités 64 bits, un problème de transfert magasin à chargement peut entraîner des blocages. L’entier de 64 bits est écrit en tant que deux valeurs de 32 bits et relu en tant que valeur de 64 bits. Cela peut être très grave si la conversion fait partie d’une longue chaîne de dépendance (pas dans ce cas).