Optimisation vitesse pure

Citation:

---

Envoyé par Miles

Je n'ai pas dit que la FAQ expliquait tout, mais en ce qui concerne le choix optimal des conteneurs, oui.

---

Effectivement.
Je vais rajouter un lien direct vers la partie de la faq avec le joli diagramme.

Citation:

---

C'est vrai que tout le monde n'a pas accès à ce livre, d'ailleurs, ça pourrait être l'occasion d'améliorer la FAQ avec ce que tu as écrit :)

---

A la base ce sujet etait fait pour evoluer et peut etre mener vers une faq isolé ne parlant que d'optimisation.

Par contre je peux quand même completer la faq avec les maps / multimaps. Faut contacter qui ? ^^

Citation:

---

Envoyé par Kujara

Donc 2 operations au lieu d'une.

---

Je ne conteste absolument pas ce point, mais je ne suis pas sûr que ça soit significatif au sein de l'algorithme d'ajout.

En tous cas personnellement tant qu'un outil de profiling ne m'indique pas que je peux obtenir un gain significatif sur la rapidité d'exécution de la procédure d'ajout en modifiant ça, je ne vais pas le faire...
Et jusqu'ici je ne me suis jamais trouvé dans ce cas.

MAT.

Citation:

---

Envoyé par screetch

en gros, const-reffer le retour d'une methode n'apporte rien en terme de vitesse et alourdit l'ecriture.

---

Ok, tu m'a mis le doute, donc je suis parti tester.

Conclusions : dans le cas d'une méthode qui renvoie une instance, donc style return (A()); , effectivement ça ne sert a rien.

Par contre, si ta fonction renvoie une reference, la c'est parfaitement justifié( cela donne lieu a un constructeur par copie si tu le recupere avec un objet normal plutot qu'une const ref).

Donc, si tu peux utiliser une const ref, et si tu n'est pas sur que la fonction renverra toujours un nouvel objet plutot qu'une reference, un const object & est preferable, non ?

Bref, personellement j'utilise les const ref dès que possible, comme ça j'ai pas a me poser la question ^^.

Citation:

---

Envoyé par screetch

concernant les iterateurs, gaulois, c'est du a la presence dans la lib visual de _HAS_ITERATOR_DEBUGGING. il faut definir cette macro a 0 si tu veux desactiver les checks d'iterateur tres lents.

les algos de la STL sont plus rapide car ils checkent begin(), end() et passent la main a la version qui ne checke rien. lorsque tu ecris la boucle a la main, tu vas faire verifier (sans le savoir) deux iterateurs par boucle, l'iterateur courant et end().

n'oubliez pas de definir _HAS_ITERATOR_DEBUGGING a 0 en release... et de tester en debug ^^

---

Ce n'est pas celui la, c'est un truc comme _SCL_SCURE. Je verifirai.

J'ai verifié avec Gcc 4.2, et le perf sont semblable...
Donc j'ai rien dit :aie:

Mais bon au final, je maintient l'utilisation des algo.

je ne veux pas (encore) faire mon relou sur la reference, mais la reference rend ce code invalide :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

#include <cstdio> #include <vector>   class A { private: std::vector<int> m_values; public: A() { printf ("dans A\n"); m_values.push_back(1); } ~A() { printf ("dans ~A\n"); } A(const A&) { printf ("dans copie\n"); } void plouf() const { printf("dans plouf\n"); } const std::vector<int>& values() const { return m_values; } };   A getA() { return A(); }   int main() { const std::vector<int>& values = getA().values(); printf("%d\n", values[0]); return 0; }

---

en effet l'objet A est temporaire et est detruit des qu'il a donné la reference, emportant avec lui le vector qu'il contenait. j'aime bien les references mais il faut utiliser avec parcimonie...

Citation:

---

Envoyé par screetch

en effet l'objet A est temporaire et est detruit des qu'il a donné la reference, emportant avec lui le vector qu'il contenait. j'aime bien les references mais il faut utiliser avec parcimonie...

---

