Zeitliche Lokalität und Arbeitsmengen

Ein Cache hilft nur bei Daten, die Sie erneut lesen, und entscheidend ist, wie bald. Diese Lektion misst das mit einer einzigen Zahl, der Wiederverwendungsdistanz, und sagt damit die Trefferquote jeder Cache-Größe auf einmal voraus, einschließlich der Klippe, an der eine Schleife nur ein kleines bisschen zu groß ist.

Die letzten beiden Themen handelten davon, wohin Zeilen kommen. Dieses handelt davon, wann sie wiederkommen. Ein Programm, das einen Preis liest, etwas arbeitet und denselben Preis einen Moment später wieder liest, zeigt zeitliche Lokalität. Je kürzer die Lücke, desto größer die Chance, dass die Zeile noch im Cache liegt. Denken Sie an die Bücher auf Ihrem Schreibtisch: Das Buch von vor einer Minute liegt noch da, das vom letzten Monat ist zurück ins Regal gewandert.

Dieselbe Zeile 5 zweimal hintereinander zu lesen ergibt Distanz 0. In der Folge 1, 2, 3, 1 hat der letzte Zugriff Distanz 2, weil die Zeilen 2 und 3 dazwischen kamen. Zehnmal Zeile 2 zwischen zwei Zugriffen auf Zeile 1 zu lesen zählt trotzdem als eine Zeile. Der Code führt eine Liste der Zeilen in der Reihenfolge ihrer letzten Benutzung, die jüngste zuletzt. Kommt eine Zeile wieder, sind die Zeilen hinter ihr in der Liste genau die seither benutzten.

def reuse_distances(lines):    stack = []    out = []    for line in lines:        if line in stack:            position = stack.index(line)            out.append(len(stack) - 1 - position)1            stack.pop(position)        else:            out.append(None)        stack.append(line)    return outprint(reuse_distances([1, 2, 3, 1, 2, 1, 1]))

[None, None, None, 2, 2, 1, 0]

1. 1Die Zeilen hinter dieser in der Liste sind genau die seit ihrem letzten Lesen benutzten: ihre Anzahl ist die Distanz.

Hier die nützliche Tatsache. Nehmen Sie einen Cache, der C Zeilen hält und die am längsten nicht benutzte verdrängt, gleich welche Zeilennummern. In jedem Moment hält er die C zuletzt benutzten verschiedenen Zeilen. Ein Lesezugriff trifft genau dann, wenn seine Zeile darunter ist, also wenn seit seiner letzten Benutzung weniger als C verschiedene Zeilen gelesen wurden. Anders gesagt: Der Zugriff trifft, wenn seine Wiederverwendungsdistanz kleiner als C ist.

Der Code unten prüft die Behauptung. Er simuliert einen LRU-Cache für Kapazitäten von 1 bis 4 und berechnet die Trefferquote auch allein aus den Distanzen, ganz ohne Cache. Beide Spalten stimmen überein. Die Distanzen werden einmal berechnet und liefern dann die Trefferquote jeder Cache-Größe.

def lru_hit_rate(lines, capacity):    cache = []    hits = 0    for line in lines:        if line in cache:            hits += 1            cache.remove(line)        elif len(cache) >= capacity:            cache.pop(0)        cache.append(line)    return hits / len(lines)def hit_rate_from_distances(distances, capacity):    hits = sum(1 for d in distances if d is not None and d < capacity)    return hits / len(distances)lines = [1, 2, 3, 1, 2, 3, 4, 1, 2, 3]d = reuse_distances(lines)for capacity in (1, 2, 3, 4):    print(capacity, "lines:", round(lru_hit_rate(lines, capacity), 3), round(hit_rate_from_distances(d, capacity), 3))1

1 lines: 0.0 0.0
2 lines: 0.0 0.0
3 lines: 0.3 0.3
4 lines: 0.6 0.6

1. 1Dieselben Zahlen in beiden Spalten: Die Distanzen allein sagen die Trefferquote jeder Cache-Größe voraus.

