Discussion :

[LeGreg]

PS:Je sais plus qui a dit qu'on lui avait demandé d'optimiser une boucle for pour un entretien d'embauche mais le mec devait etre sur les nerfs ce jour la

C'est à moi qu'on a demandé ça.

Je ne sais pas si le recruteur était sur les nerfs, c'était chez Electronic Arts et j'ai eu une offre (que j'ai déclinée).

Le but ce n'est pas d'optimiser une boucle. La plupart des questions posées en entretien n'ont aucune application concrete. Au moins pour les questions demandées aux débutants ce sont souvent des problèmes déjà résolus mais qui permettent juste de jauger de la réactivité d'un candidat.
Mais bon si je l'ai citée plus haut c'est juste parce que je trouvais l'idée interessante.

En general il y a peu de questions d'optimisations dans les entretiens que j'ai passé, surtout de la correction de code, beaucoup de calculs mathématiques formels ou l'écriture d'algos non triviaux en temps limité.
L'optimisation c'est la cerise sur le gateau et ce sont souvent des trucs de collègiens, probablement pour jauger ta "culture de programmation".

LeGreg

[LeGreg]

T'inquiète pas le compilateur il optimise bien du moment que ton algo est bien foutu. Dans le cas d'un memcpy si c'est pas bien optimisé je ne vois pas l'intérêt du C. Je crois que ça doit être une des premières instructions qui ont été optimisées à mort.

Le Memcpy générique n'est pas particulièrement optimisé, meme si c'est vrai que le code est simple.
Avec une réécriture qui utilise le support MMX (présent depuis de nombreuses années dans les processeurs), le memcopy de base va deux fois plus vite.

Ce n'est certes pas un gain tel qu'on change d'ordre de grandeur comme faire le memcopy en temps logarithmique du nombre de cases mémoires (mais qui sait un jour peut-etre). Mais deux fois plus vite si c'est pour copier de grandes zones de données ou des images, ce n'est pas à cracher dessus.

LeGreg

[ShootDX]

Pour parcourir tous les éléments d'une chaîne terminée par un '\0' ('\0'-terminated string), au lieu de faire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

for (int i = 0; i < strlen(str); i++) {}

on peut faire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

for (const char* cur = str; *cur != '\0'; cur++) {}

Effectivement, strlen() doit forcément parcourir toute la chaîne pour trouver un '\0', incrémenter un compteur, etc.

[amiro]

je veux savoir comment le parcours d'un tableau a l'aide de pointeur est plus rapide qu'un int i;
merci

[ShootDX]

je veux savoir comment le parcours d'un tableau a l'aide de pointeur est plus rapide qu'un int i;
merci

Ca revient au même (optimisation de la part du compilateur).

[el muchacho]

Pour parcourir tous les éléments d'une chaîne terminée par un '\0' ('\0'-terminated string), au lieu de faire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

for (int i = 0; i < strlen(str); i++) {}

on peut faire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

for (const char* cur = str; *cur != '\0'; cur++) {}

Effectivement, strlen() doit forcément parcourir toute la chaîne pour trouver un '\0', incrémenter un compteur, etc.

Honnêtement, je ne vois pas trop dans quel cas pratique on a besoin de parcourir un tableau de char. Si on se met à écrire du code comme celui-là, il faut se demander si on n'a pas intérêt à utiliser la classe std::string. Dans 99% des cas, la réponse est oui.

* Pour continuer sur les chaînes de caractères, éviter au maximum les printf, sprintf et dérivés, qui sont des usines à gaz. Leur préférer si possible puts (bcp plus simples car pas de formatage) et les opérateurs de C++ cin/cout<< (qui font un maximum de boulot du formatage à la compilation).

* Retarder/limiter le plus possible les opérations de fichier, forcément lentes, en créant des buffers si nécessaire.

* Utiliser la STL = plus de généricité et moins de bugs dans les algos.
Et dans ce cas, utiliser les bons conteneurs et les bons algorithmes aux bons moment.
std::vector (ou pire un tableau C) n'est pas le conteneur le plus adapté pour faire un dictionnaire (accès en O(n)). Un std::map (en O(log n)) ou mieux, un std::hash_map sera nettement plus indiqué (O(1)). De même, pour les grosses allocations, std::deque peut s'avérer plus intéressant que std::vector (ou pire un tableau C).
A part pour des domaines très spécifiques, dès qu'on a affaire à un traitement un peu compliqué (recherche dans un tableau, merge, recherche d'inclusions, etc), vérifier si l'algo n'existe pas déjà dans la STL ou dans des librairies existantes.