Le probleme avec ton exemple c'est que ton objet A temporaire n'est justement pas referencé.Donc lui meure.

Code:

---

1 2	const A & l_a = getA(); const std::vector<int>& values = l_a.values();

---

La ça marche très bien, la reference sur A le garde vivant jusqu'a la fin du scope.

Salut,

Je ne voudrais pas jouer les rabats joie, mais...

Même si, dans certains cas, on *peut* rencontrer des processus suffisemment critiques pour devoir impérativement gagner toutes les périodes processeurs possibles, il faut quand même raison garder:

A l'heure actuelles, les processeurs ont des périodes de l'ordre de 0.0000000005 secondes, périodes que que vous proposerais de comparer avec quelques autres:

1. un son n'est audible par l'homme que s'il a une période inférieure à 0.00005 seconde
2. un arc réflexe (le réflexe obtenu quand le docteur tape sur la rotule avec son marteau) se produit en 0.017 secondes
3. une suite d'images dont chaque image serait affichée avec une période supérieure à 0.055 secondes (soit 18 images par seconde) ouverture et obturation comprise, suffit à donner une impression de mouvement à cette suite d'image, du simple fait de la persistance rétinienne
4. Le temps de réaction, à une situation donnée par une action donnée (par exemple: pincer les doigts quand un carton se met à tomber ou cliquer sur le bouton de la souris quand la couleur passe du rouge au vert) demande au minimum 0.15 à 0.17 secondes

Avant que l'humain soit en mesure de percevoir une quelconque différence, il faut donc en venir à compter les périodes perdues en millions... au minimum.

De plus:

• Il est vrai que certaines instructions processeurs sont plus rapides que d'autres, ayant un résultat final équivalent.
• Il est vrai que l'on peut remarquer une différence de l'ordre de quelques périodes en utilisant un type d'accès au données (cache Vs registre, direct Vs indexé ou indirect) plutôt qu'un autre.

Par contre:

• il faut garder en tête le fait que rien n'incite normalement l'humain à utiliser un langage impératif., ni à compter en binaire/octal/hexadécimal... Sinon, on n'aurait sans doute jamais commencé à créer des langages de troisième génération, orienté objet, voire, simplement l'assembleur ;)
• Les jeux d'instructions des processeurs actuels deviennent de plus en plus complexes
• Les compilateurs récents/actuels sont très largement avantagés par rapport à l'humain en ce qui concerne l'optimisation du code machine
• L'oignon fait la farce... Pardon: l'union fait la force (ou, si vous préférez, il y a plus dans deux têtes que dans une): un algorithme utilisé depuis longtemps et sur lequel de nombreuses personnes se seront penchées sera plus que vraisemblablement bien meilleur qu'un algorithme sensé faire la même chose auquel vous aurez réfléchi seul dans votre coin, soit au niveau des performances pures, soit au niveau de la sécurisation, si pas, finalement, les deux en même temps :P

Le tout sans oublier les principes de base qui devrait rester en tête de tout programmeur:

• KISS
• If you don't need this, don't do this
• Pourquoi faire soi même quelque chose que quelqu'un a déjà fait (en mieux) ailleurs :question:

Dés lors, si j'admets le fait que l'on puisse se trouver dans des situations qui font qu'il faille traquer la moindre périodes gaspillées, il faut quand même se poser les questions suivantes:

• Est-ce réellement utile :question:
• Pourquoi ne pas faire confiances aux équipes travaillant sur les différents projet pour ce qui est des perfs :question:
• Pourquoi ne pas, tout simplement, faire confiance au compilateur :question:
• N'est il pas beaucoup plus sensé de préférer un codage qui favorise, avant tout, la relecture (et donc la modification a posteriori) du code :question:

Citation:

---

Envoyé par Kujara

Citation:

---

std::vector<T>::size est toujours en temps constant.
Le seul conteneur où ce n'est pas toujours le cas, c'est std::list, à cause de std::list<T>::splice.

---

Pour vector, oui. Pour les autres,trouve moi une source officielle qui confirme et je l'integrerais dans le sujet ?Merci d'avance ^^.

