Optimisation – quelques liens pertinents

Quelques raccourcis :

Vous aurez sans doute aussi de l'intérêt pour la question des mesures (Benchmarks) : ../Sujets/Developpement/Mesure.html

Vous trouverez ci-dessous quelques liens pertinents quant à l'optimisation du code, la mesure du temps d'exécution des programmes, le profilage de code, etc.

Pour la question plus spécifique de la gestion de l'antémémoire (de la Cache), voir ../Sujets/TempsReel/cache.html

Idées d'ordre général

À propos de quelques citations célèbres sur l'optimisation : http://www.randomprogramming.com/2014/05/quotes-of-the-week-efficiency/

Présentation d'Alexander Stepanov sur le design de bibliothèques efficientes : http://www.stepanovpapers.com/Designing%20libraries.pdf

Un chapitre de la thèse sur l'optimisation de Todd Veldhuizen : http://www.cs.chalmers.se/~tveldhui/papers/2004/dissertation/gopt.html#3

Les catégories d'optimisations réalisées par le produit NULLSTONE, expliquées : http://www.nullstone.com/htmls/category.htm

Le blogue de Nigel Jones, axé sur l'optimisation du code à fins de calculs numériques, en particulier pour des systèmes embarqués  : http://embeddedgurus.com/stack-overflow/category/efficient-cc/

Quelques réflexions sur la valeur de l'optimisation :

Make it right before you make it fastDouglas Crockford

Quelques sites Wiki :

Série d'articles généraux sur la pratique de l'optimisation, par Jeff Knupp : http://www.jeffknupp.com/blog/2012/07/10/software-optimization-a-systematic-approach/

Et, pour votre plaisir, quelques exemples de comment ne pas optimiser :

Certains sont d'avis que la vitesse n'importe pas vraiment : http://mortoray.com/2012/02/09/performance-is-irrelevant/

Selon Frank He en 2015, la premìère étape lors d'une démarche d'optimisation est d'admettre que nous n'avons, probablement, pas de réel problème : https://nopointerexception.wordpress.com/2015/07/16/optimizers-anonymous-1st-step-is-admitting-you-probably-dont-have-a-problem/

Quel est le coût de ne rien faire? Texte de Iustin Pop en 2012 : http://k1024.org/~iusty/blog/entry/perf-null/

Un petit test à propos de ce qu'un compilateur peut, ne peut pas ou ne doit pas réaliser comme optimisation, par Cory Doras en 2010 : http://ridiculousfish.com/blog/posts/will-it-optimize.html

Plus de données ou de meilleurs algorithmes? http://anand.typepad.com/datawocky/2008/03/more-data-usual.html

L'art sombre de l'optimisation : http://www.volker-lanz.de/en/software/optimising/

C'est pas facile, optimiser : http://ridiculousfish.com/blog/archives/2006/05/30/old-age-and-treachery/

Ne pas oublier : http://www.drdobbs.com/blog/archives/2010/09/overlooked_esse.html

Mesurer deux fois, optimiser une seule fois. Une réflexion de Larry Osterman en 2004 : http://blogs.msdn.com/b/larryosterman/archive/2004/05/03/125198.aspx

La guerre de l'« optimiseur radical » contre les schémas de conception, une opinion de Jaymin Kessler en 2011 : http://altdevblogaday.com/2011/04/01/the-radical-optimizationist%e2%80%99s-war-on-abstraction-and-patterns/ (notez qu'il s'agit d'un article étrange empli de faussetés...)

Réflexions de James Hague :

Techniques d'optimisation générales :

Dans un ordre d'idées connexe, un texte de Greg Colvin en 2008 qui explique comment écrire du code lent : http://www.artima.com/cppsource/how_to_go_slow.html

Réflexions de Raymond Chen :

Réflexions d'Eric Lippert :

Texte de 2013 par Yosef Kreinin, qui explique que plusieurs processeurs plus faibles travaillant en parallèle donneront typiquement de meilleurs résultats qu'un seul processeur très puissant, ceci étant dû à l'attente régulière que subit chaque coeur pour des données en mémoire : http://www.yosefk.com/blog/amdahls-law-in-reverse-the-wimpy-core-advantage.html

Valider le respect du modèle mémoire à partir des optimisations réalisées sur un programme concurrent en C11 ou en C++ 11, par Robin Morisset, Pankaj Pawan et Francesco Zappa Nardelli en 2013 : http://www.di.ens.fr/~zappa/projects/wmc/readings/pldi13.pdf

Réflexion sur les systèmes de types, les langages de programmation, les machines virtuelles et la capacité d'optimiser le code, par Charles-Oliver Nutter en 2013 : http://blog.headius.com/2013/05/on-languages-vms-optimization-and-way.html

