Nofrag | Forums | Blogs (jeux)

Optimisations de code C++

Ca faisait un moment que je n’avait pas fait d’optimisation de code. Je profite d’avoir un programme épuré de test des fluides pour améliorer les performances. Passer du temps à optimiser le calcul est très intéressant puisque la plus grosse partie du gameplay dépend de la qualité de la simulation et de la quantité de particules. Entre mon approche naïve (celle utilisée dans les vidéos postées chez moi et Holi) et la version que j’ai actuellement, j’ai divisé le temps de calcul par 20. Il y a surement moyen de gratter encore.

Il y a plusieurs axes pour améliorer les performances.

- En diminuant la complexité du programme (moins d’itérations, moins d’opérations couteuses,…)

- En améliorant la gestion du cache CPU

- Utiliser des intrinsèques (SSE/SSE2/…)

- Paralléliser

Pour bien améliorer son programme, il faut déjà isoler les parties qu’on veut bencher et forcément, avoir un système de profiling. Je vais utiliser celui de mon moteur (et de .the rush). Voici donc l’état des lieux:

Itération 0:

_______________________________________________________________________________________
| Temps total  | Temps Moyen  |   Temps Min  |  Temps Max   | Appels | Nom de l'appel
_______________________________________________________________________________________
|   13065.9543 |       9.9893 |       9.6258 |      21.9178 |  1308  | FluidUpdate
|   12934.9759 |       9.8891 |       9.5163 |      21.7861 |  1308  |   SIMU
|   10105.4063 |       7.7258 |       7.4925 |      18.0696 |  1308  |     CalculateForces
|    1304.3359 |       0.9972 |       0.8859 |       1.7658 |  1308  |     CalculatePressureAndDensities
|    1457.0675 |       1.1140 |       1.0901 |       2.4617 |  1308  |     CheckParticleDistance
|      36.3376 |       0.0278 |       0.0245 |       0.2487 |  1308  |     UpdateParticles
|      83.4699 |       0.0638 |       0.0618 |       0.1900 |  1308  |   VertexArray
|      17.6296 |       0.0135 |       0.0081 |       0.0832 |  1308  | Render
_______________________________________________________________________________________

Le calcul des particules est découpé en 4: Calcul des forces (gravité, viscosité, pression), le calcul de la densité et de la pression interne, calcul de distance pour que les particules ne se chevauchent pas, et un verlet pour calculer sa position, vélocité,…
Les temps affichés sont en millisecondes et le total pour une itération sur 400 particules fait 10ms.

Itération 1:

Découpage de l’univers de calcul en plusieurs sous parties. On calcule chaque partie +/- indépendamment des autres. Les particules ayant peu d’influences sont naturellement exclues du calcul d’une particule. Dans le code, j’ai un tableau ou chaque case contient la liste des particules qui lui appartient. Ca ressemble à un quad-tree mais sans hierarchie.

_______________________________________________________________________________________
| Temps total  | Temps Moyen  |   Temps Min  |  Temps Max   | Appels | Nom de l'appel
_______________________________________________________________________________________
|   10126.9406 |       4.0834 |       2.8163 |      27.7407 |  2480  | FluidUpdate
|     369.9525 |       0.1492 |       0.0873 |       0.5288 |  2480  |   AssignParticles
|    9505.7993 |       3.8330 |       2.6477 |      27.4923 |  2480  |   SIMU
|    4072.1919 |       1.6420 |       0.4903 |      23.5015 |  2480  |     CalculateForces
|    2375.7542 |       0.9580 |       0.9056 |       1.9108 |  2480  |     CalculatePressureAndDensities
|    2954.1905 |       1.1912 |       1.1532 |       3.0387 |  2480  |     CheckParticleDistance
|      69.2783 |       0.0279 |       0.0239 |       1.0336 |  2480  |     UpdateParticles
|     156.2827 |       0.0630 |       0.0612 |       0.2579 |  2480  |   VertexArray
|      30.4318 |       0.0123 |       0.0079 |       0.1346 |  2480  | Render
_______________________________________________________________________________________