---

Extrait du standard (désolé pour la mise en forme, à la base, c'est un tableau...) :

Code:

---

1 2 3 4 5

expression | return type | operational semantics | assertion/note | complexity a.size() | size_type | a.end() - a.begin() | | (Note A)   Those entries marked ‘‘(Note A)’’ should have constant complexity.

---

Donc, ce n'est pas garanti à 100% (emploi de should), mais très fortement conseillé.

Citation:

---

Envoyé par koala01

[*]Est-ce réellement utile :question:[*]Pourquoi ne pas faire confiances aux équipes travaillant sur les différents projet pour ce qui est des perfs :question:[*]Pourquoi ne pas, tout simplement, faire confiance au compilateur :question: [*]N'est il pas beaucoup plus sensé de préférer un codage qui favorise, avant tout, la relecture (et donc la modification a posteriori) du code :question:[/LIST]

---

C'est bien de lire le titre du sujet ^^.

J'ai jamais dit que c'etait *obligatoire* de faire des optimisations.

Ce sujet n'existe que pour les gens qui, comme moi, ont *besoin* de performance.

Les autres, c'est pas la peine de rester ici.

Pour répondre a tes 4 questions :

Citation:

---

[*]Est-ce réellement utile :question:

---

Tu prefere avoir un temps de chargement de 5 secondes ou de 3 minutes, dans un jeu ?

Citation:

---

[*]Pourquoi ne pas faire confiances aux équipes travaillant sur les différents projet pour ce qui est des perfs :question:

---

Si c'est toi qui ecrit le projet, qui va optimiser a ta place ? Personne ....

Citation:

---

[*]Pourquoi ne pas, tout simplement, faire confiance au compilateur :question:

---

Parcequ'il est très, très mauvais, contrairement a ce que tu pense :/.
Tu peux multiplier les performances par 10 ou plus si tu optimise a la main certaines choses.
Et ne viens pas me dire que c'est impossible, je l'ai fait plusieurs fois, avec un compilo qui est connu pour etre bon.

Citation:

---

[*]N'est il pas beaucoup plus sensé de préférer un codage qui favorise, avant tout, la relecture (et donc la modification a posteriori) du code :question:

---

Si la performance n'est pas ce que tu recherche ou si ce n'est pas un bout de code critique, oui.

Mais jusqu'a présent, je n'ai pas donné de bout de code illisible, que je sache ? ^^.

J'ai lu, non seulement le titre, mais aussi toutes les interventions, et c'est en partie ce qui a justifié la mienne, qui avait surtout pour but de remettre, pour certains, les choses un peu à leur place ;)

Citation:

---

Tu prefere avoir un temps de chargement de 5 secondes ou de 3 minutes, dans un jeu ?

---

Le plus souvent, cela nécessite d'optimiser la manière dont les données doivent être organisées pour permettre la récupération et le matériel qui entre en jeu, voire, l'algorithme de récupération, rarement la manière dont l'algorithme est implémenté ;):

les bandes passantes et taux de transfert de la connexion internet ou du disque dur -ou de tout autre matériel/port entrant en ligne de compte - seront de toutes façons bien plus de nature à faire "perdre son temps" au processeur que le fait qu'une boucle prenne deux périodes de plus pour fournir le résultat exploitabe;)

Pour perdre une seconde sur une boucle qui perdrait 2 périodes à chaque itération, il faudrait qu'elle soit exécutée... 1 000 000 000 de fois...

Crois moi, Bien souvent, si tu obtiens le résultat en 1 minutes en lieu d'en 30 secondes, et pour autant que tu utilise l'algorithme adapté, c'est bien plus souvent du au matériel qu'à l'implémentatin de l'algorithme ;)

Citation:

---

Si c'est toi qui ecrit le projet, qui va optimiser a ta place ? Personne ...

---

Sauf que, là, tu te base en grande partie, et de toutes manière, sur de l'existant: S(T)L, boost, libc et autres... et tous les projets sont dans le cas.

