Succès de cache et échec de cache
Lorsque le CPU a besoin de données, il cherche d'abord dans le cache. Si elles sont trouvées, tout va bien — mais que se passe-t-il si elles ne le sont pas ?
Cette leçon vous aide à comprendre la mécanique essentielle du fonctionnement des caches, et le principe clé qui rend les caches efficaces—Principe de localité。
Analogie quotidienne : le bureau dans une bibliothèque
Vous écrivez un article dans la bibliothèque. Au maximum 4 livres peuvent tenir sur votre bureau—c'est votreCache, sa capacité est petite mais à portée de main.
Lorsque vous avez besoin d'un livre, vérifiez d'abord s'il est sur le bureau :
- Sur la table (succès de cache): ouvrez-le et utilisez-le, aucune attente.
- Pas sur la table (échec de cache): levez-vous et cherchez dans l'étagère, rapportez-le et posez-le sur le bureau. Si le bureau est plein, vous devez remettre sur l'étagère le livre qui n'a pas été touché depuis le plus longtemps.
Cette règle simple est exactement l'essence d'un système de cache informatique—« Garder ce qui est récemment utilisé, évincer ce qui est rarement utilisé »。
Pour aller plus loin, vous constaterez ceci : lorsque vous écrivez un article, vous ne feuilletez pas au hasard des livres sans rapport. Sur une certaine période, vous consultez de manière répétée le même ensemble de documents de référence. Parmi ces milliers d'étagères dans la bibliothèque, celles que vous avez réellement touchées ne sont peut-être que vingt ou trente. C'estPrincipe de localitéEn action.
Concept clé : succès et défaut de cache
Termes de base
| Terme | Anglais | Signification |
|---|---|---|
| Succès de cache | Succès de cache | Les données demandées par le CPU se trouvent directement dans le cache et sont utilisées directement |
| Défaut de cache | Défaut de cache | Les données demandées par le CPU ne se trouvent pas dans le cache et doivent être chargées depuis le niveau de stockage suivant (plus lent) |
| taux de succès | Taux de succès | Nombre de succès / accès totaux, plus il est élevé, mieux c'est (idéalement proche de 100%) |
| Pénalité de défaut | Pénalité de défaut | Le temps supplémentaire passé à charger les données depuis le niveau suivant après un défaut |
| Temps de succès | Temps de succès | Temps nécessaire pour lire les données lorsque le cache a un succès |
Un exemple simple
, arr
| Étapes | Adresse d'accès | État du cache (avant accès) | Résultat | Raison |
|---|---|---|---|---|
| 1 | 10 | [] | défaut | Le cache est vide, l'adresse 10 n'y est pas |
| 2 | 20 | [10] | défaut | L'adresse 20 n'est pas dans le cache |
| 3 | 10 | [10, 20] | succès | L'adresse 10 est dans le cache ! (localité temporelle) |
| 4 | 30 | [10, 20] | défaut | L'adresse 30 n'est pas dans le cache |
| 5 | 10 | [10, 20, 30] | succès | L'adresse 10 est de nouveau un succès |
2 succès sur 5 accès, taux de succès = 40%. Pas élevé, mais cela démontre déjà le principe de la mise en cache.
Pourquoi les caches fonctionnent : le principe de localité
Si un programme accède à la mémoire de manière complètement aléatoire, le cache est presque inutile — les données sont chargées pour ne servir à rien tout de suite.
Mais les vrais programmes ne se comportent pas de manière aléatoire. Ils font preuve d'une forteLocalité, et c'est précisément la raison fondamentale pour laquelle les caches sont efficaces.
... Elles sont contiguës en mémoire.
Si une donnée est accédée, il est probable qu'elle soit accédée à nouveau dans un avenir proche.
Scénario typique :
- Variables dans une boucle：
for i in range(1000000): total += i— VariableiettotalAccédée 1 million de fois en peu de temps. - Code chaud de fonction: 20% du code d'un programme représente 80% de son temps d'exécution ; ces instructions sont fréquemment réaccédées.
- Paramètres de fonction fréquemment appelée: les variables locales d'une fonction récursive s'empilent sur la pile à chaque appel.
Localité spatiale
Si un élément de données est accédé, les données proches sont aussi susceptibles d'être accédées.
Scénario typique :
- Parcours séquentiel de tableau：
for i in range(len(arr)): sum += arr[i]—arr - Champs de struct/objet: accès
student.nameAprès [cela], il est très probable que le prochain accès soit...student.age, ils sont adjacents en mémoire. - Instructions exécutées séquentiellement: après que le CPU a exécuté l'instruction à l'adresse 100, l'instruction suivante se trouve probablement à l'adresse 104.
Visualisation des deux types de localité
时间局部性示意图：
时间轴： t1 t2 t3 t4 t5 t6 t7 t8
访问地址： A B A C A D B A
|_____|_____|_____|
地址 A 在短时间内被多次访问——时间局部性
空间局部性示意图：
内存地址： 100 104 108 112 116 120 124 128
访问顺序： *1 *2 *3 *4 *5
|_____________________________|
连续访问相邻地址——空间局部性
Les CPU modernes exploitent la localité spatiale pour améliorer les performances : lors du chargement des données à l'adresse 100 en mémoire, ils chargent aussi les adresses 100~164 (une ligne de cache complète, généralement 64 octets) dans le cache. Ainsi, lors de l'accès à l'adresse 104, elle est déjà dans le cache.
Politique de remplacement du cache : que faire lorsqu'il est plein
Les emplacements de cache sont limités ; lorsque le cache est plein et que de nouvelles données doivent y entrer, il doitÉvincer une ancienne donnée. La décision de « qui est évincé » est la politique de remplacement du cache.
| Politique | Anglais | Règles | évaluation |
|---|---|---|---|
| Moins récemment utilisé | LRU (moins récemment utilisé) | Évincer les données auxquelles on n'a pas accédé depuis le plus longtemps | Le plus couramment utilisé, fonctionne très bien |
| premier entré, premier sorti | FIFO (premier entré, premier sorti) | Évacuer les données entrées dans le cache le plus tôt | Simple mais efficacité moyenne |
| Le moins fréquemment utilisé | LFU (Least Frequently Used) | Évacuer les données ayant le moins d'accès | Favorable aux données chaudes, mais les anciennes données peuvent « refuser de partir » |
| Remplacement aléatoire | Aléatoire | Choisir aléatoirement une entrée à évacuer | Le plus simple à implémenter, fonctionne bien |
LRU donne les meilleurs résultats en pratique car il exploite directement la localité temporelle — « Si elle n'a pas été utilisée récemment, elle ne sera probablement pas utilisée avant un moment. »
Les vrais caches CPU utilisent généralement des variantes approximatives de LRU (telles que le pseudo-LRU) pour réduire la complexité de mise en œuvre matérielle.
Démo interactive : simulateur de cache LRU
Le programme Python suivant simule entièrement le fonctionnement d’un cache LRU. Vous pouvez modifier la séquence d’accès et la capacité du cache pour observer l’évolution du taux de succès.
Exemple
Simulateur de cache LRU (exemple de démonstration)
Fonction :
1. Simuler la séquence d’accès du CPU aux adresses mémoire
2. Utiliser la stratégie LRU pour gérer le cache
3. Marquer en temps réel chaque accès comme 'hit' ou 'miss'
4. Calculer et afficher le taux de succès
"""
from collections import OrderedDict
class LRUCache:
"""
Simulateur de cache LRU (Least Recently Used)
Utilisez OrderedDict pour maintenir l’ordre d’accès ; les éléments les plus proches de la fin sont les plus récemment accédés.
"""
def __init__(self, capacity):
"""
Initialiser le cache
:param capacity: capacité du cache (nombre d'entrées pouvant être stockées)
"""
self.capacity = capacity
self.cache = OrderedDict() # Dictionnaire ordonné : clé=address, valeur=data
self.hits = 0 # Nombre de succès
self.misses = 0 # Nombre d'échecs
self.evictions = 0 # Nombre d'évictions
def access(self, address):
"""
Simuler un accès mémoire
:param address: l'adresse mémoire à laquelle accéder
:return: (result_str, is_hit)
"""
if address in self.cache:
# Succès du cache !
self.hits += 1
# Politique LRU : déplacer l'entrée touchée à la fin (marquée comme la plus récemment utilisée)
self.cache.move_to_end(address)
return "HIT", True
else:
# Défaut de cache
self.misses += 1
evicted = None
if len(self.cache) >= self.capacity:
# Le cache est plein, il faut évincer l'élément le moins récemment utilisé (le premier élément d'OrderedDict)
evicted_addr, _ = self.cache.popitem(last=False)
self.evictions += 1
evicted = evicted_addr
# Charger de nouvelles données depuis le 'stockage de niveau suivant' (simulé comme une récupération directe des données)
data = f"DATA_AT_{address}"
self.cache[address] = data
return "MISS", False
def hit_rate(self):
"""Calcule le taux de succès actuel du cache (pourcentage)"""
total = self.hits + self.misses
if total == 0:
return 0.0
return (self.hits / total) * 100
def current_state(self):
"""Retourne le contenu actuellement mis en cache (du plus ancien au plus récent)"""
return list(self.cache.keys())
def run_simulation(access_sequence, cache_capacity):
"""
Exécuter une simulation complète du cache
:param access_sequence: La séquence d'accès mémoire à simuler (liste d'entiers)
:param cache_capacity: capacité du cache
"""
cache = LRUCache(cache_capacity)
print("=" * 70)
print(f"EXEMPLE de simulateur de cache LRU")
print(fCapacité du cache : {cache_capacity} emplacements)
print(f"Séquence d'accès : {access_sequence}")
print("=" * 70)
print(f"{'étape':<6} {'adresse':<8} {'résultat':<8} {'état du cache (ancien→nouveau)':<40}")
print("-" * 70)
for i, addr in enumerate(access_sequence, 1):
result, is_hit = cache.access(addr)
state = cache.current_state()
hit_mark = "SUCCÈS [OK]" if is_hit else "DÉFAUT X"
print(f"{i:<6} {addr:<8} {hit_mark:<8} {str(state):<40}")
# Statistiques de sortie
print("-" * 70)
print(f"\nRésultats des statistiques :")
print(f" Nombre de succès (Hits) : {cache.hits}")
print(f" Nombre d'échecs (Misses): {cache.misses}")
print(f" Nombre d'évictions (Evictions): {cache.evictions}")
print(f" Taux de réussite : {cache.hit_rate():.1f}%")
print()
return cache
# ============================================================
# Démo 1 : comportement de base du LRU
# ============================================================
print("\n>>> Démo 1 : Comportement de base du cache LRU")
print(La séquence d'accès montre une localité temporelle—l'adresse 10 est accédée de façon répétée\n")
run_simulation(
access_sequence=[10, 20, 10, 30, 40, 10, 20, 50, 10, 20],
cache_capacity=4
)
# ============================================================
# Démo 2 : Impact de différentes capacités de cache sur le taux de succès
# ============================================================
print("\n>>> Démo 2 : Effet de la capacité du cache sur le taux de succès")
print("Les performances de la même séquence d'accès sous différentes capacités de cache\n")
test_sequence = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5,
1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7]
print(f"Longueur de la séquence d'accès : {len(test_sequence)}")
print(f"{'capacité':<8} {'succès':<8} {'échecs':<8} {'taux de succès':<10}")
print("-" * 35)
for cap in [1, 2, 3, 4, 5, 8, 16]:
c = LRUCache(cap)
for addr in test_sequence:
c.access(addr)
print(f"{cap:<8} {c.hits:<8} {c.misses:<8} {c.hit_rate():<8.1f}%")
# ============================================================
# Démo 3 : Comparer 'accès aléatoire' vs 'accès avec localité'
# ============================================================
print("\n>>> Démo 3 : Accès avec localité vs accès aléatoire)
print("Même capacité de cache (8), différences de taux de succès selon différents motifs d'accès\n")
import random
random.seed(42)
# Motif A : Accès avec localité (simulation d'un parcours en boucle d'un tableau)
local_access = []
for _ in range(20):
# À chaque boucle, accéder consécutivement dans la plage 0-15, puis sauter
base = random.randint(0, 50)
for offset in range(5):
local_access.append(base + offset)
# Mode B : accès complètement aléatoire
random_access = [random.randint(0, 100) for _ in range(100)]
for label, seq in [("Accès avec localité", local_access), ("Accès aléatoire", random_access)]:
c = LRUCache(8)
for addr in seq:
c.access(addr)
print(f" {label} : taux de réussite = {c.hit_rate():.1f}% (totalVisites {len(seq)} fois)")
Démo interactive : simulation en temps réel des succès/échecs de cache
Générer aléatoirement une séquence d'accès mémoire avec localité (30 accès), animer chaque processus de recherche dans le cache, suivre le taux de réussite en temps réel et tracer la courbe d'évolution
Exécutez ce code et vous constaterez :
- Plus la capacité du cache est grande, plus le taux de succès est élevé—mais l'amélioration diminue progressivement (effet marginal)
- Les motifs d'accès présentant une localité ont des taux de succès bien plus élevés que l'accès aléatoire—c'est pourquoi les caches sont efficaces
- Avec la politique LRU, les adresses accédées de façon répétée restent dans le cache et ne sont presque jamais évincées
Trois types de défauts de cache
Tous les « défauts de cache » ne se valent pas. Les ingénieurs matériels les classent en trois types :
| Type | Anglais | Quand cela se produit | Peut-on l'éviter ? |
|---|---|---|---|
| Défaut obligatoire | Défaut obligatoire (défaut à froid) | Lorsqu'une donnée est accédée pour la première fois, elle n'est pas encore dans le cache | Inévitable (le premier accès est toujours à froid) |
| Défaut de capacité | Défaut de capacité | L'ensemble de travail (données activement utilisées par le programme) est plus grand que la capacité du cache | Augmenter la taille du cache ou réduire l'ensemble de travail |
| Défaut de conflit | Défaut de conflit | Des adresses différentes sont mappées vers le même emplacement dans le cache (fréquent dans les caches à mappage direct) | Utiliser un mappage associatif par ensemble ou entièrement associatif |
Pour les programmeurs ordinaires, il est plus courant de traiter les deux premiers types :
- Défaut obligatoire: inévitable, mais plus votre programme s'exécute longtemps, plus son impact est faible.
- Défaut de capacité: Peut être atténué en optimisant la taille des structures de données et les motifs d'accès. Par exemple, utilisez des types de données plus compacts, traitez les grands tableaux par blocs.
Comprendre les défauts de cache est essentiel pour écrire du code très performant. Une règle simple : rendez vos motifs d'accès aux données adaptés au cache — parcourez les tableaux dans l'ordre de disposition en mémoire, évitez les accès dispersés et gardez proches en mémoire les données souvent utilisées ensemble.
Pratique de programmation : code adapté au cache
Voici un exemple classique : lors du parcours d'un tableau 2D, un parcours en ordre de lignes vs en ordre de colonnes fait toute la différence en termes de performances.
Exemple
Parcours de tableau adapté au cache vs non adapté au cache (exemple de démonstration)
Montrer comment différents motifs d'accès aux mêmes données affectent les performances du cache
"""
import time
# Stockage des listes Python : tableau à deux dimensions = liste de listes
# Dans arr[i][j], arr[i] est une ligne entière, contiguë en mémoire.
# Ainsi, le parcours ligne par ligne = favorable au cache, le parcours colonne par colonne = défavorable au cache
def traverse_row_major(arr):
"""
Parcours ligne par ligne : fixer d'abord l'indice de ligne i, puis parcourir les colonnes j
Motif d'accès : arr[0][0], arr[0][1], arr[0][2]...
Disposition en mémoire : ces éléments sont contigus en mémoire -- bonne localité spatiale !
"""
total = 0
rows = len(arr)
cols = len(arr[0])
for i in range(rows):
for j in range(cols):
total += arr[i][j]
return total
def traverse_column_major(arr):
"""
Parcours par colonnes : fixer d'abord l'indice de colonne j, puis parcourir les lignes i
Motif d'accès : arr[0][0], arr[1][0], arr[2][0]...
Disposition en mémoire : ces éléments sautent d'un endroit à l'autre en mémoire -- mauvaise localité spatiale !
"""
total = 0
rows = len(arr)
cols = len(arr[0])
for j in range(cols):
for i in range(rows):
total += arr[i][j]
return total
# Créer un grand tableau (1000 x 1000)
SIZE = 1000
print(f"Création d'un tableau 2D {SIZE}x{SIZE}...")
arr = [[i * SIZE + j for j in range(SIZE)] for i in range(SIZE)]
# Préchauffer d'abord pour éviter le biais de démarrage à froid
traverse_row_major(arr)
traverse_column_major(arr)
# Test formel
print("\nLancer la comparaison des performances (exécuter 3 fois, prendre la moyenne):")
print("-" * 50)
def benchmark(func, arr, trials=3):
Temps moyen sur plusieurs exécutions
times = []
for _ in range(trials):
start = time.perf_counter()
func(arr)
elapsed = time.perf_counter() - start
times.append(elapsed)
return sum(times) / len(times)
row_time = benchmark(traverse_row_major, arr)
col_time = benchmark(traverse_column_major, arr)
print(f"Parcours par ligne (adapté au cache) : {row_time:.4f} secondes")
print(fParcours par colonne (non adapté au cache) : {col_time:.4f} secondes)
print(fLe parcours par colonne est plus lent que le parcours par ligne : {col_time / row_time:.1f} fois)
print()
print("Analyse des causes :")
print(Lors d'un parcours par ligne, arr[i][0], arr[i][1], arr[i][2]... sont stockés de façon contiguë en mémoire)
print(Lors du premier accès à arr[i][0], le CPU charge plusieurs éléments suivants dans le cache en même temps)
print(" Les accès suivants à arr[i][1], arr[i][2] atteindront directement le cache")
print()
print(" Lors d'un parcours par colonne, arr[0][j], arr[1][j], arr[2][j]... sont chacun séparés par une ligne entière en mémoire.")
print(Presque chaque accès nécessite un chargement depuis la mémoire, ce qui conduit à un taux de succès du cache extrêmement faible)
# Complément : test simple - utiliser id() de Python pour vérifier l'adresse mémoire
print("\nVérification de la disposition mémoire (démo de petit tableau) :")
petit = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(fid de arr[0][0] : {id(small[0][0])})
print(f"arr[0][1] d'id : {id(small[0][1])} (PoorValue: {id(small[0][1]) - id(small[0][0])})")
print(fid de arr[0][2] : {id(small[0][2])} (contigu avec [0][0]))
print(f"L'id de arr[1][0] : {id(small[1][0])} (non contigu avec [0][2], car il s'étend sur une ligne)")