Antémémoire (la Cache)

En bref :

• L'antémémoire est une zone de mémoire à proximité du processeur, et dans laquelle les accès sont beaucoup plus rapides que ceux réalisés dans la mémoire vive
• Les données dans une antémémoire sont insérées par bloc, de la taille d'une Cache Line. Cette taille varie selon les architectures matérielles
• Quand une donnée doit être manipulée par le processeur, elle est amenée dans l'antémémoire (avec ses voisines), puis circule de l'antémémoire au processeur et inversement
• Conséquemment, l'idée est de placer à proximité les unes des autres les données qui seront accédées successivement dans un même thread, et éloigner les unes des autres des données qui seront accédées par des threads distincts, du moins si au moins l'une d'elles est sujette à être accédée en écriture
• En effet, les données dans l'antémémoire doivent être à jour. Si un thread modifie une donnée dans l'antémémoire d'un coeur, tous les autres coeurs qui ont dans leur antémémoire une copie de cette donnée doivent alors rafraîchir le contenu de leur propre antémémoire, ce qui entraîne une dégradation de performance (du Cache Trashing)

Un algorithme est Cache-aware s'il est écrit pour tenir compte de la Cache dans le détail. Ceci peut signifier que l'algorithme requiert une part de calibration en fonction des paramètres de la Cache (taille d'une Cache Line, par exemple). Typiquement, l'algorithme Cache-Oblivious sera plus performant que la version naïve du même algorithme, alors que la version Cache-aware sera encore plus rapide que la version Cache-Oblivious, mais perdra en portabilité en s'associant de près à des détails architecturaux moins transférables.

Certaines pessimisations peuvent résulter d'un mauvais usage de l'antémémoire, en particulier le faux partage.

Lectures complémentaires

Quelques liens supplémentaires pour enrichir le propos.

Généralités

Quelques sites Wiki :

• Sur les antémémoires en général : http://en.wikipedia.org/wiki/Cache
• Sur l'antémémoire du processeur : http://en.wikipedia.org/wiki/CPU_cache
• Sur l'optimisation Copy-on-Write : http://en.wikipedia.org/wiki/Copy-on-write

Divers articles sur le sujet :

• Texte complémentaire par Mike Ash en 2013 : pourquoi les registres et les antémémoires sont-ils si rapides d'accès alors que l'accès à la mémoire vive est si lent? http://www.mikeash.com/pyblog/friday-qa-2013-10-11-why-registers-are-fast-and-ram-is-slow.html
• http://ralyx.inria.fr/2005/Raweb/compsys/uid0.html
• http://digbib.ubka.uni-karlsruhe.de/eva/ira/1998/16&search=/ira/1998/16
• http://www.computer.org/portal/web/csdl/doi/10.1109/40.946678
• http://portal.acm.org/citation.cfm?doid=362422.362438
• Réduire la latence des accès mémoire : http://www.tinker.ncsu.edu/symposia/mpi01.pdf
• http://lbrandy.com/blog/2009/07/computational-performance-a-beginners-case-study/
• Un texte de 2012 qui prétend que la Cache Line est l'équivalent contemporain des registres à une époque pas si lointaine : http://simonask.tumblr.com/post/30645840195/cache-lines-are-the-new-registers
• À propos de la difficulté de gérer l'invalidation d'une Cache, par Vincent Sanders en 2014 : http://vincentsanders.blogspot.co.uk/2014/02/there-are-only-two-hard-things-in.html
• Ce qu'il faut savoir sur l'antémémoire du processeur, selon Evgeny Budilovksy en 2014 : http://meta-x86.blogspot.co.il/2014/06/cpu-cache-essentials.html
• Comprendre le fonctionnement de la Cache Coherence, texte de Fabian Giesenen en 2014 : http://fgiesen.wordpress.com/2014/07/07/cache-coherency/
• L'impact de divers algorithmes pour déterminer ce qui sortira de la Cache quand on aura besoin d'y faire un peu de place, par Dan Luu en 2014 : http://danluu.com/2choices-eviction/
• Comment l'accès à la mémoire influence la vitesse d'exécution, une étude de Matt Kline en 2015 : http://bitbashing.io/memory-performance.html
• Le Cache Partitioning sur processeur Haswell, expliqué par Dan Luu en 2015 : http://danluu.com/intel-cat/
• Ce que toute programmeuse et tout programmeur devrait savoir :
  • à propos de la mémoire : http://lwn.net/Articles/250967/ (version plus complète : http://people.redhat.com/drepper/cpumemory.pdf)
  • à propos de ce qu'on nomme en anglais le Hardware Prefetching, étape par laquelle les données et instructions sont rapprochées du processeur avant d'être utilisées : http://www.futurechips.org/chip-design-for-all/prefetching.html
• Le Caching et le Web :
  • comment optimiser les performances d'un site Web, un texte de 2011 : http://betterexplained.com/articles/how-to-optimize-your-site-with-http-caching/
  • en 2012, Jeff Knupp parle d'optimiser Django en tirant profit du Caching : http://www.jeffknupp.com/blog/2012/02/24/django-memcached-optimizing-django-through-caching/
  • en 2012, Steve Souders explore la question sous divers angles : http://www.stevesouders.com/blog/2012/03/22/cache-them-if-you-can/
  • en 2012, Martin Kleppmann suggère de repenser notre manière d'aborder les antémémoires dans nos applications Web : http://martin.kleppmann.com/2012/10/01/rethinking-caching-in-web-apps.html
  • conserver une Cache d'authentification « amicale », proposition de Nikolay Nemshilov en 2012 : http://theosom.com/p/Qong
• Comprendre la cohérence de la Cache, texte de 2014 par Fabian Giesen : https://fgiesen.wordpress.com/2014/07/07/cache-coherency/
• Selon Carlos Bueno en 2014, la Cache joue aujourd'hui le rôle que jouait la RAM hier : http://blog.memsql.com/cache-is-the-new-ram/
• Pourquoi se préoccuper de la Cache? Un texte d'Ivo Sklenar en 2015 : https://ivosklenar.net/Blog/Post/19
• Série de textes par Emil Ernerfeldt en 2014, soutenant la « thèse » que l'accès à une donnée en mémoire vive soit de complexité$O(\sqrt{n})$ :
  • http://www.ilikebigbits.com/blog/2014/4/21/the-myth-of-ram-part-i
  • http://www.ilikebigbits.com/blog/2014/4/28/the-myth-of-ram-part-ii
  • http://www.ilikebigbits.com/blog/2014/4/29/the-myth-of-ram-part-iii
• En 2015, James Hague met un bémol sur la quête de l'optimisation absolue des accès à la Cache : http://prog21.dadgum.com/204.html
• Antémémoire et réorganisation des données de programmes Lisp, article de Richard Fateman en 2003 : http://www.cs.berkeley.edu/~fateman/papers/cachelisp.pdf
• Selon Carlos Bueno en 2014, la Cache est aujourd'hui ce que la RAM était à une autre époque : http://carlos.bueno.org/2014/11/cache.html
• Comparatif d'approches à l'utilisation de la mémoire contiguë selon les plateformes, par Karl Rupp en 2016 : https://www.karlrupp.net/2016/02/strided-memory-access-on-cpus-gpus-and-mic/
• Tour d'horizon des Caches d'un processeur, par Lukas Waymann en 2017 : https://meribold.github.io/2017/10/20/survey-of-cpu-caches/

Niveaux d'antémémoire

• Survol succinct des antémémoires sur x86 : http://www.whdload.de/docs/en/cache.html
• Pour une illustration animée comparant les temps d'accès à un registre, à la Cache L1, à la Cache L2 et à la mémoire principale, voir : http://www.overbyte.com.au/misc/Lesson3/CacheFun.html
• Pour une explication des raisons pour lesquelles un ordinateur comprend plusieurs niveaux de Cache, voir ce texte de 2016 par Fabian Giesen : https://fgiesen.wordpress.com/2016/08/07/why-do-cpus-have-multiple-cache-levels/

Outils

• L'appel système vmsplice() sous Linux : http://kerneltrap.org/node/6506
• Le produit memcached : http://en.wikipedia.org/wiki/Memcached
• http://varnish-cache.org/wiki/ArchitectNotes
• Le paquetage javax.cache de Java 7 : http://gregluck.com/blog/archives/2011/10/javax-cache-the-new-java-caching-standard/

Profiter de l'antémémoire

• Taille d'un programme, taille de l'antémémoire et performance : http://discuss.joelonsoftware.com/default.asp?joel.3.58627.5
• Optimiser du code pour lequel l'essentiel du travail se passe en mémoire : http://docs.cray.com/books/S-2315-50/html-S-2315-50/z1051208423brbethke.html
• Impact de la taille des tableaux sur la « performance » : http://www.idiom.com/~zilla/Computer/cachekiller.html
• http://www.linuxshowcase.org/2000/2000papers/papers/sears/sears_html/
• http://www.tophatstuff.co.uk/?p=119
• L'impact des modalités de parcours de la mémoire, avec illustrations en Java, par Martin Thompson en 2012 : http://mechanical-sympathy.blogspot.co.uk/2012/08/memory-access-patterns-are-important.html
• Comprendre ce que signifie un Cache Flush, et surtout ce que cela ne signifie pas, par Martin Thompson en 2013 : http://mechanical-sympathy.blogspot.co.uk/2013/02/cpu-cache-flushing-fallacy.html
• Réorganiser les structures de données, un texte de Randy Gaul en 2014 : http://www.randygaul.net/2014/06/25/cache-aware-components/
• Textes d'Austin G. Walters en 2014 :
  • utiliser OpenMP correctement pour tenir compte de l'antémémoire : http://austingwalters.com/the-cache-and-multithreading/
  • texte d'ordre général sur les saines pratiques en ce sens : http://austingwalters.com/cache-optimizing/
• Des algorithmes conscients de l'antémémoire : http://cs.gmu.edu/~menasce/cs571/Spring2001/BovetSlides.pdf
• Des diapositives électroniques de Scott Meyers : http://aristeia.com/TalkNotes/PDXCodeCamp2010.pdf
• Profiter du Cache Prefetching par programmation, selon Katarzyna Macias en 2015 : http://katecpp.github.io/cache-prefetching/
• Visualiser les impacts de diverses approches sur l'antémémoire : http://igoro.com/archive/gallery-of-processor-cache-effects/
• Pour profiter de l'antémémoire, mieux vaut privilégier les conteneurs dont les éléments sont contigus en mémoire (en C++, préférez std::vector) :
  • texte de Jon Kalb en 2013 sur les vertus de tels conteneurs : http://www.slashslash.info/2013/10/ode-to-a-flat-set/
  • en C++, std::vector tend même à battre en vitesse les tableaux bruts (s'ils sont tous deux bien utilisés, évidemment) : ../Sources/comparatif_vecteur_tableau.html
  • bien utiliser un vecteur, texte de Thomas Young en 2013 : http://upcoder.com/1/using-stl-vectors/
  • bien utiliser un vecteur de vecteurs, texte de Thomas Young en 2013 : http://upcoder.com/2/efficient-vectors-of-vectors/
• La recherche dichotomique (Binary Search) est parfois un cas pathologique pour les antémémoires. À ce sujet, une étude assez riche de Paul Khuong en 2012 : http://www.pvk.ca/Blog/2012/07/30/binary-search-is-a-pathological-case-for-caches/
• Présentation assez claire d'Eric Brumer, en 2013, sur l'impact de l'accès à la mémoire sur la vitesse d'exécution : http://channel9.msdn.com/Events/Build/2013/4-329
• Tenir compte de l'antémémoire rapporte, comme en fait état Naftali Harris en 2013 qui explique avoir obtenu gain imposant en vitesse d'exécution par l'ajout d'une seule ligne de code : http://www.naftaliharris.com/blog/2x-speedup-with-one-line-of-code/
• Caching et « mémo-isation » en programmation :
  • un exemple de « mémo-isation » reposant sur des templates variadiques et de la métaprogrammation, par Sumant Tambe en 2012 (attention, article intéressant mais costaud) : http://cpptruths.blogspot.ca/2012/01/general-purpose-automatic-memoization.html
  • distinguer « mémo-isation » et programmation dynamique, un texte de Shriram Krishnamurthi en 2012 : http://blog.racket-lang.org/2012/08/dynamic-programming-versus-memoization.html
  • appliquer une variante de la « mémo-isation » pour accélérer drastiquement l'exécution du Jeu de la vie, texte de 2006 par Tomas G. Rokicki : http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478
  • la « mémo-isation » pour les nuls, par Bart de Smets en 2008 : http://community.bartdesmet.net/blogs/bart/archive/2008/10/21/memoization-for-dummies.aspx
  • implémenter une « mémo-isation » automatique pour des expressions λ, par Arjun Bijanki en 2008 : http://blogs.msdn.com/b/vcblog/archive/2008/11/18/stupid-lambda-tricks.aspx
  • programmation dynamique paresseuse, par Tikhon Jelvis en 2014 : http://jelv.is/blog/Lazy-Dynamic-Programming/
• En 2014, Igor Ostrovsky décrit, par des exemples en C#, l'impact de la Cache sur le temps d'exécution de certaines répétitives : http://igoro.com/archive/gallery-of-processor-cache-effects/
• Obtenir la taille de la Cache en C++ et en D à partir d'un identifiant de processeur (CPU ID), par Melker Litsgård en 2016 : http://blog.melkerlitsgard.se/2016/05/12/cache-sizes-with-cpuid/
• Les approches Struct of Arrays (SoA) et Array of Structs (AoS) :
  • texte de 2016 qui présente la technique et explique quand elle peut être utile : https://maikklein.github.io/post/soa-d/
• Comprendre le Caching avec Postgres, par Madusudanan.B.N en 2016 : https://madusudanan.com/blog/understanding-postgres-caching-in-depth/
• Partager efficacement une Cache, un texte d'Adrian Colyer en 2016 : https://blog.acolyer.org/2016/03/23/fairride-near-optimal-fair-cache-sharing/
• Les avantages d'une Cache immuable, expliqués par Patrick McManus en 2016 : https://bitsup.blogspot.ca/2016/05/cache-control-immutable.html

Risques et périls

• Les périls de l'antémémoire : http://www.ece.cmu.edu/~koopman/pc_cache/espcache.html
• Dans un jeu, les coûts d'un design qui ne tiendrait pas suffisamment compte de l'antémémoire :
  • présentation de Tony Albrecht en 2009, qui critique l'approche orientée objet, mais manque un peu sa cible en confondant l'approche avec certaines manières de l'appliqer (manières inappropriées aujourd'hui). Cependant, le message important demeure, soit celui à l'effet duquel l'organisation en mémoire des données n'est pas un détail... Au contraire, il s'agit de quelque chose de crucial : http://research.scee.net/files/presentations/gcapaustralia09/Pitfalls_of_Object_Oriented_Programming_GCAP_09.pdf
  • http://gamesfromwithin.com/data-oriented-design
  • http://igoro.com/archive/gallery-of-processor-cache-effects/
  • texte d'Andy Thomason en 2005 : http://www.gamasutra.com/view/feature/2490/writing_efficient_game_code_for_.php
  • texte sur les péchés de programmation en jeu vidéo (l'un d'eux est très à propos...), écrit en 2011 par quelques auteurs : http://www.gamasutra.com/view/feature/6426/sponsored_feature_programming_.php
• À propos du faux partage, texte de Nitsan Wakart en 2014 : http://psy-lob-saw.blogspot.com/2014/06/notes-on-false-sharing.html
• Si votre antémémoire logicielle repose sur les hash codes, alors soyez prudents, car il se peut qu'elle ne fonctionne pas réellement, comme le signale Timothy Alper dans ce texte de 2014 à propos d'une implémentation Java : http://blog.coverity.com/2014/01/29/cache-cache/
• Dans cet intéressant texte de 2022, Bruce Dawson relate l'impact d'une différence de distance entre un coeur et une Cache L2 sur la latence d'accès à la mémoire : https://randomascii.wordpress.com/2022/01/12/5-5-mm-in-1-25-nanoseconds/