Die Arbeitsmenge einer Folge von Lesezugriffen ist die Menge der verschiedenen Zeilen, die sie berühren. Passt sie in den Cache, läuft das Programm fast ganz aus dem Cache. Ist sie nur wenig größer, kann LRU völlig versagen. Nehmen Sie eine Schleife, die 48 Zeilen der Reihe nach liest, dreimal. Jede Zeile wird nach 47 anderen wieder gelesen, also ist jede Wiederverwendungsdistanz 47. Ein Cache mit 47 Zeilen oder weniger trifft deshalb nie, und einer mit 48 trifft bei jedem Zugriff nach dem ersten Durchlauf.

def sweep_lines(n_lines, passes):    return list(range(n_lines)) * passeslines = sweep_lines(48, 3)for capacity in (16, 32, 47, 48):    print(capacity, "lines:", round(lru_hit_rate(lines, capacity), 3))

16 lines: 0.0
32 lines: 0.0
47 lines: 0.0
48 lines: 0.667

Ein auf die langsame Art berechneter gleitender Mittelwert liest jeden Tag die letzten 20 Werte: Er liest 19 der 20 Werte vom Vortag erneut. Das ist ein Programm mit viel zeitlicher Lokalität. Der Code baut die gelesenen Adressen für die ersten 600 Schlusskurse, macht Zeilen daraus und misst die Distanzen, die Trefferquote für vier Cache-Größen und die Arbeitsmenge von 20 aufeinanderfolgenden Lesezugriffen.

def rolling_mean_trace(n, window, elem_bytes):    trace = []    for end in range(window - 1, n):        for position in range(end - window + 1, end + 1):            trace.append(position * elem_bytes)    return tracedef working_set(lines, window):    return max(len(set(lines[i:i + window])) for i in range(len(lines) - window + 1))lines = [address // 64 for address in rolling_mean_trace(600, 20, 8)]d = reuse_distances(lines)print(len(lines), "reads from", len(set(lines)), "lines")for capacity in (1, 2, 4, 8):    print(capacity, "lines:", round(hit_rate_from_distances(d, capacity), 3))print("working set of 20 reads:", working_set(lines, 20), "lines")

11620 reads from 75 lines
1 lines: 0.831
2 lines: 0.831
4 lines: 0.994
8 lines: 0.994
working set of 20 reads: 4 lines

Eine Zeile genügt für 83 % der Lesezugriffe, weil der nächste Wert des Arrays in der gerade gelesenen Zeile liegt. Vier Zeilen erreichen 99,4 %. Die 75 Zeilen des ganzen Datensatzes müssen nie hineinpassen: Die Arbeitsmenge von 20 Lesezugriffen sind nur 4 Zeilen, ein winziger Cache reicht also. Das ist der Unterschied zwischen der Größe der Daten und der Größe der Arbeitsmenge.

Das Labor verlangt die obigen Teile, dazu den Helfer, der den kleinsten Cache für eine Trefferquote findet, und endet mit der Studie an den echten SPY-Schlusskursen.

• Funktion · FrageBaut auf
• reuse_distances(lines)Wie bald wird jede Zeile wieder gelesen?Eine Liste in Reihenfolge der letzten Benutzung
• lru_hit_rate(lines, capacity)Wie viel trifft ein simulierter LRU-Cache?Zeilen in LRU-Reihenfolge
• hit_rate_from_distances(distances, capacity)Dieselbe Trefferquote ohne Cache?reuse_distances
• working_set(lines, window)Wie viele Zeilen berührt eine Folge von Lesezugriffen?Ein gleitendes Fenster
• capacity_for(lines, target)Wie klein darf der Cache sein?reuse_distanceshit_rate_from_distances
• rolling_mean_trace(n, window, elem_bytes)Welche Adressen liest ein langsamer gleitender Mittelwert?Einfache Arithmetik
• study(bars)Wie lokal ist ein gleitender Mittelwert auf den SPY-Schlusskursen?rolling_mean_tracecapacity_for

Nächstes Thema: Sie wissen nun, wie aus einem Layout eine Spur und aus einer Spur Treffer und Fehlzugriffe werden. In Array of Structs gegen Struct of Arrays nutzen Sie das, um das Layout einer Tick-Tabelle zu wählen, und vergleichen Spaltenzugriffe und Ganzzeilenzugriffe in beiden Layouts.