La hiérarchie mémoire et les temps de latence

Un processeur additionne deux nombres en une fraction de nanoseconde, mais aller chercher un nombre absent des caches peut prendre 80 ns. Ce cours transforme ces temps de latence en un seul chiffre, le coût moyen d'un accès mémoire, et montre quel niveau de mémoire dévore votre temps.

Un programme de trading passe l'essentiel de sa vie à attendre des données : un prix, un ordre, une ligne de table. Le calcul sur ces données est presque gratuit, mais elles doivent d'abord voyager de la mémoire au processeur, et plus elles sont loin, plus c'est long. Pensez à un bureau, une étagère, l'étage d'une bibliothèque et un entrepôt à l'autre bout de la ville. Les quelques feuilles sur le bureau sont instantanées, l'étagère prend quelques secondes, la bibliothèque une minute et l'entrepôt un après-midi. Les ordinateurs copient les données les plus utilisées dans de petites mémoires rapides à côté du processeur, appelées caches, pour que la plupart des demandes soient servies sur le bureau.

Un cœur de serveur typique a trois caches devant la mémoire principale. Nous les appelons L1, L2 et L3, et la mémoire principale RAM. Une demande servie par un cache est un succès ; une demande qui doit passer au niveau suivant est un défaut. Le tableau ci-dessous met les quatre latences côte à côte.

LATENCY_NS = {"L1": 1.0, "L2": 4.0, "L3": 15.0, "RAM": 80.0}for level, ns in LATENCY_NS.items():    print(level, ns, "ns", ns / LATENCY_NS["L1"], "x L1")

L1 1.0 ns 1.0 x L1
L2 4.0 ns 4.0 x L1
L3 15.0 ns 15.0 x L1
RAM 80.0 ns 80.0 x L1

Chaque niveau est plusieurs fois plus lent que celui du dessus, et la RAM est 80 fois plus lente que L1. Toute cette compétence consiste à faire en sorte que la plupart des accès soient servis près du sommet.

Un accès commence en L1. Si la valeur y est, l'accès coûte la latence de L1 et c'est fini. Sinon, le processeur interroge L2, puis L3, puis la RAM, qui a toujours la valeur. Chaque niveau interrogé coûte du temps, qu'il réussisse ou non : un accès trouvé en L3 a donc payé L1, L2 et L3.

1. 1
   Interroger L1Payez 1 ns. Un succès termine l'accès.
2. 2
   En cas de défaut, interroger L2Payez 4 ns de plus. Un succès termine l'accès.
3. 3
   En cas de défaut, interroger L3Payez 15 ns de plus. Un succès termine l'accès.
4. 4
   En cas de défaut, aller en RAMPayez 80 ns de plus. La RAM a toujours la valeur.

LATENCY_NS = {"L1": 1.0, "L2": 4.0, "L3": 15.0, "RAM": 80.0}cost_found_in_l3 = LATENCY_NS["L1"] + LATENCY_NS["L2"] + LATENCY_NS["L3"]print(cost_found_in_l3, "ns")

20.0 ns

Un accès servi par L3 coûte 20 ns, pas 15 : les 1 ns et 4 ns dépensées pour les deux défauts précédents font partie de la note.

Aucun accès n'est typique, on demande donc la moyenne sur de nombreux accès. Pondérez le coût de chaque chemin par sa fréquence. Chaque accès paie la latence de L1 ; seule la part qui rate L1 paie L2 ; seule la part qui rate les deux paie L3 ; et ainsi de suite. Écrit en une expression, avec des parenthèses qui s'emboîtent comme les niveaux :

C'est le temps d'accès mémoire moyen. Lisez les parenthèses de l'intérieur vers l'extérieur : la plus intérieure est ce que coûte un défaut en L3, la suivante ajoute la visite de L3, et ainsi de suite jusqu'à la visite de L1 que tout accès paie.

LATENCY_NS = {"L1": 1.0, "L2": 4.0, "L3": 15.0, "RAM": 80.0}h1, h2, h3 = 0.9, 0.8, 0.7t = LATENCY_NSamat = t["L1"] + (1 - h1) * (t["L2"] + (1 - h2) * (t["L3"] + (1 - h3) * t["RAM"]))1print(round(amat, 2), "ns")

2.18 ns

1. 11 - h est la part des accès qui échouent, donc chaque parenthèse est multipliée par la part qui arrive jusque-là.

Avec 90 % des accès qui réussissent en L1, la moyenne reste de 2,18 ns, plus du double de la latence de L1. Les quelques accès qui vont en profondeur coûtent si cher qu'ils tirent la moyenne. C'est pourquoi un taux de succès qui paraît excellent peut cacher un programme lent.

Deux questions se ressemblent mais ont des réponses différentes. Quel niveau répond aux accès ? Et quel niveau prend le temps ? La première compte des accès, la seconde compte l'attente. Un niveau est atteint par une part des accès et chaque visite coûte sa latence : un niveau rarement atteint mais lent peut donc dominer l'attente.

h1, h2, h3 = 0.9, 0.8, 0.7served = [h1, (1 - h1) * h2, (1 - h1) * (1 - h2) * h3, (1 - h1) * (1 - h2) * (1 - h3)]reach = [1.0, 1 - h1, (1 - h1) * (1 - h2), (1 - h1) * (1 - h2) * (1 - h3)]1cost = [r * ns for r, ns in zip(reach, [1.0, 4.0, 15.0, 80.0])]2print([round(x, 3) for x in served])print([round(c / sum(cost), 3) for c in cost])

[0.9, 0.08, 0.014, 0.006]
[0.459, 0.183, 0.138, 0.22]

1. 1reach est la part des accès qui visitent chaque niveau : tous visitent L1.
2. 2sum(cost) est le temps d'accès moyen : les mêmes 2,18 ns que précédemment.

La RAM ne répond qu'à 0,6 % des accès mais représente 22 % du temps d'attente, tandis que L1 répond à 90 % d'entre eux et prend 46 % du temps. C'est le fait clé derrière chaque optimisation de cette compétence : ne comptez pas les accès, comptez où va le temps.

Quelle importance cela a-t-il pour une vraie table ? La table des barres quotidiennes de SPY du labo a 5 405 lignes et cinq colonnes (ouverture, plus haut, plus bas, clôture, volume), soit 27 025 valeurs. Lisez chaque valeur une fois dans trois conditions : caches chauds où presque tout réussit, caches tièdes, et caches froids où la moitié des accès échouent à chaque niveau.

Le labo transforme ce cours en six petites fonctions, chacune construite sur les précédentes, et se termine par le chiffrage de la lecture de la vraie table SPY. Les voici avec la question à laquelle chacune répond.

• Fonction · questionS'appuie sur
• average_access_time(hit_rates)Combien coûte un accès en moyenne ?La table des latences
• slowdown(hit_rates)Combien de fois plus lent que réussir toujours en L1 ?average_access_time
• levels_served(hit_rates)Quel niveau répond aux accès ?Taux de succès locaux
• time_shares(hit_rates)Quel niveau prend le temps ?average_access_time
• scan_time_us(n_accesses, hit_rates)Combien de temps prennent n accès ?average_access_time
• study(bars)Que coûte la lecture de toute la table SPY ?scan_time_ustime_shares

Sujet suivant : ce cours a pris les taux de succès comme donnés. Dans Lignes de cache et localité spatiale, vous construisez le cache qui les produit et découvrez pourquoi lire une valeur voisine de celle qu'on vient de lire est presque gratuit.