* Eviter de créer des hiérarchies de classes de hauteur trop profonde. Au-dela de 4 niveaux, il faut commencer à se poser des questions et chercher à "étaler" une hiérarchie horizontalement. L'accumulation des constructeurs et des destructeurs finit par tuer les performances (voir les librairies java), sans parler de la gestion des exceptions qui peut devenir rapidement problématique. En général, faire des hiérarchies compliquées n'est pas bon signe en OO, -en C++ en tout cas-.
L'utilisation de classes paramétrées (class templates), peut parfois aider. Mais attention à ne pas en abuser, car les templates ne remplacent pas les classes : pas de hiérarchie possible, et le code devient vite illisible, donc une bonne règle à respecter est qu'il faut ne les utiliser qu'avec les types de base en paramètre (int, char, float, boo et int*, char*, float*, bool*l).

Et profiler, profiler, bien évidemment.

ps : l'optimisation du code ne doit pas être une excuse pour ne pas utiliser les techniques connues pour améliorer la robustesse du code, comme les auto_ptr, l'usage de const, des classes stack-based, etc.

[fabien.raynaud]

En terme de rapidité de code, le premier aspect à aborder est l'efficacité de l'algorithme utilisé ainsi que les collections utilisées selon le nombre de données et l'accès qu'on y fera (liste simple, chainées, hash table, etc.)
Après ça, les autres améliorations perfos restent minimes par rapport au temps consacré.

[maxlef]

2 - utilisez les types dont vous avez besoin. C'est quoi cette histoire de préférer les types entiers. on ne "préfère" pas utiliser tel ou tel type, on a "besoin" d'utiliser un type float plutot qu'un type int. Je ne sais pas qui a pondu cette règle.

théoriquement on peux utiliser l'un ou l'autre.... mais il arrive que l'on soit obligé de préférer l'un à l'autre...

d'ailleurs je ne sais pas s'il est plus rapide de convertir les float en int afin de travailler plus rapidement avec les int, ou de rester en float ?

[ShootDX]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

d'ailleurs je ne sais pas s'il est plus rapide de convertir les float en int afin de travailler plus rapidement avec les int, ou de rester en float ?

Si tes floats sont entières (exposant >= 0), alors je dirais que ça dépend du nombre d'opérations et de leur type:
1. Pour additionner deux flottants ou trouver leur différence, il faut aligner leurs exposants (pas besoins pour les multiplications/divisions).
2. Pour convertir un flottant en entier, on ne prend que les (m-e) premiers bits du mantisse en considération, où m est le nombre de bits de celui-ci et e l'exposant du flottant.

Si tes floats ne sont pas entières, il faut voir du côté des décimaux à virgule fixe (exemple: tous les nombres à manipuler sont déjà alignés sur le même exposant, on ne fait que des opérations sur le mantisse).

[salseropom]

Bonjour, j'avoue ne pas avoir lu les 8 pages de réponses alors j'espère que je ne vais pas répéter quelqu'un.
Pour vioir les fonctions qui prennent le plus de temps d'exécution, il faut utiliser le profiler (lors de la compilation, il faut compiler avec l'option -pg

Ce profiler renvoie le temps d'exécution de chacune des fonctions utilisées. Ainsi, on sait tout de suite qu'elle partie du prgm retravailler.

[Caine]

Pour parcourir tous les éléments d'une chaîne terminée par un '\0' ('\0'-terminated string), au lieu de faire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

for (int i = 0; i < strlen(str); i++) {}

on peut faire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

for (const char* cur = str; *cur != '\0'; cur++) {}

Effectivement, strlen() doit forcément parcourir toute la chaîne pour trouver un '\0', incrémenter un compteur, etc.

Honnêtement, je ne vois pas trop dans quel cas pratique on a besoin de parcourir un tableau de char. Si on se met à écrire du code comme celui-là, il faut se demander si on n'a pas intérêt à utiliser la classe std::string. Dans 99% des cas, la réponse est oui.

Des exemples:

Implémenter un parser de langage ou un générateur de code.

Reconnaitre dans un flux de caractères les mots réservés d'un langage. Faire de la surbrillance de sa syntaxe.
Développer un outil qui met en place des balises Doxygen sur des sources existant non documentés.

