Optimisation
tablier
Membre
Mon fils qui programme sur pc m'a demandé combien de temps prend mon Mac pour faire des boucles vides. Je mets en pièce jointe le petit programme de test que j'ai écrit. Les résultats sont tels que je n'y comprends rien: 832 ms pour 2560000000000000000 boucles. Le problème, ce doit être l'optimisation. Si vous avez un explication, je suis intéressé.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Peuvent aussi rentrer en ligne de compte tout le contexte autour de ta boucle.
Si tu n'utilises pas du tout les variables après la boucle, le compilateur qui optimisera bien ton code va carrément complètement enlever cette boucle inutile qui ne fait rien. Si tu utilises ces variables après la boucle, il va quand même enlever la boucle for et la remplacer directement par une affectation.
De même il y a peut-être d'autres Threads qui tournent en parallèle pendant ton compte, pouvant ainsi le ralentir. Mettre tout ça dans une RunLoop d'une appli Cocoa ajoute également du contexte autour (un programme en C brut avec juste un "maim.c" aurait été mieux pour faire du benchmark brut)
Enfin, ça dépend de la méthode que tu utilises pour ton BenchMark. Si ta fonction TickCount prend qques millisecondes, ces millisecondes sont forcément comptées dans ton temps de benchmark. Idéalement pour s'approcher un peu plus du temps réellement pris par ta boucle, il faudrait écrire "UInt32 apres2 = TickCount();" immédiatement après la ligne "apres = TickCount();", on aurait ainsi apres2-apres qui contiendrait le temps mis par la fonction TickCount, à soustraire de ton calcul apres-now (temps_boucle_for = apres-now - (apres2-apres))
Je vais refaire ça en C pure. Ce qui m'a interpellé c'est le chiffre aberrant!
Pour info, les conditions de compilation:
OSx 10.6.8
Xcode 3.2.6
Architecture 64-bit Intel
SDK OS X 10.6
Compilateur GCC 4.2
Déploiement 10.6
optimization None
Xcode 3
GCC
Pas d'optimisation
...
Rassures moi, ton fiston n'est pas programmeur?
Et si! DUT en France + "Bachelor in science in computing" in England. Il ne veut pas connaitre les machines Apple "c'est de la m..de!"
@Aligator
tu parais trouver évident que GCC 4.2 fasse n'importe quoi!
J'ai aussi les Xcode 4.3.2 et 5.1.1 Tu crois qu'avec les mêmes sources et les mêmes réglages llvm va donner des résultats différents?
Et puis compile en Release, en -O3, avec les réglages qui vont bien, si tu veux pouvoir sortir un chiffre qui va bien.
Quant à l'objectif premier de la question, ça me fait bien marrer si ton fils se base sur ce genre de question pour savoir si une machine est mieux qu'une autre ^^
Ok. Ca c'est dit... Encore un esprit bien formaté.
Profitons en au moins pour réfléchir avec des travaux pratiques. Alors est-ce que LLVM est super tip-top mieux que GCC? Le mieux est encore de tester avec un vrai cas d'école qui fasse vraiment monter en charge nos machines (et puis tiens on va ajouter l'OpenCL comme c'est mon jouet du moment)...
http://www.eliotis.com//videos/benchgalaxy.mp4
Bilan:
- Gain de l'ordre de 5 à 6% avec LLVM en compilation x86 64 bits. Pas de quoi fouetter un chat donc mais c'est toujours bon à prendre.
- Open CL (jet naà¯f sans usage des caches de mémoire locale de la GPU) prend le large. Et encore avec seulement 8000 particules, il n'est pas à pleine charge (en poussant à 64000 on peut dépasser les 100 GFlops sans problème).
A noter au passage même si la vidéo ne le montre pas, que tout comme pour GCC à l'époque, avec LLVM l'auto-vectorization ne semble pas opérationnelle sur x86. J'optimise moi même manuellement mes boucles critiques (gain de l'ordre de 5 GFlops ici sur le CPU).
En fait, ce n'était pas sa question de base. Il ne cherchait pas a comparer des machines. En 2D, il a un point (bonhomme) qui se balade librement dans un espace clos comportant des obstacles. Le point a un champ de vision (de 40° par exemple) et il veut obtenir ce que voit le point. Son algorithme marche bien sauf qu'il demande un grand nombre de boucle et il se pose la question du temps de gestion des boucles vis à vis du temps total de calcul, car dans les cas compliqués le calcul est trop lent.
Sur le web on trouve un certain nombre d'exemples fonctionnels, mais rarement d'explications correctes.
Je pense que ça s'apparente un peu au ray-tracing.
Merci les universités Française et Anglaises!! Et malheureusement c'est encore comme ça dans beaucoup d'université.
Des pistes d'optimisation:
- précalculer tout ce qui peut l'être hors boucles et créer des caches si possible pour les données récurrentes.
- limiter la précision des calculs (pas de double précision si des float suffisent) pour l'arithmétique. Vu le cas que tu décris, j'irais même jusqu'à penser qu'on peut descendre encore à 16bits de précision.
- voir pour optimiser les boucles critiques en les vectorisant manuellement (jeu d'instruction SSE).
C'est bien là tout le problème du bachetage: on ne fabrique pas des têtes bien faites, on se contente de les remplir avec un programme scolaire.
Mais il faut tout de même relativiser. J'ai eu deux profs extraordinaires en prog à l'université (un en algo et l'autre en programmation temps réel). Je ne les remercierai jamais assez pour leur passion communicative. Un grand pas en France serait peut-être de former et sélectionner nos enseignants non pas sur du savoir mais sur la capacité à passionner leurs élèves.
L'optimisation d'un programme, c'est bien plus que calculer le temps que prend chaque méthode/fonction.
C'est bien plus complexe que ça, il y a des cours entiers sur le sujets tellement ça tire plein de concepts.
Par exemple, en vrac:
- La parallélisation des boucles.
- La vectorisation des calculs.
- Le cache-hit (qui dépend lui-même de choses comme tes niveaux de cache, ton nombre de régistres disponibles, etc).
- Si tu as des memory-barriers qui empêchent une optimisation.
- Si tu utilises de l'OpenCL ou pas.
- Si c'est Multi-Threadé ou pas (d'ailleurs, rappelons-le, le multi-threading *ralentit* l'exécution d'un code " puisque le scheduleur fait du time-sharing entre les threads pour donner la main à chacun par petits créneaux " et non l'accélère comme certains seraient tenté de le croire, sans parler du fait que si l'exécution de l'algo est réparti sur plusieurs coeurs, il faut prendre en compte le temps de transfert des données mémoire entre les 2 coeurs et le fait qu'on n'a pas toujours un cache partagé)
- Le niveau d'optimisation de ton compilateur (qui va faire du déroulement de boucles pour certains cas, pas pour d'autres, etc)
- Et j'en oublie un paquet.
En résumé, surtout vu la complexité des architectures d'aujourd'hui, l'optimisation d'un code et son temps d'exécution (surtout si tu fais de l'algorithmie) sont très très loin de se limiter à isoler le bout de code de son environnement et de le réduire au strict minimum pour l'étudier. On peut pas réduire le problème que tu exposes à "quel temps prend mon Mac à exécuter des boucles for vides". Selon le contexte la réponse à cette question n'aura rien à voir.---
La compilation d'un programme informatique, la génération du code final et son exécution sont à la fois déterministes (donnant tjs le mm résultat) mais aussi à forte entropie et très influençables par les éléments exétieurs : le moindre changement dans le contexte (changement dans le code source, ou changement dans le contexte d'exécution type cache ou nombre de processeurs ou autre) peut te générer un binaire assez différents, où le compilateur va t'ordonner les instructions dans un ordre plutôt qu'un autre pour mieux optimiser les choses, et un temps d'exécution qui peut être sensible à la fois à l'architecture cible et à l'état de la machine à l'exécution.
Par exemple si tu exécutes un bête programme qui se contente de faire une bête boucle for et un calcul, à la première exécution il pourra prendre du temps (car va charger les données sur lesquelles il va faire le calcul & tout), et les exécutions suivantes peuvent être ensuite très très rapides (car tout est en cache L2 ou L3). Si le même bout de code fait partie dans un programme plus large, tu risques d'avoir bcp + de cache-miss et donc ne pas avoir cet effet de cache entre 2 exécutions...
Ali a raison, pour optimiser du code il est impératif de le mesurer dans son contexte.
A te lire, on pourrait presque croire qu'un programme multi-threadé va être plus lent au final.
Par exemple si tu as un calcul A qui prend 2s, puis un calcul B qui prend 3s, ça va s'exécuter dans un total de 5s en mono-thread.
Mais que si tu utilises du multi-threading pour exécuter les 2 algos en parallèle chacun dans son thread, ça ne va pas prendre 3s (le temps le plus long des 2) parce que les 2 s'exécuteraient en parallèle. Ca va plutôt faire un truc du style "ça exécute le début de l'algo A pendant 1s, puis ça va basculer sur le thread de l'algo B pendant 1s, puis ça va rebasculer sur le thread de l'algo A pour terminer la 2e seconde de l'algo A, puis ça va rebasculer sur le thread de l'algo B et le finir. Au total ça fera 1s (A) + 1s (
Au final tes 2 algos ne seront finis qu'au bout de 5.5s après le démarrage des 2 algos.
Alors évidemment, si tu as un ordi multi-coeurs, tu ne vas pas avoir qu'un seul coeur exécutant tout les threads en temps partagé. Tu vas pouvoir avoir un thread sur un coeur et l'autre sur l'autre coeur, et donc du coup chaque coeur ayant son CPU / son processeur va exécuter son thread dans son coin, il n'y aura pas à partager un CPU pour 2 threads en temps partagé. Donc là ça va prendre 2s sur 1 coeur et 3s sur un autre, mais en parallèle, et donc tu auras juste à attendre 3s pour avoir le résultat de tes 2 algos.
Si les 2 algos A et B partagent certaines données, cela devient plus compliqué, car non seulement il faut que tu protège l'accès à ces données (pour pas que le thread A ne modifie certaines données pendant que le thread B est en train de les lire, ou pire de les modifier lui aussi), donc avec des Mutex & autres sémaphores, et ça aussi ça prend un peu de temps de verouiller les mutex & co, donc ça ralentit un poil ton algo juste parce que tu dois protéger les accès aux ressources partagées. Et puis il y a le temps de transfert des données jusqu'au processeur, si ces données ne sont pas en cache L1 ou L2.
Bref, autant de paramètres qui font que dans ce genre de cas que j'ai pris en exemple, rendre ton programme multithread va plutôt le ralentir que l'accélérer.
---
Exemple type, si au lieu d'exécuter du code sur ton main thread " et de bloquer ainsi l'UI de ton appli, donnant l'impression à l'utilisateur que ton appli est gelée/plantée " tu choisis d'exécuter ce code dans un thread secondaire. Le code ne va pas s'exécuter + vite parce qu'il est dans un thread secondaire et pas dans le thread principal. Au contraire potentiellement le code dans le thread va être exécuté par intermitence si tout ça est en du temps partagé sur un même processeur.
Donc tu vas y gagner fortement en ergonomie utilisateur car l'utilisateur va pouvoir continuer à utiliser son interface graphique, bouger les fenêtres, faire avancer une barre de progression, etc et n'aura pas l'impression que l'appli est plantée. Mais tu vas peut-être y perdre en temps d'exécution dudit code potentiellement (oh, un tout petit peu, cette perte de temps est ridicule face au gain d'avoir cette meilleure expérience utilisateur hein, donc ça vaut largement le coup) puisque son thread va être interrompu de temps en temps par le scheduleur.
Evidemment, là j'ai fait exprès de prendre des cas qui mettent en avant ce cas de "c'est plus long qd je met mon code dans un autre thread", pour un peu casser le mythe du "c'est multithread DONC c'est plus rapide".
Mais dans d'autres cas, surtout si ton ordi est multi-coeur et donc que tes threads peuvent être exécutés chacun sur des coeurs séparés et que les algos sont indépendants, évidemment que par contre tu pourras y gagner. Faut juste garder à l'esprit que c'est pas systématique ni magique.
Eh oui que veux-tu, on ne s'improvise pas développeur comme ça sur un coup de tête, c'est un métier...
En tout cas je trouve que c'est toujours utile d'avoir un minimum de connaissances sur l'architecture des systèmes et le fonctionnement sous le capot de tout ça, threads & co (et il y a de quoi faire sur le sujet !), et ce quel que soit le langage de programmation et la plateforme dont on parle (sur PC c'est pareil, en C c'est pareil, ...).
Car mine de rien cela a pas mal de conséquences, et même si des choses comme GCD ont grandement facilité tout ce qui concerne le traitement de tâches en parallèle ou sur des files de traitement dédiées, en ayant moins à se prendre la tête sur les concepts de ressources partagées & co (on peut toujours mais bcp moins pour les cas les plus usuels), il reste toujours des cas où c'est utile de comprendre tout cela.
Effectivement Ali, il faut raison gardée sur le multi-threading et l'utiliser quand le contexte s'y prête. C'est comme tout. Dans le cas du fils de tablier, j'ai tout de même l'intuition que le contexte devrait bien s'y prêter.
Il y a aussi parfois des optimisations algorithmiques liées au mono-threading qui posent problème. Par exemple, pour un simulateur de particules, on passe en revue chaque particule et on calcule la force exercée par ses congénères. Jusque là rien de bien complexe sur le principe. Si on tourne sur un système mono-thread, on peut se permettre une optimisation assez simple: si toutes les particules ont la même masse alors la force entre particules est réciproque. Grace à cette astuce, on peut diviser par deux le nombre de calculs nécessaires puisqu'une particule 'a' exerce une force F sur une particule 'b' mais du coup l'inverse est aussi vrai au signe près. Le problème c'est que si on passe cette algo en multi thread, cette optimisation ne peut être conservée à cause de conflits d'accès. La masse de calculs nécessaires réels étant alors doublée, deux coeurs ne sont pas suffisant pour compenser. Un traitement sur deux coeur est alors moins rapide qu'avec la version optimisée mono-thread. Il faut avoir au moins 4 coeurs pour que le parallélisme prenne l'avantage.
Juste pour la caféine !
Sympa comme article. Il n'y a que la partie "Don't prematurely optimize." qui me fait un peu ticker. Pour moi c'est une approche à la Javaà¯ste ça:
L'optimisation d'un code, c'est toujours plus facile si elle est pensée en amont. C'est comme aux échecs, l'expérience permet d'avoir un coup d'avance et d'anticiper. Et c'est d'autant plus vrai que certaines optimisations non anticipées c'est souvent des pans entier de code à recoder.
Et je ne peux qu'aller dans son sens, j'ai déjà vu et vécu des cas où on passe des heures ou des jours à essayer d'optimiser un algo (muquaddar, si tu nous entends, avec tes questionnements sur ta synchro...) en pensant que c'est le coeur du problème et que c'est lui qui ralentit tout... Alors que si on lance Instruments pour faire un simple Time Profiling, on se rend parfois compte que finalement cet algo en question il n'était pas si lent, et en tout cas et surtout c'est loin d'être lui qui prend le plus de temps dans l'appli, et que s'il y a qqch à optimiser c'est plutôt tel autre truc qui prend 2s que cet algo qui en prend 400ms.
Ca revient à ce qu'on disait plus haut sur le multi-threading qui n'est pas forcément, selon les cas, une solution qui va accélérer les choses. Ca dépend des cas. Ca ne sert à rien de se jeter sur un bout de code ou une solution en imaginant que c'est THE solution qui va tout accélérer, alors qu'en fait ça n'aura pas l'effet escompté ou que, pire, on a passé un temps fou sur l'optimisation de ce truc alors qu'en fait c'était le code d'à côté qui était le plus ralentisseur.
Oui je vous entends, ou plutôt je vous lis...
Cela dit cette discussion est assez "haut niveau" et on voit ce qu'on perd quand on n'a pas eu de cours de fac ou d'école d'ingé... Apprendre tout seul, ça a vraiment ses limites.
J'ai trouvé un goulet d'étranglement énorme côté serveur il n'y a pas plus d'une heure pour ma synchro d'images: le téléchargement des images d'AWS s3 en batch passait par mon serveur avant d'être envoyé au client. Autrement dit, l'image était d'abord téléchargée sur mon serveur (ce qui bouffe en plus de la ram) avant d'être redirigée vers le client avec send_file(). Je pensais que ce n'était pas le cas de send_file() justement (puisqu'on lui envoit une url), contrairement à send_data() (à qui on donne du data)... Et donc avec un redirect 302 tout bête vers la ressource, j'ai passé mon pull() batch de 48 images (de 100Ko en moyenne) de 28 secondes à 3,5 secondes !!!
Certes, ça n'a rien à voir avec une boucle, ou GCD ou OpenCL, mais l'optimisation est partout ! (et parfois à notre détriment)
Enfin, j'ai essayé de changer le nombre de maxConcurrentOperations, et là , pour le coup, ça n'a l'air de rien apporter...
Edit: enfin, si ça change quelque chose... je l'ai passé à 1 opération à la fois et je suis retombé à 30 secondes, simplement, c'est le système qui détermine ce nombre par défaut... donc je ne sais combien il choisit quand ce n'est pas précisé, et ce n'était pas précisé dans mon cas de 3,5 secondes.
Si tu regardes ton nombre de thread lancés au niveau de l'appli pendant que GCD tourne, tu verras qu'il se cale en règle générale sur ton nombre de coeurs. Après il y a peut-être des subtilitées si une autre appli est en charge mais globalement ça va pas plus loin.
Une chose que je ne m'explique pas avec Xcode c'est la disparition du mode debug/release. Du coup, je suis obligé de me créer un sheme en mode release sur mes projets pour pouvoir testers les perfs en situation réelle que ce soit en live ou avec Instruments. Il y a une autre astuce?
Et ils sont même mieux intégrés, puisque quand tu regardes ton Scheme par défaut, il est configuré pour que quand tu utilises l'action "Run" ça compile avec la configuration Debug, mais quand tu utilises l'action Profile (pour lancer Instruments et faire du Profiling) ça utilise la configuration Release (et de même pour quand tu demandes une Archive dans le but de faire une livraison)...
Pardon, je précise: disparition au niveau de la toolbar. Du coup, je suis obligé de créer un Sheme dédié pour pouvoir switcher rapidement.
Je vais dans le sens de Mala!
J'utilise Xcode 3.2.6, 4.3.2 et 5.1.1. sous OSx 10.6.8, 10.7.5, 10.8.5 et 10.9 (et parfois Xcode 2.5 sous 10.5.8)
Les évolutions de Xcode et d'Objective-C font que je perds beaucoup de temps à retrouver comment faire ce que je faisait facilement dans une version précédente parce qu'il existait un menu explicite qui a disparu. Le passage OC-1 à OC-2 et les différents ajouts qui ont suivis font que je m'y perds et que j'ai tendance à ne pas utiliser les nouveautés!
Autre exemple, sous les derniers OSx les fenêtres n'ont naturellement plus de flèches (up-down) dans l'ascenseur vertical. Je n'ai pas encore trouvé comment changer cela et remettre ces flèches (Je préfère la souris au pavé ou l'on use ses doigts).
J'en arrive à penser que toutes ces choses ont été faites pour économiser les doigts des pro sans tenir compte que la majorité des utilisateurs sont des amateurs. Pour les amateurs (dont je suis) cela donne l'impression que pleins de choses deviennent implicites et nous sont désormais interdites d'accès et/ou de modification de réglage. Il est vrai aussi que je ne passe pas mon temps à suivre toutes les évolutions.
Pour ce post que j'ai maladroitement commencé, votre discussion sur l'optimisation m'a remis quelques idées en place! Merci