Fonte de la performance de size_t double

Question

TL;DR: Pourquoi multiplier/moulage de données en size_t lent et pourquoi cela varie selon la plate-forme?

Je vais avoir quelques problèmes de performance que je ne comprends pas tout. Le contexte est un appareil d'acquisition d'images où un 128x128 uint16_t image est de lire et de post-traitement à un taux de plusieurs de 100 Hz.

Dans le post-traitement-je générer un histogramme frame->histo qui est de uint32_t et a thismaxval = 2^16 éléments, fondamentalement, je comptabiliser toutes les valeurs d'intensité. À l'aide de cet histogramme-je calculer la somme et le carré de la somme:

double sum=0, sumsquared=0;
size_t thismaxval = 1 << 16;

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

Profilage du code avec le profil j'ai eu la suivante (échantillons, de pourcentage, de 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 prend en hausse de 32% de temps CPU, le deuxième ligne de 64%.

J'ai fait un peu de benchmarking et il semble être le type de données/moulage de cette problématique. Quand j'ai modifier le code pour

uint_fast64_t isum=0, isumsquared=0;

for(uint_fast32_t i = 0; i < thismaxval; i++) {
    isum += i * frame->histo[i];
    isumsquared += (i * i) * frame->histo[i];
}

il s'exécute ~10x plus rapide. Cependant, ce gain de performance varie également par la plate-forme. Sur la station de travail, un Core i7 950 @ 3.07 GHz, le code est 10 fois plus rapide. Sur mon Macbook8,1, qui dispose d'un processeur Intel Core i7 Sandy Bridge 2,7 GHz (2620M) le code n'est 2x plus rapide.

Maintenant je me demande:

1. Pourquoi le code d'origine de la lenteur et facilement accéléré?
2. Pourquoi cela varie selon la plate-forme autant?

Mise à jour:

J'ai compilé le code ci-dessus avec

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

Update2:

J'ai couru à l'optimisation des codes par le biais d'un générateur de profils (Instruments sur Mac, comme les Requins) et a constaté deux choses:

1) La boucle elle-même prend une quantité considérable de temps dans certains cas. thismaxval est de type size_t.

1. for(size_t i = 0; i < thismaxval; i++) 17% du total de mes runtime
2. for(uint_fast32_t i = 0; i < thismaxval; i++) prend de 3,5%
3. for(int i = 0; i < thismaxval; i++) ne s'affiche pas dans le profiler, je suppose que c'est moins de 0,1%

2) Les types de données et de la coulée d'importance comme suit:

1. sumsquared += (double)(i * i) * histo[i]; 15% (avec size_t i)
2. sumsquared += (double)(i * i) * histo[i]; 36% ( 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 plus rapide que de l' uint_fast32_t?

Update4:

J'ai couru quelques plus de tests avec différents types de données et les différents compilateurs, sur une seule machine. Les résultats sont comme suit.

Pour testd 0 -- 2 du code correspondant est

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

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

Pour les tests 3--5 du code de l'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ées sont gcc 4.2.1, gcc 4.4.7, gcc et gcc 4.6.3 4.7.0. Les horaires sont en pourcentages du total des temps cpu du code, de façon à montrer la performance relative, pas absolue (bien que l'exécution a été assez constant à 21). Le temps de calcul est pour les deux lignes, parce que je ne suis pas sûr si le profiler 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 de 21,95 19.2
test 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:

Sur cette base, il semble que le casting est cher, indépendamment de ce type entier que j'utilise.

Aussi, il semble gcc 4.6 et 4.7 sont pas en mesure d'optimiser la boucle 3 (size_t et uint_fast64_t) correctement.

Answer 1

Pour vos questions:

1. Le code est lente, car elle implique la conversion de l'entier flotteur de types de données. C'est pourquoi il est facilement accéléré lorsque vous utilisez également un type de données entier pour la somme de variables car il ne nécessite pas un hydravion de la conversion.
2. La différence est le résultat de plusieurs facteurs. Par exemple, il dépend de la façon dont l'efficacité énergétique d'une plate-forme est capable pour effectuer une int->float conversion. De plus, cette conversion peut aussi gâcher le processeur interne des optimisations dans le programme flux et la prédiction du moteur, caches, ... et également à l'intérieur la parallélisation-caractéristiques des processeurs peuvent avoir une influence énorme dans de tels calculs.

Pour les autres questions:

• "Étonnamment int est plus rapide que uint_fast32_t"? Quelle est la sizeof(size_t) et sizeof(int) sur votre plate-forme? On suppose que je peux faire est que les deux sont sans doute 64 bits et donc une fonte à 32 bits non seulement peut vous donner des erreurs de calcul, mais comprend également un autre-taille-casting peine.

En général, essayez d'éviter les visibles et cachés jette aussi bon que possible si ce ne sont pas vraiment nécessaires. Par exemple, essayer de découvrir ce qu'est le vrai type de données est caché derrière "size_t" sur votre environnement (ccg) et de l'utilisation que l'on fait la boucle de la variable. Dans votre exemple, le carré de uint ne saurait être un flotteur de type de données de sorte qu'il n'a pas de sens d'utiliser le double ici. De controle pour les types d'entiers pour obtenir des performances maximales.

Answer 2

Sur x86, la conversion de uint64_t à la virgule flottante est plus lent, car il y a seulement des instructions pour convertir int64_t, int32_t et int16_t. int16_t et en mode 32 bits int64_t ne peuvent être convertis en utilisant x87 instructions, pas de l'ESS.

Lors de la conversion d' uint64_t à virgule flottante, GCC 4.2.1 première convertit la valeur comme s'il s'agissait d'un int64_t , puis ajoute 2⁶⁴ si elle est négative pour compenser. (Lors de l'utilisation de la x87, sur Windows et *BSD ou si vous avez changé le contrôle de la précision, méfiez-vous que la conversion ignore le contrôle de la précision, mais le plus qu'elle le respecte.)

Un uint32_t est d'abord étendue à d' int64_t.

Lors de la conversion des entiers 64 bits en mode 32 bits sur des processeurs avec certaines capacités de 64-bit, un magasin à la charge de redirection question peut causer des stands. L'entier de 64 bits est écrit que les deux valeurs de 32 bits et de la lecture à l'arrière comme une valeur 64 bits. Cela peut être très mauvais, si la conversion est partie d'une longue chaîne de dépendances (pas dans ce cas).