Ecrire un programme qui parse un source afin de remonter des graphes de contrôle ...

Et pour tous ces cas, il vaut mieux du code C optimisé à l'utilisation de la STL.

* Pour continuer sur les chaînes de caractères, éviter au maximum les printf, sprintf et dérivés, qui sont des usines à gaz.

Je ne vois pas où sont ces usines à gaz? Certes, les flux C++ sont plus jolis, mais je regrette franchement le formatage de chaîne parfois.

Leur préférer si possible puts (bcp plus simples car pas de formatage) et les opérateurs de C++ cin/cout<< (qui font un maximum de boulot du formatage à la compilation).

Oui, et puts ne dois pas être utilisée en même temps que les flux, sinon plantage, au passage. Ainsi que fgets, printf ... Enfin, ça dépend des compilateurs.

* Retarder/limiter le plus possible les opérations de fichier, forcément lentes, en créant des buffers si nécessaire.

Excellent conseil, sauf pour les fichiers de logs servant à debuguer.

* Utiliser la STL = plus de généricité et moins de bugs dans les algos.
Et dans ce cas, utiliser les bons conteneurs et les bons algorithmes aux bons moment.
std::vector (ou pire un tableau C) n'est pas le conteneur le plus adapté pour faire un dictionnaire (accès en O(n)). Un std::map (en O(log n)) ou mieux, un std::hash_map sera nettement plus indiqué (O(1)). De même, pour les grosses allocations, std::deque peut s'avérer plus intéressant que std::vector (ou pire un tableau C).
A part pour des domaines très spécifiques, dès qu'on a affaire à un traitement un peu compliqué (recherche dans un tableau, merge, recherche d'inclusions, etc), vérifier si l'algo n'existe pas déjà dans la STL ou dans des librairies existantes.

Je suis d'accord, dans les applications de haut niveau, la STL est bien. Par contre, tous les domaines de développement ne demandent pas les même temps de réponses, par exemple le temps réel embarqué.

De plus, il y a souvent un surcoût non négligeable en mémoire.

On gagne en sécurité et en économie de code ce que l'on perd en performances et économie mémoire.

* Eviter de créer des hiérarchies de classes de hauteur trop profonde. Au-dela de 4 niveaux, il faut commencer à se poser des questions et chercher à "étaler" une hiérarchie horizontalement. L'accumulation des constructeurs et des destructeurs finit par tuer les performances (voir les librairies java), sans parler de la gestion des exceptions qui peut devenir rapidement problématique. En général, faire des hiérarchies compliquées n'est pas bon signe en OO, -en C++ en tout cas-.

Excellent, tout le monde devrait suivre ce conseil.

L'utilisation de classes paramétrées (class templates), peut parfois aider. Mais attention à ne pas en abuser, car les templates ne remplacent pas les classes : pas de hiérarchie possible, et le code devient vite illisible, donc une bonne règle à respecter est qu'il faut ne les utiliser qu'avec les types de base en paramètre (int, char, float, boo et int*, char*, float*, bool*l).

Et profiler, profiler, bien évidemment.

ps : l'optimisation du code ne doit pas être une excuse pour ne pas utiliser les techniques connues pour améliorer la robustesse du code, comme les auto_ptr, l'usage de const, des classes stack-based, etc.

Il n'est pas toujours possible de profiler, notamment quand le code est embarqué, que le seul profiler possible est un profiler ICE qui coûte plusieur milliers d'euro.

Non, il est plus rentable parfois de générer le code en assembleur, et de calculer les temps d'exécution à partir de l'assembleur. ( Très long et très fastidfieux.)

[Matthieu Brucher]

je veux savoir comment le parcours d'un tableau a l'aide de pointeur est plus rapide qu'un int i;
merci

L'explication est donnée un peu plus haut dans le topic.

Pour la liste de LeGreg, le point 3. Les const, j'en use énormément dans le code que je dois implémenter pour du calcul matriciel. J'ai une classe de matrice, mais quand une opération d'addition crée une nouvelle matrice, il renvoie celle-ci, donc impossible d'utiliser le passage par référence dans mon code si je veux pouvoir faire des calculs comme avec des entiers. Cela fait que les const sont super pratiques car passés avec un argument ou comme effet de la méthode, ça indique au compilateur qu'il n'aura pas besoin de créer un nouvel objet. Ensuite, à lui de voir s'il va effectivement se passer du constructeur ou pas.

