Cache-Treffer und Cache-Miss
Wenn die CPU Daten benötigt, schaut sie zuerst in den Cache. Wenn sie gefunden werden, ist alles gut—aber was, wenn sie nicht gefunden werden?
Diese Lektion hilft dir, die Kernmechanismen der Funktionsweise von Caches zu verstehen, und das Schlüsselprinzip, das Caches effektiv macht—Lokalitätsprinzip。
Alltagsanalogie: der Schreibtisch in einer Bibliothek
Du schreibst in der Bibliothek eine Arbeit. Auf deinen Schreibtisch passen höchstens 4 Bücher—das ist deinCache, seine Kapazität ist klein, aber er ist in Reichweite.
Wenn du ein Buch brauchst, prüfe zuerst, ob es auf dem Schreibtisch liegt:
- Auf dem Tisch (Cache-Treffer): einfach aufschlagen und nutzen, keine Wartezeit.
- Nicht auf dem Tisch (Cache-Miss): aufstehen und im Bücherregal nachsehen, es zurückbringen und auf den Schreibtisch legen. Wenn der Schreibtisch voll ist, musst du das Buch, das am längsten nicht angefasst wurde, zurück ins Regal stellen.
Diese einfache Regel ist genau das Wesen eines Computer-Cache-Systems—"Behalte die zuletzt genutzten, verdränge die selten genutzten"。
Wenn du weitergehst, wirst du feststellen: Beim Schreiben einer Arbeit blätterst du nicht zufällig durch unzusammenhängende Bücher. Über einen bestimmten Zeitraum hinweg ziehst du wiederholt dieselben Referenzmaterialien zu Rate. Von den Büchern in den Tausenden von Regalen der Bibliothek sind die, die du tatsächlich angefasst hast, vielleicht nur zwanzig oder dreißig. Das istLokalitätsprinzipin Aktion.
Kernkonzept: Cache-Treffer und Cache-Fehlschlag
Grundbegriffe
| Begriff | Englisch | Bedeutung |
|---|---|---|
| Cache-Treffer | Cache-Treffer | Die von der CPU angeforderten Daten befinden sich direkt im Cache und werden direkt verwendet |
| Cache-Fehlschlag | Cache-Fehlschlag | Die von der CPU angeforderten Daten sind nicht im Cache und müssen aus der nächsten (langsameren) Speicherebene geladen werden |
| Trefferquote | Trefferquote | Anzahl der Treffer / Gesamtzugriffe, je höher, desto besser (idealerweise nahe 100%) |
| Fehlzugriffsstrafe | Fehlzugriffsstrafe | Die zusätzliche Zeit, die nach einem Fehlzugriff zum Laden von Daten aus der nächsten Ebene aufgewendet wird |
| Trefferzeit | Trefferzeit | Zeit, die zum Lesen von Daten benötigt wird, wenn ein Cache-Treffer vorliegt |
Ein einfaches Beispiel
, arr
| Schritte | Zugriffsadresse | Cache-Zustand (vor dem Zugriff) | Ergebnis | Grund |
|---|---|---|---|---|
| 1 | 10 | [] | Fehlzugriff | Der Cache ist leer, Adresse 10 ist nicht darin enthalten |
| 2 | 20 | [10] | Fehlzugriff | Adresse 20 ist nicht im Cache |
| 3 | 10 | [10, 20] | Treffer | Adresse 10 ist im Cache! (temporale Lokalität) |
| 4 | 30 | [10, 20] | Fehlzugriff | Adresse 30 ist nicht im Cache |
| 5 | 10 | [10, 20, 30] | Treffer | Adresse 10 ist wieder ein Treffer |
2 Treffer bei 5 Zugriffen, Trefferrate = 40 %. Nicht hoch, aber es demonstriert bereits das Prinzip des Cachings.
Warum Caches funktionieren: das Prinzip der Lokalität
Wenn ein Programm vollständig zufällig auf den Speicher zugreift, ist der Cache nahezu nutzlos—Daten werden nur in den Cache geladen, um gleich danach nicht verwendet zu werden.
Aber echte Programme verhalten sich nicht zufällig. Sie weisen starkeLokalitätauf, und genau das ist der fundamentale Grund, warum Caches effektiv sind.
... Sie liegen zusammenhängend im Speicher.
Wenn auf ein Datenelement zugegriffen wird, wird wahrscheinlich in naher Zukunft erneut darauf zugegriffen.
Typisches Szenario:
- Variablen in einer Schleife:
for i in range(1000000): total += i— VariableiundtotalInnerhalb eines kurzen Zeitraums 1 Million Mal zugegriffen. - Funktions-Hot-Code: 20% des Codes eines Programms machen 80% seiner Ausführungszeit aus; auf diese Anweisungen wird häufig erneut zugegriffen.
- Häufig aufgerufene Funktionsparameter: Lokale Variablen in einer rekursiven Funktion sammeln sich bei jedem Aufruf auf dem Stack an.
Räumliche Lokalität
Wenn auf ein Datenelement zugegriffen wird, wird wahrscheinlich auch auf benachbarte Daten zugegriffen.
Typisches Szenario:
- Sequenzieller Array-Durchlauf:
for i in range(len(arr)): sum += arr[i]—arr - Struct-/Objektfelder: Zugriff
student.nameDanach ist es sehr wahrscheinlich, dass der nächste Zugriff ... sein wirdstudent.age, sie liegen im Speicher nebeneinander. - Sequenziell ausgeführte Befehle: Nachdem die CPU den Befehl an Adresse 100 ausgeführt hat, befindet sich der nächste Befehl wahrscheinlich an Adresse 104.
Visualisierung der beiden Arten von Lokalität
时间局部性示意图:
时间轴: 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
|_____________________________|
连续访问相邻地址——空间局部性
Moderne CPUs nutzen räumliche Lokalität zur Leistungssteigerung: Wenn sie Daten von Adresse 100 im Speicher laden, laden sie auch die Adressen 100~164 (eine vollständige Cache-Zeile, normalerweise 64 Bytes) in den Cache. Auf diese Weise sind sie beim Zugriff auf Adresse 104 bereits im Cache.
Cache-Ersetzungsrichtlinie: Was tun, wenn sie voll ist
Cache-Slots sind begrenzt; wenn der Cache voll ist und neue Daten aufgenommen werden müssen, muss erein altes Datenelement verdrängen. Die Entscheidung, "wer verdrängt wird", ist die Cache-Ersetzungsrichtlinie.
| Policy | Englisch | Regeln | Bewertung |
|---|---|---|---|
| Am längsten nicht verwendet | LRU (Am längsten nicht verwendet) | Die Daten verdrängen, auf die am längsten nicht zugegriffen wurde | Am häufigsten verwendet, funktioniert sehr gut |
| First-In, First-Out | FIFO (First In First Out) | Verdränge die Daten, die zuerst in den Cache gelangt sind | Einfach, aber durchschnittliche Wirksamkeit |
| Am seltensten verwendet | LFU (am seltensten verwendet) | Verdränge die Daten mit den wenigsten Zugriffen | Freundlich gegenüber heißen Daten, aber alte Daten könnten sich "weigern zu gehen" |
| Zufällige Verdrängung | Zufällig | Wähle zufällig einen zum Verdrängen aus | Am einfachsten zu implementieren, funktioniert gut |
LRU schneidet in der Praxis am besten ab, weil es die zeitliche Lokalität direkt ausnutzt — "Wenn etwas kürzlich nicht verwendet wurde, wird es wahrscheinlich eine Weile nicht verwendet."
Echte CPU-Caches verwenden üblicherweise Näherungsvarianten von LRU (wie Pseudo-LRU), um die Komplexität der Hardware-Implementierung zu reduzieren.
Interaktive Demo: LRU-Cache-Simulator
Das folgende Python-Programm simuliert den Arbeitsprozess eines LRU-Caches vollständig. Sie können die Zugriffsfolge und die Cache-Kapazität ändern, um Änderungen der Trefferrate zu beobachten.
Beispiel
LRU-Cache-Simulator (Beispiel-Demo)
Funktion:
1. Die Zugriffsfolge der CPU auf Speicheradressen simulieren
2. LRU-Strategie zum Verwalten des Caches verwenden
3. Jeden Zugriff in Echtzeit als „Hit“ oder „Miss“ kennzeichnen
4. Die Trefferrate berechnen und anzeigen
"""
from collections import OrderedDict
class LRUCache:
"""
LRU (Least Recently Used) Cache-Simulator
OrderedDict verwenden, um die Zugriffsreihenfolge beizubehalten; Einträge näher am Ende wurden zuletzt zugegriffen.
"""
def __init__(self, capacity):
"""
Cache initialisieren
:param capacity: Cache-Kapazität (Anzahl der Einträge, die gespeichert werden können)
"""
self.capacity = capacity
self.cache = OrderedDict() # Geordnetes Wörterbuch: Schlüssel=address, Wert=data
self.hits = 0 # Trefferanzahl
self.misses = 0 # Anzahl der Fehlzugriffe
self.evictions = 0 # Anzahl der Verdrängungen
def access(self, address):
"""
Simuliert einen Speicherzugriff
:param address: die zuzugreifende Speicheradresse
:return: (result_str, is_hit)
"""
if address in self.cache:
# Cache-Treffer!
self.hits += 1
# LRU-Richtlinie: den Treffer-Eintrag ans Ende verschieben (als zuletzt verwendet markiert)
self.cache.move_to_end(address)
return "HIT", True
else:
# Cache-Fehlschlag
self.misses += 1
evicted = None
if len(self.cache) >= self.capacity:
# Cache ist voll, der am längsten nicht verwendete Eintrag muss verdrängt werden (das erste Element von OrderedDict)
evicted_addr, _ = self.cache.popitem(last=False)
self.evictions += 1
evicted = evicted_addr
# Neue Daten aus dem 'Next-Level-Speicher' laden (simuliert als direktes Abrufen von Daten)
data = f"DATA_AT_{address}"
self.cache[address] = data
return "MISS", False
def hit_rate(self):
"""Berechne die aktuelle Cache-Trefferrate (Prozentsatz)"""
total = self.hits + self.misses
if total == 0:
return 0.0
return (self.hits / total) * 100
def current_state(self):
"""Gibt den aktuell zwischengespeicherten Inhalt zurück (vom ältesten zum neuesten)"""
return list(self.cache.keys())
def run_simulation(access_sequence, cache_capacity):
"""
Führt eine vollständige Cache-Simulation aus
:param access_sequence: Die zu simulierende Speicherzugriffssequenz (Liste von ints)
:param cache_capacity: Cache-Kapazität
"""
cache = LRUCache(cache_capacity)
print("=" * 70)
print(f"BEISPIEL LRU-Cache-Simulator")
print(fCache-Kapazität: {cache_capacity} Plätze)
print(f"Zugriffssequenz: {access_sequence}")
print("=" * 70)
print(f"{'Schritt':<6} {'Adresse':<8} {'Ergebnis':<8} {'Cache-Status (alt→neu)':<40}")
print("-" * 70)
for i, addr in enumerate(access_sequence, 1):
result, is_hit = cache.access(addr)
state = cache.current_state()
hit_mark = "TREFFER [OK]" if is_hit else "FEHLSCHLAG X"
print(f"{i:<6} {addr:<8} {hit_mark:<8} {str(state):<40}")
# Ausgabestatistiken
print("-" * 70)
print(f"\nStatistik-Ergebnisse:")
print(f" Trefferzahl (Hits) : {cache.hits}")
print(f" Fehlschlaganzahl (Misses): {cache.misses}")
print(f" Verdrängungsanzahl (Evictions): {cache.evictions}")
print(f" Trefferquote : {cache.hit_rate():.1f}%")
print()
return cache
# ============================================================
# Demo 1: Grundlegendes LRU-Verhalten
# ============================================================
print("\n>>> Demo 1: Grundlegendes LRU-Cache-Verhalten")
print(Die Zugriffsfolge zeigt zeitliche Lokalität – auf Adresse 10 wird wiederholt zugegriffen\n")
run_simulation(
access_sequence=[10, 20, 10, 30, 40, 10, 20, 50, 10, 20],
cache_capacity=4
)
# ============================================================
# Demo 2: Auswirkung unterschiedlicher Cache-Kapazitäten auf die Trefferrate
# ============================================================
print("\n>>> Demo 2: Auswirkung der Cache-Kapazität auf die Trefferrate")
print("Die Leistung derselben Zugriffsfolge bei unterschiedlichen Cache-Kapazitäten\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"Länge der Zugriffsfolge: {len(test_sequence)}")
print(f"{'Kapazität':<8} {'Treffer':<8} {'Fehlzugriffe':<8} {'Trefferrate':<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}%")
# ============================================================
# Demo 3: Vergleich von 'Zufallszugriff' mit 'Lokalitätszugriff'
# ============================================================
print("\n>>> Demo 3: Lokalitätszugriff vs Zufallszugriff)
print("Gleiche Cache-Kapazität (8), Unterschiede der Trefferrate bei verschiedenen Zugriffsmustern\n")
import random
random.seed(42)
# Muster A: Zugriff mit Lokalität (Simulation der Schleifendurchquerung eines Arrays)
local_access = []
for _ in range(20):
# Jede Schleife: aufeinanderfolgender Zugriff im Bereich 0-15, dann Sprung
base = random.randint(0, 50)
for offset in range(5):
local_access.append(base + offset)
# Modus B: völlig zufälliger Zugriff
random_access = [random.randint(0, 100) for _ in range(100)]
for label, seq in [("Lokaler Zugriff", local_access), ("Zufälliger Zugriff", random_access)]:
c = LRUCache(8)
for addr in seq:
c.access(addr)
print(f" {label}: Trefferquote = {c.hit_rate():.1f}% (Gesamtzugriffe {len(seq)} Mal)")
Interaktive Demo: Echtzeitsimulation von Cache-Hit/Miss
Generiere zufällig eine Speicherzugriffssequenz mit Lokalität (30 Zugriffe), animiere jeden Cache-Lookup-Prozess, verfolge die Trefferquote in Echtzeit und zeichne die Änderungskurve.
Führen Sie diesen Code aus, und Sie werden feststellen:
- Je größer die Cache-Kapazität, desto höher die Trefferquote—aber die Verbesserung nimmt allmählich ab (marginaler Effekt)
- Zugriffsmuster mit Lokalität haben viel höhere Trefferquoten als zufällige Zugriffe—das ist der Grund, warum Caches effektiv sind
- Unter der LRU-Richtlinie bleiben wiederholt zugegriffene Adressen im Cache und werden fast nie verdrängt
Drei Arten von Cache-Fehlzugriffen
Nicht alle "Cache-Fehlzugriffe" sind gleich. Hardware-Entwickler klassifizieren sie in drei Typen:
| Type | Englisch | Wann er auftritt | Kann er vermieden werden? |
|---|---|---|---|
| Zwangsläufiger Fehlzugriff | Zwangsläufiger Fehlzugriff (Kaltstart-Fehlzugriff) | Wenn zum ersten Mal auf ein Datenelement zugegriffen wird, befindet es sich noch nicht im Cache | Unvermeidbar (der erste Zugriff ist immer kalt) |
| Kapazitätsfehlzugriff | Kapazitätsfehlzugriff | Der Arbeitssatz (die vom Programm aktiv genutzten Daten) ist größer als die Cache-Kapazität | Cache-Größe erhöhen oder Working Set verkleinern |
| Konflikt-Miss | Konflikt-Miss | Verschiedene Adressen werden auf dieselbe Stelle im Cache abgebildet (häufig bei direkt zugeordneten Caches) | Set-assoziative oder vollständig assoziative Zuordnung verwenden |
Für gewöhnliche Programmierer ist der Umgang mit den ersten beiden Arten häufiger:
- Compulsory-Miss: unvermeidbar, aber je länger Ihr Programm läuft, desto geringer ist seine Auswirkung.
- Kapazitäts-Miss: Kann durch Optimieren der Größe von Datenstrukturen und der Zugriffsmuster abgemildert werden. Verwenden Sie zum Beispiel kompaktere Datentypen und verarbeiten Sie große Arrays in Blöcken.
Cache-Misses zu verstehen ist der Schlüssel zum Schreiben von hochperformantem Code. Eine einfache Faustregel: Machen Sie Ihre Datenzugriffsmuster cachefreundlich – durchlaufen Sie Arrays in der Reihenfolge des Speicherlayouts, vermeiden Sie sprunghafte Zugriffe und halten Sie Daten, die oft zusammen verwendet werden, im Speicher nahe beieinander.
Programmierpraxis: cachefreundlicher Code
Hier ist ein klassisches Beispiel: Beim Durchlaufen eines 2D-Arrays macht zeilenweises gegenüber spaltenweisem Durchlaufen einen riesigen Unterschied in der Leistung.
Beispiel
Cachefreundliches vs. cacheunfreundliches Durchlaufen von Arrays (Beispiel-Demo)
Veranschaulichen Sie, wie unterschiedliche Zugriffsmuster auf dieselben Daten die Cache-Leistung beeinflussen
"""
import time
# Speicherung von Python-Listen: zweidimensionales Array = Liste von Listen
# In arr[i][j] ist arr[i] eine ganze Zeile, zusammenhängend im Speicher.
# Also ist zeilenweises Durchlaufen = cache-freundlich, spaltenweises Durchlaufen = cache-unfreundlich
def traverse_row_major(arr):
"""
Zeilenweises Durchlaufen: zuerst den Zeilenindex i festlegen, dann die Spalten j durchlaufen
Zugriffsmuster: arr[0][0], arr[0][1], arr[0][2]...
Speicherlayout: Diese Elemente liegen zusammenhängend im Speicher -- gute räumliche Lokalität!
"""
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):
"""
Spaltenweise Traversierung: Zuerst Spaltenindex j festlegen, dann Zeilen i durchlaufen
Zugriffsmuster: arr[0][0], arr[1][0], arr[2][0]...
Speicherlayout: Diese Elemente springen im Speicher umher -- schlechte räumliche Lokalität!
"""
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
# Erstelle ein großes Array (1000 x 1000)
SIZE = 1000
print(f"Erzeuge ein {SIZE}x{SIZE} 2D-Array...")
arr = [[i * SIZE + j for j in range(SIZE)] for i in range(SIZE)]
# Zuerst vorwärmen, um Cold-Start-Bias zu vermeiden
traverse_row_major(arr)
traverse_column_major(arr)
# Formaler Test
print("\nLeistungsvergleich starten (3-mal ausführen, Durchschnitt bilden):")
print("-" * 50)
def benchmark(func, arr, trials=3):
Durchschnittliche Zeit über mehrere Durchläufe
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"Zeilenweise Traversierung (cache-freundlich): {row_time:.4f} Sekunden")
print(fSpaltenweise Traversierung (cache-unfreundlich): {col_time:.4f} Sekunden)
print(fSpaltenweise ist langsamer als zeilenweise: {col_time / row_time:.1f} Mal)
print()
print("Ursachenanalyse:")
print(Beim zeilenweisen Durchlaufen werden arr[i][0], arr[i][1], arr[i][2]... zusammenhängend im Speicher abgelegt)
print(Beim ersten Zugriff auf arr[i][0] lädt die CPU mehrere nachfolgende Elemente gemeinsam in den Cache)
print(" Nachfolgende Zugriffe auf arr[i][1], arr[i][2] treffen direkt den Cache")
print()
print(" Beim spaltenweisen Durchlaufen sind arr[0][j], arr[1][j], arr[2][j]... jeweils durch eine ganze Zeile im Speicher getrennt.")
print(Fast jeder Zugriff erfordert ein Laden aus dem Speicher, was zu einer extrem niedrigen Cache-Trefferrate führt)
# Ergänzung: Einfacher Test – Pythons id() verwenden, um die Speicheradresse zu prüfen
print("\nÜberprüfung des Speicherlayouts (kleine Array-Demo):")
gering = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(fID von arr[0][0]: {id(small[0][0])})
print(f"ID von arr[0][1]: {id(small[0][1])} (PoorValue: {id(small[0][1]) - id(small[0][0])})")
print(fID von arr[0][2]: {id(small[0][2])} (zusammenhängend mit [0][0]))
print(f"Die ID von arr[1][0]: {id(small[1][0])} (nicht zusammenhängend mit [0][2], weil es eine Zeile überspannt)")