Citation:

---

Parcequ'il est très, très mauvais, contrairement a ce que tu pense :/.
Tu peux multiplier les performances par 10 ou plus si tu optimise a la main certaines choses.
Et ne viens pas me dire que c'est impossible, je l'ai fait plusieurs fois, avec un compilo qui est connu pour etre bon.

---

Et je peux te citer plusieurs cas parus sur le forum dans lesquels on a été bluffé par le résultat assembleur obtenu, tant on avait tendance à prendre le compilateur pour un imbécile :roll:

Il nous a même sorti des choses auxquelles on n'aurait pas forcément pensé :D

Citation:

---

Si la performance n'est pas ce que tu recherche ou si ce n'est pas un bout de code critique, oui.

---

Le problème, c'est qu'un code critique n'apparaît qu'une fois que l'on a quelque chose qui fonctionne, et à grand renfort d'outils de bench.

Dans la plupart des conseils donnés, on se rend compte que si l'on peut les approuver, il reste quand même un mais... ce qui fait que ça reste des conseils dont l'efficacité n'est démontrée que dans certains cas particuliers

Je ne dis pas qu'ils sont faux, et je ne dis pas qu'il ne faut absolument pas tenir compte des performances générales...

Ce que je dis, c'est que, bien avant d'essayer de gagner un peu de temps par une astuce ou une autre d'écriture - car au final, le compilateur reste quand même le maître de cérémonie - il faut surtout veiller à créer l'algorithme le meilleur possible...

Citation:

---

Envoyé par Kujara

Par contre je peux quand même completer la faq avec les maps / multimaps. Faut contacter qui ? ^^

---

Très imple, tu le mets dans un topic nouveau dans le forum Contribuez de la partie C/C++, et lors d'une mise à jour, ce sera ajouté.

Citation:

---

Envoyé par Kujara

Le probleme avec ton exemple c'est que ton objet A temporaire n'est justement pas referencé.Donc lui meure.

Code:

---

1 2	const A & l_a = getA(); const std::vector<int>& values = l_a.values();

---

La ça marche très bien, la reference sur A le garde vivant jusqu'a la fin du scope.

---

Non, dans ce cas, l'objet A est supprimé à la fin de la ligne le créant. Ta référence est invalide. Dans certains cas, ça va marcher, dans d'autres la mémoire aura été réallouée et là plantage.

Citation:

---

Envoyé par Kujara

C'est bien de lire le titre du sujet ^^.

J'ai jamais dit que c'etait *obligatoire* de faire des optimisations.

---

Il y a deux types d'optimisations. Il y a les utilisations correctes des outils et les hacks. Les hacks sont à éviter, les utilisations correctes à utiliser quoiqu'il arrive (early optimization is the root of all evil).
Il y a beaucoup de choses ici qui font partie de la première catégorie, comme effacer des données, trier, ...

Citation:

---

Envoyé par Miles

Non, dans ce cas, l'objet A est supprimé à la fin de la ligne le créant. Ta référence est invalide. Dans certains cas, ça va marcher, dans d'autres la mémoire aura été réallouée et là plantage.

---

Faux, si tu fait des affichages dans les constructeurs / destructeurs, tu verra ...

Citation:

---

Les hacks sont à éviter, les utilisations correctes à utiliser quoiqu'il arrive (early optimization is the root of all evil).

---

Les hacks sont a utiliser quand on cherche la performance maximum, a la fin d'un projet.
Evidemment les hacks en debut de projet, bad.

Citation:

---

Sauf que, là, tu te base en grande partie, et de toutes manière, sur de l'existant: S(T)L, boost, libc et autres... et tous les projets sont dans le cas.

---

Pour l'instant je n'ai parlé que de la STL, oui. Et pour la stl, les algos sont connus, etc. Donc j'en profite pour les redonner a ceux qui ne les conaissent pas.

Citation:

---

Et je peux te citer plusieurs cas parus sur le forum dans lesquels on a été bluffé par le résultat assembleur obtenu, tant on avait tendance à prendre le compilateur pour un imbécile