On voit apparaitre un profilage sur AssignParticles. Cette fonction passe sur toutes les particules pour les assigner dans la case spatiale correspondante a sa position. On a un facteur degain de vitesse de 2,5.

Itération 2:

Je gratte comme je peux : suppression de test ifs non nécessaires, utilisation de variables temporaires sur la pile plutôt que de membres de structure/class, utilisation de pointeurs sur la pile plutôt que d’utiliser un index:


particule[i].postion += f;

particule[i].velocity =tvector2(0,0);

particule[i].life += timeEllapsed;

Devient:


Particule & myParticule = particule[i];

myParticule.postion += f;

myParticule.velocity =tvector2(0,0);

myParticule.life += timeEllapsed;
_______________________________________________________________________________________
| Temps total  | Temps Moyen  |   Temps Min  |  Temps Max   | Appels | Nom de l'appel
_______________________________________________________________________________________
|    3111.9287 |       1.8837 |       1.0959 |      33.9193 |  1652  | FluidUpdate
|     256.2206 |       0.1551 |       0.0956 |       0.4963 |  1652  |   AssignParticles
|    2678.3283 |       1.6213 |       0.9078 |      33.6677 |  1652  |   SIMU
|     919.0588 |       0.5563 |       0.2765 |      19.8407 |  1652  |     CalculateForces
|     885.6993 |       0.5361 |       0.2943 |       7.8931 |  1652  |     CalculatePressureAndDensities <- sortie de if, iterateur
|     804.6188 |       0.4871 |       0.3022 |       5.8618 |  1652  |     CheckParticleDistance
|      47.2587 |       0.0286 |       0.0245 |       0.4719 |  1652  |     UpdateParticles
|     106.0983 |       0.0642 |       0.0612 |       1.1090 |  1652  |   VertexArray
|      20.6552 |       0.0125 |       0.0081 |       0.2564 |  1652  | Render
_______________________________________________________________________________________

Un peu plus d’un facteur 2 en vitesse.

Itération 3:

Dans les options du compilo: désactivation des exceptions, mode FPU en fast, optimisations globales,…


_______________________________________________________________________________________
| Temps total  | Temps Moyen  |   Temps Min  |  Temps Max   | Appels | Nom de l'appel
_______________________________________________________________________________________
|    3013.9239 |       1.7057 |       1.0533 |      20.5626 |  1767  | FluidUpdate < desactivation des exceptions + options d'optim du compilo
|     241.6325 |       0.1367 |       0.0722 |       1.0293 |  1767  |   AssignParticles
|    2649.5582 |       1.4995 |       0.8973 |      20.3121 |  1767  |   SIMU
|     929.6930 |       0.5261 |       0.3015 |      11.3593 |  1767  |     CalculateForces
|     903.5049 |       0.5113 |       0.2970 |       4.5576 |  1767  |     CalculatePressureAndDensities
|     769.1413 |       0.4353 |       0.2752 |       4.5486 |  1767  |     CheckParticleDistance
|      28.4287 |       0.0161 |       0.0128 |       0.1424 |  1767  |     UpdateParticles
|      52.3070 |       0.0296 |       0.0283 |       0.2301 |  1767  |   VertexArray
|      20.5821 |       0.0116 |       0.0070 |       0.0474 |  1767  | Render
_______________________________________________________________________________________

10% de gagné. Toujours bon a prendre vu le temps que ca prend a modifier :)

Itération 4:

La plus impressionnante surement. Je remplace tous les templates std::vector par une approche C-Like. J’ai pour chaque case spatiale, un tableau de taille fixe, dimensionné tel qu’il ne peut y avoir physiquement plus de particules dedans. J’ai un pointeur d’ajout. Dans mes boucles d’itération de particule par case, ne n’utilise plus d’iterator mais un pointeur simple. Je le compare avec le pointeur d’ajout pour savoir quand je dois arrêter d’itérer.