En 2013, Richard WM Jones raconte comment il a écrit un agent de planification pour résoudre un problème d'optimisation délicat : http://rwmj.wordpress.com/2013/12/14/writing-a-planner-to-solve-a-tricky-programming-optimization-problem/#content

Texte de 2013 décrivant des optimisations de dernière minute apportées à un jeu vidéo : http://www.grimrock.net/2014/03/07/performance-optimizations/

Dans le monde du jeu, entre autres domaines, mieux vaut connaître son substrat matériel pour tirer le maximum de ce qu'il a à offrir. Présentation de Keith O'Conor en 2014 : http://fragmentbuffer.com/docs/PerformanceProgramming.pdf

Selon Valentin Simonov en 2014, mieux vaut d'abord optimiser en vue de la lisibilité : http://va.lent.in/optimize-for-readability-first/

En 2014, Paul Khuong trace un parallèle entre l'optimisation et l'écriture d'essais : http://www.pvk.ca/Blog/2014/10/19/performance-optimisation-~-writing-an-essay/

Dans ce texte de 2014, Nitsan Wakart compare le recours à un modulo et le recours à un masque bit à bit pour accéder à des éléments de manière cyclique dans un tableau. Il est toujours préférable de mesurer ses suppositions, faut-il le répéter? http://psy-lob-saw.blogspot.ca/2014/11/the-mythical-modulo-mask.html

Optimiser une fonction récursive pour profiter de la Tail Recursion, par Matt Nedrich en 2014 : http://spin.atomicobject.com/2014/11/05/tail-call-recursion-optimization/

En 2014, Robert C. Martin nous rappelle qu'il vaut mieux ne pas essayer de jouer au plus fin avec un compilateur, à moins bien sûr d'avoir mesuré un problème et de pouvoir démontrer quantitativement un gain de par notre manoeuvre : http://www.randomprogramming.com/2014/10/quote-of-the-week-outsmarting-the-compiler/

La programmation purement en mémoire, par Nikita Ivanov en 2013 : https://gridgaintech.wordpress.com/2013/09/18/four-myths-of-in-memory-computing/

En 2015, Bruce Dawson relate deux moments où écrire le chiffre zéro a mené à des optimisations signifiantes : https://randomascii.wordpress.com/2015/01/19/knowing-where-to-type-zero/

Réflexions de Benjamin Supnik :

La micro-optimisation pour « battre le compilateur » dans un cas pointu, étude de cas par James Brown en 2015 : http://www.roguelazer.com/2015/02/beating-the-compiler/

Comprendre l'impact des Page Faults, texte de 2015 : http://blog.scoutapp.com/articles/2015/04/10/understanding-page-faults-and-memory-swap-in-outs-when-should-you-worry

Les cinq règles de la saine programmation de Rob Pike, qui donnent directement dans les consignes d'optimisation et de programmation efficace : http://users.ece.utexas.edu/~adnan/pike.html

Trouver l'équilibre entre code « propre » et code rapide, article d'Arne Mertz en 2015 : http://arne-mertz.de/2015/03/simple-and-clean-code-vs-performance/

Comme le rappelle Emil Ernerfeldt en 2015, le code le plus rapide est celui qu'on n'exécute pas : http://www.ilikebigbits.com/blog/2015/12/6/the-fastest-code-is-the-code-that-never-runs

Quelques conseils simples mais organisés de manière intelligente et productive, proposés par Howard Hinnant en 2014. Howard Hinnant est l'un des meilleurs programmeurs que je connaisse, et vous remarquerez l'accent mis, dans sa perspective, sur les pratiques qui mènent à du code plus efficace : http://howardhinnant.github.io/coding_guidelines.html

Générer des optimisations qui soient correctes de manière démontrable, par Nuno P. Lopes, David Menendez, Santosh Nagarakatte et John Regehr en 2015 : https://www.cs.utah.edu/~regehr/papers/pldi15.pdf

Intéressant plaidoyer de Jack Mott en 2016, à l'effet que les langages de programmation devraient être conçus de manière telle que le code « évident » soit aussi le code rapide : https://jackmott.github.io/programming/2016/07/22/making-obvious-fast.html

Comment fonctionne un allocateur de registres? Un regard « de l'intérieur », proposé par Ramkumar Ramachandra en 2016 : http://artagnon.com/inside-a-register-allocator/

En 2016, Fabian Giesen explique comment profiter à plein des registres SSE : https://fgiesen.wordpress.com/2016/04/03/sse-mind-the-gap/

Optimiser en fonction de l'espace

Comment construire un « redirecteur » DOS ne consommant que 256 bytes de mémoire vive? Une analyse de Larry Osterman en 2004 : http://blogs.msdn.com/b/larryosterman/archive/2004/11/08/254108.aspx

