Le même total, bien plus lentement
Chaque nuit, une chaîne de supermarchés additionne un grand tableau de ventes. Un développeur inverse les deux boucles pour parcourir les colonnes au lieu des lignes.
Le total reste juste, au centime près. Mais le calcul prend maintenant plusieurs fois plus de temps. Le travail n’a pas changé, seulement l’ordre. La raison s’appelle le cache.
À la fin de cette leçon
Remarque
Je peux expliquer pourquoi un cache rend la mémoire rapide.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Hiérarchie mémoire | des mémoires rangées de la petite et rapide à la grande et lente | |
| Cache | une petite mémoire rapide qui garde des copies des données récentes | |
| Ligne de cache | le bloc d’octets que le cache copie d’un coup | 64 octets |
| Succès | la donnée voulue est déjà dans le cache | |
| Défaut de cache | la donnée doit venir d’une mémoire plus lente | |
| Localité | un programme réutilise ses données et celles qui sont voisines |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
La mémoire est faite d’étages
Un processeur fait une addition en bien moins d’une nanoseconde. Lire la mémoire principale prend environ cent fois plus.
Un ordinateur a donc une hiérarchie mémoire. Près du processeur se trouvent de petits caches rapides : L1, puis L2, souvent L3. Derrière eux vient la mémoire principale, puis le disque. Chaque étage est plus grand et plus lent que le précédent.
Exemple travaillé : un portable de bureau
| Étage | Taille habituelle | Temps de lecture approché |
|---|---|---|
| Registres | 32 de 8 octets chacun | Moins d’une nanoseconde |
| Cache L1 | 32 à 64 Ko | Environ 1 nanoseconde |
| Cache L2 | Quelques centaines de Ko à quelques Mo | Quelques nanosecondes |
| Cache L3 | Quelques Mo à quelques dizaines de Mo | 10 à 20 nanosecondes |
| Mémoire principale | Plusieurs Go | Environ 100 nanosecondes |
| SSD | Des centaines de Go | Des dizaines de milliers de nanosecondes |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Aller dans le dossier d’architecture
cd ~/archAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Quelle taille fait une ligne ici ?
getconf LEVEL1_DCACHE_LINESIZEAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Un défaut apporte une ligne entière
Un cache ne copie jamais un seul octet. Lors d’un défaut, il copie toute une ligne de cache, en général 64 octets, depuis l’étage du dessous.
C’est rentable grâce à la localité. Un programme lit bientôt les données voisines de celle qu’il vient de lire : c’est la localité spatiale. Il relit aussi les mêmes données : c’est la localité temporelle. Dans les deux cas, la lecture suivante est un succès.
Pourquoi ligne par ligne gagne dans loop.c
loop.c garde un tableau de 4096 lignes de 4096 int. Un int fait 4 octets : une ligne du tableau fait 16384 octets, et une ligne de cache de 64 octets tient 16 nombres.
Ligne par ligne, un défaut apporte les 16 nombres suivants : 15 lectures sur 16 sont des succès. Colonne par colonne, chaque lecture est une ligne du tableau plus loin, dans une autre ligne de cache. Quand la boucle y revient, cette ligne est déjà partie.
La taille du tableau et d’une ligne
python3 -c "print(4096 * 4096 * 4 // 1024 // 1024, 4096 * 4 // 64)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Construire le programme loop du labo
gcc -O2 -o loop loop.cAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Minuter les deux ordres
./loopAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Erreur fréquente
Attention
Beaucoup pensent que la boucle la plus lente fait plus de travail. C’est faux : les deux additionnent les mêmes 16777216 nombres et affichent la même somme. La différence, c’est le temps passé à attendre la mémoire. Quand un code est lent, comptez les défauts de cache autant que les instructions.
Où va une ligne en correspondance directe
Dans un cache à correspondance directe, chaque adresse n’a qu’une seule place possible. On découpe l’adresse en trois parties.
Le déplacement est l’adresse modulo la taille de ligne : quel octet dans la ligne. En divisant par la taille de ligne, on obtient le numéro de bloc. L’index est ce numéro modulo le nombre de lignes : quelle place. L’étiquette est le reste : quel bloc occupe cette place.
Exemple travaillé : 4 lignes de 16 octets
| Adresse | Bloc | Index | Étiquette | Résultat |
|---|---|---|---|---|
| 8 | 0 | 0 | 0 | Défaut : place 0 vide |
| 12 | 0 | 0 | 0 | Succès |
| 40 | 2 | 2 | 0 | Défaut : place 2 vide |
| 72 | 4 | 0 | 1 | Défaut : remplace le bloc 0 |
| 8 | 0 | 0 | 0 | Défaut : le bloc 0 a été remplacé |
| 44 | 2 | 2 | 0 | Succès |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Découper 0x2a7c pour 16 lignes de 64 octets
python3 -c "print(0x2a7c % 64, 0x2a7c // 64 % 16, 0x2a7c // 1024)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Pour aller plus loin : un tableau plus petit
Faites une copie de loop.c avec un tableau seize fois plus petit en tapant sed 's/4096/1024/' loop.c > petit.c. Construisez-la avec gcc -O2 -o petit petit.c et lancez ./petit plusieurs fois.
Avant de lancer, prévoyez la somme. Comparez ensuite les deux ordres avec ceux de ./loop. Servez-vous de votre simulateur pour expliquer ce que vous voyez.