_______________________________________________________________________________________
| Temps total  | Temps Moyen  |   Temps Min  |  Temps Max   | Appels | Nom de l'appel
_______________________________________________________________________________________
|     981.9738 |       0.5679 |       0.3419 |       5.3668 |  1729  | FluidUpdate
|     329.2299 |       0.1904 |       0.0989 |       0.7310 |  1729  |   AssignParticles
|     517.5557 |       0.2993 |       0.1636 |       5.1940 |  1729  |   SIMU
|     194.3753 |       0.1124 |       0.0494 |       2.1208 |  1729  |     CalculateForces
|     158.9119 |       0.0919 |       0.0485 |       1.2347 |  1729  |     CalculatePressureAndDensities
|     118.4793 |       0.0685 |       0.0429 |       1.8281 |  1729  |     CheckParticleDistance
|      28.0112 |       0.0162 |       0.0130 |       0.2137 |  1729  |     UpdateParticles
|      55.1190 |       0.0319 |       0.0284 |       0.3317 |  1729  |   VertexArray
|      22.5937 |       0.0131 |       0.0073 |       0.7404 |  1729  | Render
_______________________________________________________________________________________

J’ai un facteur >à 3. AssignParticles varie peu et est linéaire avec le nombre de particules. L’idéal serait de refaire cette fonction en itératif. C’est à dire de réassigner les particules seulement si elles changent de case. Cette fonction est difficilement parallélisable. Les mutex/synchro d’accès aux cases casseraient le parallélisme.

Conclusion:

Il y a encore de la place pour pas mal d’optimisations. Le fastSqrt de Carmack n’a pas donné de bons résultats. Recoder certains petit bouts de code en SSE plutôt que de laisser faire le compilo est possible. Les templates (std::vector et itérator) sont à utiliser avec parcimonie. Pour du code clairement identifé comme consommateur de CPU, il vaut mieux éviter. Pour tout ce qui est macroscopique dans un moteur de jeu, ca reste rentable. Il vaut mieux dans ce cas, perdre quelques pour-cents de CPU pour être plus agile dans le développement.

C’est effrayant de voir que la complexité entre le calcul des forces/pression/densité et AssignParticles est très très différente. Dans le 1er, j’ai des sqrt, beaucoup de multiplications, des divisions,… dans l’autre, j’ai 3 Ifs et une copie de pointeurs. Au final, la différence de temps CPU n’est pas si grande.

5 commentaires pour “Optimisations de code C++”

  1. BoBiNoU dit :

    tres interessant !

  2. skaven dit :

    Au passage, j’ai divisé l’empreinte CPU par 2 d’AssignParticles en remplacant ceilf et floorf par :

    #define auxFloor(x) ((float)(long)(x))
    #define auxCeil(x) ((float)(long)((x)+1))

    90 microsecondes de gagnées.

  3. Octobinz dit :

    Pour les gens intéressés, un site ou j’avais trouvé des infos intéressantes sur l’optim, notement sur le load hit store (typiquement le cas de ton itération 2)

    http://assemblyrequired.crashworks.org/

    Sur le site il doit y avoir le lien vers la EASTL, la STL version Electronic Arts, avec, toujours pareil, des petites astuces bien sympa.

  4. Aristo dit :

    auxCeil ne remplace pas parfaitement ceilf, dans le cas ou tu rentre un entier.

  5. Gama dit :

    Intéressant, merci.

    J’ai pas eu une formation très orientée dev et du coup je suis complètement à la ramasse sur ce genre de trucs, c’est dur à rattraper.

    Y’a quoi comme moyen simple de progresser à part avaler tous les bouquins de référence sur le C++ et hanter Gotw ?
    Genre sur l’optimisation, pour chopper les bons réflexes ?

    Le plus simple c’est de coder encore et toujours mais j’ai un peu peur de passer à côté de trop de trucs ou de prendre des sales habitudes…

Laisser un commentaire

Si vous avez un compte sur WeFrag, connectez-vous pour publier un commentaire.

XHTML: Vous pouvez utiliser ces tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <img src="" alt="">