[lepoutho]

++ i est plus rapide que i++
idem pour -- i a la place de i--

Cordialement

[lepoutho]

parcours d'une chaine
char * chaine = "salut les copines";
char * pt = chaine;
while (* pt)
{

//ce que je dois faire .....


pt ++
}

[lepoutho]

utiliser l'operateur * plutot que l'opérateur /

float toto = 2;
float titi = toto / 2 ;//pas terrible ...
float titi = toto * 0.5; //meilleur, plus rapide enfin c'est
//ce que je faisais avec de vieux compilo et je continue
//par habitude, mais je n'ai aucune certitude, a voir ...

[moldavi]

utiliser l'operateur * plutot que l'opérateur /

float toto = 2;
float titi = toto / 2 ;//pas terrible ...
float titi = toto * 0.5; //meilleur, plus rapide enfin c'est
//ce que je faisais avec de vieux compilo et je continue
//par habitude, mais je n'ai aucune certitude, a voir ...

Je pense que les compilateurs actuels optimisent tout seul ce genre de calcul.
Ils peuvent même utiliser les registres spécialisés en nombre à virgule. Mais c'est vrai que je n'ai pas personnellement vérifié, j'ai juste lu la documentation.

[lepoutho]

j'ai fait des tests concernant mes précédents posts...
c'est vraiment que des conneries, avec le compilo de
Visual Net ça vaut vraiment pas la peine de jouer au plus
fin, perso code optimisé ou pas je mets le même temps d'execution, va
falloir changer mes habitudes ...

Bonne continuation,

[Rafy]

Le mieux pour optimiser du code c'est d'utiliser des logiciels adaptés : AQtime est surprennant par ses résultats....
Et vous verrez qu'il n'est pas forcément utile d'optimiser un "if" ou un "for" face à des fonctions beaucoup plus gourmandes.

Je fais allusion à des fonctions qui peuvent ralentir un algorythme.
Le plus important dans la lecture d'une chaine de caractère c'est ce qu'on fait des caractères lu ! Si on écrit chaque caractère dans un fichier, que l'on ouvre le fichier à chaque passage dans la boucle qu'on écrit et qu'on referme ensuite.... Le for avec le strlen ou sans ça ne va même pas se voir... Il ne faut pas se focaliser sur des généralités, mais plutot dire je vais optimiser telle ou telle partie du code pour la rendre aussi rapide que telle autre. Et pas dire je vais optimiser ça pour que ça aille plus vite...

Pour ceux qui programme avec directX, des jeux, par exemple, ils seront d'accord avec moi qu'il faut porter ses effots d'optimisation sur la methode de rendu.... Ca ne sert strictement à rien d'optimiser une pauvre boucle qui n'est parcourue que quand on appuye sur telle touche...

Il faut privillégier ses efforts sur les boucles qui sont appellée souvent, qui sont longue (en temps d'éxectution relatif au temps total)....

[Rafy]

La methode béton qui marche à chaque fois si on ne veut pas utiliser de logicel d'optimisation, c'est la methode dite "Du test bourin chrono".....
Tu lance ton application avec un certain algorythme, tu regarde le temps d'éxecution, tu change d'algorythme et tu donne au nouvel algorythme le même travail......
Pour plus de précisions tu fais faire différents travaux aux algorythmes, le plus rapide des algorythme est le meilleur.....
Ca marche à chaque coup, mais c'est super long....

[Rafy]

Ceci dit pour optimiser les boucles ou tres tres tres souvent on fait des additions, des multiplications sur un nombre; il est préfèrable d'utiliser si possible les opérateurs +=, -=, *=, /= car il n'y a pas de copies...
Donc si vous faites des class de base de calculs (vecteurs, matrices) ne pas oublier ces opérateurs....
AQtime dit par exemple, dans un code comme celui ci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
int i = 1;
int j = 1;
for (int k = 0;k < 100000; ++k)
{
    i = i + 15;     // Ligne 1
    j += 15;       // Ligne 2
}

Ligne 1 : 66%
Ligne 2 : 33%

De même, il est préfèrable d'utiliser l'opérateur ++"" à l'opérateur ""++
pour des raisons de copie encore (même remarque qu'au dessus pour les class perso)