---

Links je te prie, ça m'interesse.

Citation:

---

Pour perdre une seconde sur une boucle qui perdrait 2 périodes à chaque itération, il faudrait qu'elle soit exécutée... 1 000 000 000 de fois...

---

Sur un moteur de jeu( 3D ou physique), c'est vite atteint. Perds 1 operation par çi, une autre par la ... au final les imperfections s'accumulent et tu perds 50 % de performances ...

Citation:

---

il faut surtout veiller à créer l'algorithme le meilleur possible...

---

Pas d'inquietude, je vais y venir. La stl c'etait juste pour commencer et jauger de la réaction des gens a mon initiative.
Pour l'instant ça va, critiques assez constructives dans l'ensemble. Je vais continuer.

Je vais essayer de clarifier ma position:

L'utilisation d'astuces de codage vient très loin dans la liste des choses à entreprendre dans le but d'optimiser la vitesse pure.

J'accepterais d'en parler s'il y avait une discussion sur tout ce qui peut être entrepris avant, trop souvent passé à la trappe, et qui est d'ailleurs généralement de nature à fournir des gains bien meilleurs de performances...

En priorité, il y a effectivement le choix des structures pour représenter ses données:

Utiliser un tableau (dynamique ou non, std::vector ou "C style"), alors que l'on va principalement accéder aux données "de proche en proche", et/ou que l'on va effectuer un tas d'ajout ou de suppression est un très mauvais choix, tout comme le choix d'une liste alors qu'on ne prévois que peu d'ajouts ou de suppression lors de l'utilisation, et qu'on veut pouvoir accéder aux éléments dans un ordre aléatoire est un mauvais choix.

En ex-aequo, on trouve la logique à mettre en oeuvre:

Dépendant en grande partie du choix des structures utilisées, il faut accepter l'idée de réfléchir à "un autre chemin" pour arriver au résultat obtenu: tous les chemins mènent à rome ;):roll:

Parfois, il existe des petits trucs simples qui permettent de gagner du temps d'exécution (par exemple: ne tester que jusqu'à sqrt(nombre) si on cherche à savoir si c'est un nombre)

J'affirme que, tant qu'il reste un type de structure et une idée - aussi farfelue soit-elle - de logique à teste, cela ne sert strictement à rien de vouloir gagner quelques périodes grace à une astuce de codage, et que les modifications doivent d'abord et avant tout être envisagées sur ces deux points...

Une fois que tu auras envisagé toutes les solutions au niveau des structures et des algorithmes, tu *peux* éventuellement envisager de grapiller quelques périodes grâce à une astuce de codage du meilleur algorithme utilisant la meilleure structure.

Cependant, voilà... on en revient à ma question: sachant que le gain sera infinitésimal, est-ce que cela en vaut réellement la peine :question:

Citation:

---

Envoyé par Kujara

Sur un moteur de jeu( 3D ou physique), c'est vite atteint. Perds 1 operation par çi, une autre par la ... au final les imperfections s'accumulent et tu perds 50 % de performances ...

---

Jamais 50% de performances... ou du moins, ce ne sera jamais le gain que tu obtiendra avec des astuces de codages...

Si tu gagne 50% de performances, c'est d'abord et avant tout que tu a accepté l'idée de repenser aux structures et aux algorithmes utilisés ;)

Citation:

---

Envoyé par Kujara

Faux, si tu fait des affichages dans les constructeurs / destructeurs, tu verra ...

---

Selon les compilateurs alors parce que cette référence est normalement invalide, sauf si tu me montres noir sur blanc que le standard l'indique.

Citation:

---

Envoyé par koala01

Jamais 50% de performances... ou du moins, ce ne sera jamais le gain que tu obtiendra avec des astuces de codages...

Si tu gagne 50% de performances, c'est d'abord et avant tout que tu a accepté l'idée de repenser aux structures et aux algorithmes utilisés ;)

---

Oui, mes excuses.

J'aurais du preciser que, pour moi, certaines astuces sont ce que tu appelerait un changement de structure.