Décrire une structure de données qui sera plus efficace qu'un tableau brut pour accéder à un élément par son indice et pour retrouver les indices de tous les éléments ayant une valeur donnée, un défi proposé par Terence Siganakis en 2012 : http://siganakis.com/challenge-design-a-data-structure-thats-small

À quel point peut-on compacter des bits rapidement? Un texte de Daniel Lemire en 2012 : http://lemire.me/blog/archives/2012/03/06/how-fast-is-bit-packing/

Parfois, chaque byte compte. Un texte de Cody Powell en 2012 : http://www.codypowell.com/taods/2012/02/bytes-matter.html

Faire entrer un gros programme dans un petit ordinateur : http://www.csd.uwo.ca/Infocom/Articles/small.html

Texte de James Hague en 2011 qui nous rappelle que Turbo Pascal (version 3) était vraiment très petit pour ce qu'il parvenait à faire : http://prog21.dadgum.com/116.html?0

En 2013, ce texte disserte sur l'évolution des outils et la pertinence – ou non – de se préoccuper de l'ajout de 4 bytes à la taille de tous les objets de Delphi, son langage de prédilection. Prudence : ce texte, qui est intéressant, est clairement écrit du point de vue de quelqu'un dont les projets sont des programmes « conventionnels », pas des systèmes en temps réel par exemple : http://subspacecables.com/blog/2013/5/19/abstraction

Proposition de standard IETF pour une représentation compacte des objets, le Concise Binary Object Representation, ou COBR, par C. Bormann et P. Hoffman en 2013 : http://tools.ietf.org/html/rfc7049

Réduire la taille des instances d'une classe C++ :

L'art ancien de la représentation compacte des enregistrements C, par Eric S. Raymond en 2014 : http://www.catb.org/esr/structure-packing/

Réduire l'espace occupé par une chaîne de caractères JavaScript, texte de Jan de Mooij en 2014 : https://blog.mozilla.org/javascript/2014/07/21/slimmer-and-faster-javascript-strings-in-firefox/

En 2015, Chad Austin propose une approche pour réfléchir les besoins d'optimisation : http://chadaustin.me/2015/04/thinking-about-performance/

Gestion de l'antémémoire (de la Cache)

Le contenu de cette section a été relocalisé dans une page à part entière : ../Sujets/TempsReel/cache.html

Techniques d'optimisation numérique

Bibliothèques numériques « à haute performance » de C++ :

Faire des transformées de Fourier sur le GPU? http://gamma.cs.unc.edu/GPUFFTW/

À propos de certaines fonctions numériques de C : http://www.johndcook.com/blog/2010/06/07/math-library-functions-that-seem-unnecessary/

Optimiser par le choix d'un type numérique en C, texte de Fabien le Mentec en 2013 : www.embeddedrelated.com/showarticle/176.php

Réaliser une approximation rapide de pow() dans divers langages : http://firstclassthoughts.co.uk/misc/optimized_power_method_for_java_and_c_and_cpp.html

Calculer exp() et sans utiliser de multiplications : http://www.quinapalus.com/efunc.html

Évaluer efficacement, par John D. Cook en 2012 : http://www.johndcook.com/blog/2012/07/25/trick-for-computing-log1x/

Techniques d'optimisation pour l'intégration numérique : http://www.codeproject.com/KB/recipes/FastNumericalIntegration.aspx

Exploiter la mémoire partagée dans des algorithmes d'analyse numérique : http://www.stanford.edu/class/cs238/lect_notes/lecture11-05.pdf

Quelqu'un a passé beaucoup de temps à réfléchir aux divisions par dix... http://www.avrfreaks.net/index.php?id=PNphpBB2&file=viewtopic&t=37150

Quelqu'un a réfléchi au remplacement de divisions par une multiplication et un glissement de bits... http://ridiculousfish.com/blog/archives/2010/02/15/labor-of-division-episode-1/

Arithmétique sur bits? http://locklessinc.com/articles/256bit_arithmetic/

Améliorer certaines opérations sur des nombres à virgule flottante à double précision : http://falasol.net/2-pow-x-optimization-for-double-type

Optimisation des divisions :

Tenir compte du pipeline du processeur (du CPU) dans le choix des opérations, texte de 2011 (avec une mise à jour en 2014) : http://lolengine.net/blog/2011/9/17/playing-with-the-cpu-pipeline

Écrire du code numérique efficace avec D, par Reija Ljubobratovic en 2016 : http://blog.mir.dlang.io/ndslice/algorithm/optimization/2016/12/12/writing-efficient-numerical-code.html

À propos des Expression Templates

Les Expression Templates constituent une technique d'optimisation remarquable... dans certains contextes.