Certaines autres passent par un leger changement au point de vue algorithmique.

Mais dans le sens où tout cela est motivé exclusivement par le fait que le proc le traitera plus vite pour une raison X ou Y assez compliquée generalement ( genre retailler les tableaux pour qu'ils rentrent dans le cache, refaire l'algo pour utiliser les registres a fond, parcourir les tableaux dans le bon ordre pour que le proc n'aie pas a rechercher dans la mémoire tout le temps, etc), ce sont des "astuces".




Koala :

Citation:

---

Une fois que tu auras envisagé toutes les solutions au niveau des structures et des algorithmes

---

Parfaitement d'accord. Mais c'est vite atteint comme limite si tu es experimenté en analyse.

Citation:

---

L'utilisation d'astuces de codage vient très loin dans la liste des choses à entreprendre dans le but d'optimiser la vitesse pure.

---

Tu a néanmoins raison sur ce point bien sur, donc je vais faire l'effort de le traiter le plus vite possible, par contre c'est compliqué de penser a tout donc je vais avoir besoin d'aide sur la partie : optimiser ton algo ^^.

Citation:

---

Envoyé par koala01

Jamais 50% de performances... ou du moins, ce ne sera jamais le gain que tu obtiendra avec des astuces de codages...

Si tu gagne 50% de performances, c'est d'abord et avant tout que tu a accepté l'idée de repenser aux structures et aux algorithmes utilisés ;)

---

bah, récemment, j'ai repris un code d'affichage de fonte en 3D ou les passages de paramètres etait mal fait, j'ai gagné près de 30% de perf sans modifier d'un poile l'architecture... Donc ca reste quand même utile de faire attention à bien ecrire de façon performante. (et après réarchitecture, les perf etaient environs 7 fois superieurs :lol:)

Sinon, moi, ce topic m'interesse particulièrement, car comme Kujara, j'ai besoin d'obtenir, autant que possible, les meilleurs perf possibles. Et quand on seche sur la réarchitecture, c'est toujours pratique de pouvoir gratter quelques % en temps d'execution.

Bien sûre, sur des appli "classiques", c'est moins important, mais quand on fait de la 3D temps réel sur des gros moteurs, les perfs sont un objectif permannent.

Citation:

---

Envoyé par bafman

Bien sûre, sur des appli "classiques", c'est moins important, mais quand on fait de la 3D temps réel sur des gros moteurs, les perfs sont un objectif permannent.

---

Ahhhhh, enfin quelqu'un qui me comprends :king: je commençais a me sentir seul ....

Page 1 : Utiliser la STL
Page 2 : ici.

Bon, quelques astuces d'implementation en vrac :
J'en donnerai d'autres plus tard.
N'hesitez pas a commenter dessus si vous pensez pouvoir les optimiser plus.
Et n'hesitez pas a donner vos astuces ...

-> Precalculer les fonctions lourdes.
Très connu mais toujours efficace.
Où : une boucle qui fait appel a une fonction lourde mais previsible ( genre sinus / cosinus).
Quand : seulement si vous y passez souvez et que vous n'avez pas besoin d'une très grande precision.
Comment :
Creer un tableau de 10 x 360 par exemple, faire une boucle qui le remplit avec des valeurs resultats de la fonction.
A l'utilisation, on a juste un utiliser le tableau avec comme index l'angle en dixième de degrès.

Variante : rand().
Rand() peut etre précalculé de cette façon.A eviter si vous voulez un vrai rand, mais si vous avez besoin d'un rand entre 0 et 255, par exemple, c'est parfait.
A cumuler avec la technique suivante pour une vitesse assez incroyable.


-> Index de tableaux en unsigned char / unsigned short.
Ca peut paraitre stupide puisque les registres sont en 32 bits, mais en fait, c'est plus rapide, vu que ça evite d'avoir a verifier que l'index est dans les limites prévues.
Où : si vous avez besoin de boucler sur quelque chose qui a exactement 256 ou 65536 valeurs possibles.
Quand : dès que l'on peut, c'est a dire presque jamais.
Comment :
Exemple de cette technique cumulée avec la précedante :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

const int MAX_SIZE = 65536; unsigned int *g_precalcRands = NULL; unsigned short g_index; void Init() { g_precalcRands = new unsigned int[ MAX_SIZE ]; for( unsigned int i = 0 ; i < MAX_SIZE ; i++ ) { g_precalcRands = rand( ) & 0x1FF; } }

---

Maintenant que c'est rempli, vous avez des rands entre 0 et 511 de façon très, très rapide.

Code:

---

1 2 3 4 5

inline unsigned int myrand() { return g_precalcRands[++g_index]; }

---

g_index etant un unsigned short, il est forcement entre 0 et MAX_SIZE - 1, ce qui correspond a tous les index valides pour le tableau, donc pas besoin de verification.
Et il reviendra tout seul a zero.
Touche finale, même pas besoin de l'initialiser.Si votre compilateur est gentil, il ne le mettra pas a zero, vous evitant d'avoir a appeler g_index = rand() & 0xFFFF; pour l'initialiser a une valeur au pif ...

Certes, c'est pas beau, et ça passe que sur une architecture 32 bits, mais qu'est-ce-que c'est rapide >.<

-> Preallocation de la mémoire.

Où : Là où vous avez un nombre précis d'objets que vous passez votre temps a construire / detruire.
Quand : au moment d'en construire un / detruire un.
Comment : Placement new, et explicit destructor.
Un peu compliqué mais potentiellement très puissant.

Premiere etape : placement new.
Exemple :

Code:

---

1 2	char * l_buffer = new char[256]; std::string * l_string = new ( l_buffer ) std::string();

---

L'exemple est pourri, mais ça donne le principe. La mémoire est alloué en bloc par le buffer, pas lors du new sur l'objet.Celui çi ne fait qu'appeler le constructeur.

Deuxième etape : placement delete, sauf qu'il n'existe pas, dommage.

Code:

---

l_string->~string();

---

Appeler le destructeur comme ça ne libere pas la mémoire, donc c'est a reserver exclusivement a cet usage.


-> Calculs de distance
Technique extremement spécialisée ( je vois pas d'applications en dehors de la 3D / jeux / simulations, mais bon, vous etes inventifs).
Explication directe :
soit 3 points dans l'espace A,B,C.
La distance AB se calcule comme sqrt((a.x-b.x)² + (a.y-b.y)² + (a.z-b.z)²)
Sauf que la racine carrée n'est pas nécessaire quand on fait des comparaisons entre 2 distances.
Ca tombe bien, la racine carrée est une opération couteuse.

Cas pratique : en pathfinding A *, pour trouver les liens les plus courts....


-> Maps de paire d'objets, recherche d'une paire précise.
C'est basé sur le principe d'une hashmap, mais en plus rapide.

Probleme : vous avez une multimap qui stoque des paires d'objet, tous les 2 en pointeurs.Et vous devez recuperer une paire précise la dedans.

Technique : map< __int64 , std::pair< A * , B *>>
Remplacez __int64 par son equivalent local si vous ne bossez pas sous windows ( long long int sous gcc)
la clef de la map se crée comme suit :

Code:

---

__int64 l_clef = reinterpret_cast<__int64>(l_a) + (reinterpret_cast<__int64>(l_b)<<32);

---

Et voila, si vous avez les 2 pointeurs, vous avez la clef, donc vous pouvez chercher sur la map.

Je n'ai pas encore eu l'occasion de tester ça, mais ça me parait prometteur.


Calculs en virgule fixe.
Très, très chaud.
Principe de base : faire vos calculs sur des ints plutot que sur des floats, c'est beaucoup plus rapide ( même si l'ecart diminue avec les proc actuels).
Le problème principal c'est de rester dans les limites des ints malgré les calculs compliqués, et d'eviter d'enchainer les calculs car cela entraine une perte de precision monstrueuse.

Le meilleur exemple que je connais c'est une des demos du moteur Ogre3D, elle s'appelle "Dynamic Textures", et elle tourne au moins 5 fois plus vite avec les ints qu'avec les même calculs en floats...

Pour la préallocation -> http://miles.developpez.com/tutoriel...n/object-Pool/

Je pense que pour le coup de l'indice du tableau, il vaut mieux vérifier d'abord que ça nécessite une optimisation et ensuite seulement essayer d'utiliser cette méthode. Dans un de mes algos, j'ai dû zapper les ints pour passer des long à cause de l'extension à long qui posait un pb.

Pour déjà montrer l'importance d'envisager en priorité de modifier l'algorithme, je peux te citer cette discution dans laquelle je mets en évidence que le fait d'utiliser l'algorithme le plus adapté permet, outre de s'éviter des écritures inutiles, d'obtenir un résultat de manière bien plus rapide, mais aussi de lever certaines restrictions ;)

Pour les optimisations directement apportées par le compilateur, il faudra que je prenne le temps de chercher dans mes archives, mais il y a une discussion (qui date déjà un peu) dans laquelle on s'est rendu compte que sur un code - minimal je te l'accorde - le compilateur nous sortait un code assembleur assez surprenant ;)