Profilage de code

Pédagogie :

Quelques outils de profilage « faites-le vous-même » :

Outils professionnels de profilage :

Approches novatrices :

Réflexions plus larges sur le sujet :

Entrées / sorties

Optimisation et exceptions

Les exceptions ont un coût; cependant, étant présumées rares ou inhabituelles (d'où leur nom!), la majorité des compilateurs générera du code à coût essentiellement nul en termes de temps d'exécution (probablement pas à coût nul en termes d'espace mémoire, par contre) si les exceptions ne sont pas levées. C'est probablement là le truc clé pour ce qui est de la programmation avec exceptions : il est préférable de n'en lever une qu'en situation, littéralement, exceptionnelle.

Coût des exceptions sous .NET : http://www.codeproject.com/KB/exception/ExceptionPerformance.aspx

Exceptions rapides avec Java : http://www.javaspecialists.eu/archive/Issue129.html

Exceptions avec C++ :

Alternatives à la gestion d'exceptions, partie 1 et partie 2.

Optimisation et C ou C++

Le Technical Report on C++ Performance, en 1999 : http://www2.research.att.com/~bs/performanceTR.pdf

Tutoriel d'optimisation en C : http://www.abarnett.demon.co.uk/tutorial.html

Conseils généraux d'optimisation en C et en C++ :

Le mot clé restrict :

L'horrible mais divertissante Duff's Device :

Organisation du code et vitesse d'exécution :

Algorithmes :

Chaînes de caractères :

Un (vieil) article sur la conception d'allocateurs (ça peut être instructif) : http://g.oswego.edu/dl/html/malloc.html

L'optimisation avec g++ :

Série d'articles sur l'optimisation du code C++ avec Visual Studio, par Jim Hogg : http://blogs.msdn.com/b/vcblog/archive/2013/05/29/optimizing-c-code.aspx

Série d'articles par Johan Mabille sur l'enrobage d'intrinsèques SIMD avec C++ :

Optimiser un type comme optional<T> : http://www.boost.org/doc/libs/1_59_0/libs/optional/doc/html/boost_optional/tutorial/performance_considerations.html

Le déroulement des boucles, ou Loop Unrolling, expliqué par Katarzyna Macias en 2015 : http://katecpp.github.io/loop-unrolling/

Règle du « comme si » (as-if)

Les compilateurs C++ ont le droit de transformer le code source un peu comme bon leur semble, dans la mesure où cela ne change pas le comportement observable (lire : les effets de bord, le résultat des calculs) d'un programme, donc dans la mesure où le programme post-transformations se comporte « comme si » il s'agissait du programme avant transformations (évidemment, l'idée des transformations est généralement de rendre l'exécution du programme transformé plus rapide que celle du programme original!).

Dans le standard, §[intro.execution]/1, cette règle s'exprime comme suit :

« This International Standard places no requirement on the structure of conforming implementations. In particular, they need not copy or emulate the structure of the abstract machine. Rather, conforming implementations are required to emulate (only) the observable behavior of the abstract machine as explained below[5]. »

La note en bas de page [5] indique quant à elle :

« This provision is sometimes called the "as-if" rule, because an implementation is free to disregard any requirement of this International Standard as long as the result is as if the requirement had been obeyed, as far as can be determined from the observable behavior of the program. For instance, an actual implementation need not evaluate part of an expression if it can deduce that its value is not used and that no side effects affecting the observable behavior of the program are produced. »

La règle du « comme si » ne peut être appliquée de manière aussi « libérale » dans un programme multiprogrammé que dans un programme monoprogrammé, ce qui explique l'avènement d'un modèle mémoire restreignant les optimisations possibles en situation de concurrence.

Pour en savoir plus sur le sujet : http://en.cppreference.com/w/cpp/language/as_if

EBCO, le Empty Base Class Optimization

L'optimisation EBCO, ou Empty Base Class Optimization, permet à un compilateur d'« aplatir » une classe parent dans son enfant lorsque le parent n'a pas d'attributs d'instance. Par exemple :

struct Base { // n'a aucun attribut d'instance; en pratique, un Base occupe au moins un byte en mémoire
   int f() const { return 3; }
};
struct E0 {
   Base base; // ici, base occupe au moins un byte d'espace dans E0
};
struct E1 : Base { // ici, la partie Base d'un E1 peut ne pas occuper d'espace dans ce E1
};

Pour en savoir plus :

Inlining

L'inlining, ou le remplacement (par le compilateur) du code d'un appel de fonction par le code de la fonction appelée :

RVO, le Return Value Optimization

L'optimisation RVO, ou Return Value Optimization, permet à un compilateur d'éliminer des copies lorsque la valeur retournée par une fonction est utilisée pour initialiser un objet. Par exemple :

vector<int> creer() {
   return { 2, 3, 5, 7, 11 };
};
int main() {
   vector<int> v0; // constructeur par défaut
   v0 = creer(); // remplace le contenu de v0 par ce que retourne creer()
   auto v1 = creer(); // pas besoin de copier un vector<int>, il est possible
                      // de construire v1 directement et éviter une temporaire
}

Notez, car c'est important, que RVO est particulier en ce sens qu'il s'agit d'une des rares optimisations permises en C++ qui ne soit pas as -if, au sens où sa mise en application a un effet reconnaissable (autre que la simple accélération de l'exécution du programme) du fait que certaines méthodes (un constructeur, un destructeur, parfois une affectation) ne seront pas appelées avec cette optimisation et le seraient sans elle. Cette forme de Copy Elision est malgré tout permise, mais n'est pas obligatoire avant C++ 17; à partir de C++ 17 toutefois, il deviendra possible d'écrire du code portable dépendant de cette optimisation : http://open-std.org/JTC1/SC22/WG21/docs/papers/2015/p0135r0.html

Illustration détaillée de RVO

Ce qui suit découle d'une conversation que j'ai tenue avec Félix-Antoine Ouellet, brillant étudiant à la maîtrise à l'Université de Sherbrooke, et qui se demandait s'il était préférable d'écrire « return std::move(x); » ou « return x; » en pratique.

En pratique, « return x; » est la chose à faire. La raison est que recourir à std::move() force le mouvement, qui est typiquement efficace, mais moins que l'optimisation RVO que le compilateur peut (et, avec C++ 17, doit) parfois réaliser. Concrètement, tous les compilateurs pertinents appliquent déja RVO depuis longtemps, mais ce n'était pas imposé par le standard alors ça en faisait une optimisation qui brisait la règle du as if, car son impact sur la sémantique du code était observable.

À titre d'exemple, soit la classe Noisy suivante : ../Sujets/TrucsScouts/Noisy.html. Son rôle est, essentiellement, de faire du bruit. Avec cette classe, il devient possible d'observer le déroulement de la vie des objets dans un programme.

Ainsi, ce programme :

Noisy f(Noisy n) {
   Noisy m = n;
   return m;
}
int main() {
   Noisy n;
   n = f(n);
}

... affichera ceci :

Noisy::Noisy()
Noisy::Noisy(const Noisy&)
Noisy::Noisy(const Noisy&)
Noisy::~Noisy()
Noisy::operator=(Noisy&&)
Noisy::~Noisy()
Noisy::~Noisy()

...donc beaucoup d'action. Si on raffine pour obtenir ceci :

Noisy f(Noisy n) {
   return n;
}
int main() {
   Noisy n;
   n = f(n);
}

...on obtiendra cela :

Noisy::Noisy()
Noisy::Noisy(const Noisy&)
Noisy::Noisy(Noisy&&)
Noisy::~Noisy()
Noisy::operator=(Noisy&&)
Noisy::~Noisy()
Noisy::~Noisy()

...où une copie a été remplacée silencieusement par un mouvement (le return, en fait). On peut faire mieux :

Noisy f(Noisy n) {
   return n;
}
int main() {
   Noisy n;
   n = f(std::move(n));
}

...ce qui nous donne :

Noisy::Noisy()
Noisy::Noisy(Noisy&&)
Noisy::Noisy(Noisy&&)
Noisy::~Noisy()
Noisy::operator=(Noisy&&)
Noisy::~Noisy()
Noisy::~Noisy()

...où toutes les copies sont disparues. Ajouter un retour par mouvement ici ne donne rien :

Noisy f(Noisy n) {
   return std::move(n);
}
int main() {
   Noisy n;
   n = f(std::move(n));
}

...nous donnera encore :

Noisy::Noisy()
Noisy::Noisy(Noisy&&)
Noisy::Noisy(Noisy&&)
Noisy::~Noisy()
Noisy::operator=(Noisy&&)
Noisy::~Noisy()
Noisy::~Noisy()

Si on simplifie un peu pour obtenir ceci :

Noisy f(Noisy n) {
   return n;
}
int main() {
   Noisy n = f(Noisy{});
}

...on voit l'optimiseur s'amuser avec les variables anonymes et nous donner cela :

Noisy::Noisy()
Noisy::Noisy(Noisy&&)
Noisy::~Noisy()
Noisy::~Noisy()

...ce qui commence à être sympathique. D'ailleurs, on aurait simplement pu écrire ceci :

Noisy f(Noisy n) {
   return n;
}
int main() {
   Noisy n = f({});
}

...et voir encore cela, car l'appel à f() n'est pas ambigü :

Noisy::Noisy()
Noisy::Noisy(Noisy&&)
Noisy::~Noisy()
Noisy::~Noisy()

Pour s'amuser vraiment, nous pouvons aller jusqu'à :

Noisy f() {
   return{};
}
int main() {
   Noisy n = f();
}

...ce qui donnera :

Noisy::Noisy()
Noisy::~Noisy()

...et c'est là que l'on voit qu'il vaut mieux laisser le compilateur s'amuser. Ici, si nous avions une variable nommée et un mouvement explicite, nous perdrions au change. Ainsi, ceci :

Noisy f() {
   Noisy n;
   return std::move(n);
}
int main() {
   Noisy n = f();
}

...affichera cela :

Noisy::Noisy()
Noisy::Noisy(Noisy&&)
Noisy::~Noisy()
Noisy::~Noisy()

...ce qui est le mieux qu'il puisse faire dans ce cas. De manière amusante, ceci :

Noisy f() {
   Noisy n;
   return n;
}
int main() {
   Noisy n = f();
}

...donnera cela :

Noisy::Noisy()
Noisy::~Noisy()

... ce qui est plus rapide que la version avec un std::move() (on voit ici la variante NRVO, pour Named Return Value Optimization). En effet, le compilateur applique le mouvement implicitement quand c'est possible, et fait RVO (qui escamote carrément une temporaire) quand il le peut. Mieux vaut le laisser faire son travail.

Pour en savoir plus :

Dans le monde des jeux

Divers articles sur l'optimisation dans les jeux : http://www.tantalon.com/pete.htm

La version de STL que propose Electronic Arts, EASTL : http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html

Une bibliothèque de chaînes de caractères à haute performance : http://www.gamasutra.com/view/feature/1607/a_high_performance_low_level_.php

Rédiger du code pour les plateformes Next-Gen : http://www.gamasutra.com/features/20051220/thomason_01.shtml

Faire disparaître certains coûts du polymorphisme en réimplémentant partiellement cette fonctionnalité manuellement, selon Aras Pranckevičius en 2011 : http://altdevblogaday.com/2011/02/01/the-virtual-and-no-virtual/

Il semble que le recours aux langages de scripting dans un jeu, ça ait ses limites, du moins selon John Carmack en 2011 : http://www.codingthewheel.com/game-dev/john-carmack-script-interpreters-considered-harmful

Optimisation et Haskell

Optimisation et plateforme .NET

Bêtises à éviter :

Améliorer les performances d'un programme .NET : http://msdn.microsoft.com/en-us/library/ms998530.aspx

Discussion du compilateur juste à temps (JIT) de .NET : http://www.codeproject.com/KB/dotnet/JITOptimizations.aspx

Rédiger du code C# à haute performance :

Examen de diverses considérations d'optimisation avec C#, article du Code Project mais plutôt intéressant par Ben Watson en 2014 : http://www.codeproject.com/Articles/812678/Performance-Considerations-of-Class-Design-and-Gen

Accélérer l'exécution du code .NET, diapositives d'une présentation par Sasha Goldshtein en 2015 : https://www.dropbox.com/s/hugrj8nr6cvghvp/Making_NET_applications_faster.pptx?dl=0

Taille des objets et impact sur la Cache, article de Yan Cui en 2015 : http://theburningmonk.com/2015/07/smallest-net-ref-type-is-12-bytes-or-why-you-should-consider-using-value-types/

À propos des optimisations possibles sur des opérations associatives en C#, texte d'Eric Lippert en 2015 : http://ericlippert.com/2015/10/27/optimizing-associative-operations/

Optimisation et plateforme Java

Légendes urbaines en lien avec les seuils de performance en Java : http://www.ibm.com/developerworks/java/library/j-jtp04223.html

Optimiser le code Java :

Diverses études de cas : http://www.research.ibm.com/journal/sj39-1.html

Quel est le coût réel d'un appel de méthode sous Java? La réponse à cette question n'est pas simple du fait qu'un programme Java est intégré à un profileur qui en optimise les performances dynamiquement. Tout de même :

Réflexion sur le fossé sémantique entre les programmes tels que rédigés et leur performance à l'exécution : http://wiki.jvmlangsummit.com/MindTheSemanticGap

Le paquetage javax.cache de Java 7 : http://gregluck.com/blog/archives/2011/10/javax-cache-the-new-java-caching-standard/

Utiliser String, StringBuffer ou StringBuilder? Un texte de Mathew Bukowicz en 2012 : http://code-thrill.blogspot.ca/2012/08/stringbuilder-optimizations-demystified.html

Caractéristiques de « performance » des vecteurs persistants, selon Niklas L'orange en 2015 : http://hypirion.com/musings/persistent-vector-performance

Mesurer le temps d'exécution d'un programme Java :

Ce que l'on nomme Espace Analysis en Java est une technique d'optimisation permettant à un programme d'éliminer des objets qui n'ont pas d'impact visibles hors de leur contexte d'utilisation. En particulier, cette technique pourrait permettre à une méthode sollicitant des itérateurs d'escamoter certains coûts inhérents à leur implémentation :

Quel est le coût du chargement dynamique des classes par la JVM?

Quel est le coût du Boxing?

Écrire des programmes Java aussi rapides que leur équivalent C, mais qui sont de très vilains programmes Java? Une présentation de Charles Nutter en 2015 : http://fr.slideshare.net/CharlesNutter/fast-as-c-how-to-write-really-terrible-java

Optimisation dans d'autres langages

Optimisation en langage d'assemblage :

Optimiser du code brainfuck :

Optimiser le compilateur du langage D (un programme C++) :

Optimiser du code F# :

Optimiser du code Go :

Optimiser du code Lisp pour obtenir des performances analogues à celles de code C :

Comparatif de vitesse d'exécution entre C++, Go, Java et Scala, avant et après optimisations :

Écrire du code rapide avec Mathematica, par Jon McLoone en 2011 : http://blog.wolfram.com/2011/12/07/10-tips-for-writing-fast-mathematica-code/

Optimiser avec JavaScript :

Optimiser avec Nim :

Optimiser avec OCaml :

Optimiser avec Python :

Optimisation avec Ruby :

Optimisation avec Scala :

Optimiser avec SQL :

Optimisations sous diverses plateformes

Tirer le maximum d'une pile LAMP (Linux, Apache, MySQL, PHP) :

Optimisation et réseautique

Le problème du Bufferbloat, par lequel les communications TCP et UDP en viennent à ralentir :

Série d'articles par Larry Osterman, en 2006, sur l'optimisation du trafic réseau :

Optimiser le trafic sur un réseau grâce à Python, texte de Gergely Kalman en 2013 : http://www.toptal.com/python/how-i-made-porn-20x-more-efficient-with-python

Optimisations non portables

Comprendre le format Portable Executable (PE) de Windows :

Les directives #pragma de Visual Studio :

Optimiser les transferts de données sur un Pentium :

Optimiser en fonction du processeur Intel Atom :

Optimisations propres à Microsoft Windows :

La question des branchements :

Optimisations 64 bits

Sur ce sujet, voir aussi ces quelques liens.

Convention d'appel 64 bits sous Windows : http://msdn.microsoft.com/fr-fr/library/bb738063.aspx (l'article mère vers plusieurs autres liens intéressants, d'ailleurs).

Pour optimiser les programmes 64 bits :

Optimisations de sites Web

Rédiger de meilleures feuilles CSS :

Écrire de meilleurs greffons (de meilleurs plugins) :

Mieux comprendre le traitement réalisé par les fureteurs pour générer de meilleurs sites, un texte de Tali Garsiel et Paul Irish en 2011 : http://www.html5rocks.com/en/tutorials/internals/howbrowserswork/

Comprendre la performance côté client pour les applications Web, selon Tali Garsiel : http://taligarsiel.com/ClientSidePerformance.html

L'mpact de la géographie (en fait, des variations d'infrastructure à travers les pays et les régions) sur les performances. Texte intéressant qui montre certains aléas peut-être surprenants de la réalité concrète d'Internet, de par un accident résultant pourtant d'efforts sincères chez Youtube. Texte de Chris Zacharias en 2012 : http://blog.chriszacharias.com/page-weight-matters

L'impact de l'avènement de http 2.0, par Ilya Grigorik en 2013 : http://queue.acm.org/detail.cfm?id=2555617

Comment le processus d'édition d'une page Wiki a été fortement accéléré, selon Ori Livneh en 2014 : http://blog.wikimedia.org/2014/12/29/how-we-made-editing-wikipedia-twice-as-fast/

(beaucoup à ajouter...)

Algorithmes et techniques d'ordre général

Étude des manipulations de chaînes de caractères : http://research.microsoft.com/apps/pubs/default.aspx?id=70656

Optimisation par saturation : http://cseweb.ucsd.edu/~rtate/publications/eqsat/

Génération automatique d'optimiseurs : http://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf

Découvrir dynamiquement des opportunités d'optimisation ratées, texte de John Regehr en 2014 : http://blog.regehr.org/archives/1146

Un outil pour découvrir des algorithmes capables de résoudre de problèmes difficiles : http://critticall.com/

Optimisation dynamique :

Le Whole Program Optimization, qui refait des optimisations au moment de l'édition des liens (donne de meilleurs résultats sur du code pris en charge que sur du code indigène, mais compile vraiment plus longtemps... Ou, en fait, qui compile plus vite mais prolonge considérablement l'édition des liens) :

Dossier connexe, le Profile-Guided Optimization :

Optimiser le traitement par lots : http://codeascraft.etsy.com/2010/07/09/batch-processing-millions-of-images/

Ce que toute programmeuse et tout programmeur devrait savoir à propos des optimisations générées par les compilateurs, selon Hadi Brais en 2015 : https://msdn.microsoft.com/en-us/magazine/dn904673.aspx

Cas d'espèces

Étude de cas chez une firme qui prétend avoir obtenu une accélération d'un facteur de de son algorithme de reconnaissance de visages : http://lbrandy.com/blog/2008/10/how-we-made-our-face-recognizer-25-times-faster/

Optimiser le démarrage d'un fureteur comme Firefox : http://blog.mozilla.com/tglek/2010/05/27/startup-backward-constructors/

À propos de grep :

L'optimisation de l'API de Netflix, décrite par Jeevak Kasarkod en 2013 : http://www.infoq.com/news/2013/02/netflix-api-optimization

Textes de Bruce Dawson :

Textes d'Eli Bendersky :

Accélérer la conversion d'un entier en chaîne de caractères, par Leandro Pereira en 2014 : http://tia.mat.br/blog/html/2014/06/23/integer_to_string_conversion.html

Les conséquences, parfois surprenantes, de l'initialisation à zéro, un article de Xi Yang, Stephen M. Blackburn, Daniel Frampton, Jennifer B. Sartor et Kathryn S. McKinley en 2011 : http://users.cecs.anu.edu.au/~steveb/downloads/pdf/zero-oopsla-2011.pdf

Prudence par contre, car comme le rapporte Raymond Chen en 2016, les temps changent et initialiser une page à zéro peut aussi en accélérer le chargement : https://blogs.msdn.microsoft.com/oldnewthing/20161109-00/?p=94675

Les périls de l'optimisation du traitement de chaînes de caractères, selon Michael Richman en 2014 : http://word.bitly.com/post/74069870671/optimizing-text-processing

En 2015, Daniel J. Bernstein « prédit » la mort des compilateurs optimisants, du moins ceux auxquels nous avons été habitués : http://cr.yp.to/talks/2015.04.16/slides-djb-20150416-a4.pdf

Pour optimiser l'expérience sur Netflix, l'une des meilleures approches est de ne pas viser une solution homogène, allant jusqu'à configurer les paramètres de transmission « un titre à la fois ». Texte de Anne Aaron, Zhi Li, Megha Manohara, Jan De Cock et David Ronca en 2015 : http://techblog.netflix.com/2015/12/per-title-encode-optimization.html

Optimisation dans les compilateurs

Comparatif de la capacité qu'ont divers compilateurs de générer du code optimisé, par Felix von Leitner en 2009 : http://www.linux-kongress.org/2009/slides/compiler_survey_felix_von_leitner.pdf

Votre compilateur perviendra-t-il à optimiser ces extraits de code? http://ridiculousfish.com/blog/archives/2010/07/23/will-it-optimize/

Comparatif des moteurs d'optimisation de gcc et de Clang : http://vmakarov.fedorapeople.org/spec/

Le futur des optimisations par le compilateur : http://blog.regehr.org/archives/247

Épargner de l'espace pour les chaînes de caractères brutes à l'aide de Visual Studio (texte du Code Project) : http://www.codeproject.com/Articles/345887/Using-the-Visual-C-Cplusplus-Compiler-1

Les super-optimiseurs stochastiques, par John Regehr en 2013 : http://blog.regehr.org/archives/923

Peut-on raffiner les optimisations produites par un compilateur en examinant mécaniquement le code généré? Semble que oui, si on se base sur ce texte de John Regehr en 2014 : http://blog.regehr.org/archives/1192

Optimisations vectorielles pour x86 avec gcc 5.0, rapportées par Evgeny Stupachenko en 2014 : https://software.intel.com/en-us/blogs/2014/11/24/what-is-new-for-x86-in-upcoming-gcc-50

Ce que tout programmeurs devrait savoir quant aux optimisations réalisées par un compilateur, série d'articles par Hadi Brais en 2015 :

Comprendre comment gcc s'y prend pour réaliser (ou pas) certaines optimisations, par Krister Walfridsson en 2017 : https://kristerw.blogspot.ca/2017/01/gcc-code-generation-for-c-weekly-ep-43.html

Autres types d'optimisations

Il existe évidemment d'autres manières d'optimiser que les classiques cas du temps d'exécution et des ressources requises. Par exemple :


Valid XHTML 1.0 Transitional

CSS Valide !