Le choix de l'algorithme intervient, par exemple, dans le cadre du choix entre une simple boucle itérative et une fonction récursive:

Il est inutile d'envisager la récursivité pour le calcul de x exposant N, ou pour la factorielle, mais elle sera la méthode la plus simple à mettre en oeuvre, la plus évolutive et au final la plus rapide dans le cadre d'une "tour de hannoi", par exemple...

La petite précision: quand je parle de structures dans mes interventions précédentes, j'entend en fait les structures utilisées pour permettre de faire cohabiter plusieurs élément d'un même type "l'un à coté de l'autre".

C'est à dire, et pour faire simple, de choisir ce qui est le plus adapté entre un tableau, une liste et un arbre binaire (en vous faisant grâce des piles et des files :D)

Un tableau (qu'il soit "C style" ou sous la forme std::vector<>) aura un avantage certain sur les autres dés qu'il s'agit d'avoir un acces aléatoires aux éléments: passer du premier au dixième puis au 15eme avant de revenir sur le deuxième, mais sera catastrophique s'il s'agit d'ajouter des éléments, quelque soit la place à laquelle l'élément doit être ajouté, et surtout s'il doit être inséré entre deux éléments existants.

Une liste sera naturellement plus lente qu'un tableau pour les accès "aléatoires" mais plus performante si de nombreuses insertions/suppressions sont susceptibles de survenir.

Enfin, un arbre binaire trouvera un intérêt certain dans les circonstances où l'on fait énormément de recherches d'éléments.

Evidemment, l'algorithme utilisé dépendra principalement de la manière dont plusieurs éléments cohabitent... Une recherche par exemple prendra

pour un tableau une forme proche de

Code:

---

1 2 3 4 5 6 7

size_t t; //nombre d'éléments du tableau for(size_t i=0;i<t;i++) { if(tab[i]==valeur) return tab[i] }

---

pour une liste une forme proche de

Code:

---

1 2 3 4 5 6 7 8

elem* totest=prem; do { if(totest==valeur) return *totest; totest=totest->next; }while(totest!=NULL);

---

et pour un arbre binaire une forme proche de

Code:

---

1 2 3 4 5 6 7 8 9 10

elem* Chercher(elem* totest, type value) { type val=totest->val; if(val>value) return (totest->gt ? Chercher(totest->gt): NULL); else if(val<value) return (totest->lt ? Chercher(totest->lt) : NULL); return totest; }

---

qui, bien qu'a priori plus complexe permettra de trouver la réponse bien plus rapidement (un élément parmis 255 en 8 exécutions à peine maximum ;):D)

Et, en définitive, ce qui est vrai pour la recherche l'est pour l'insertion, l'ajout, la suppression, le tri et tout ce que tu peux imaginer.

Gagner 8 fois quelques périodes à l'exécution en devient un gain tout à fait marginal ;):D