Ein Prozessor addiert zwei Zahlen in einem Bruchteil einer Nanosekunde, aber eine Zahl zu holen, die in keinem Cache liegt, kann 80 ns dauern. Diese Lektion macht aus den Latenzzahlen eine einzige Kennzahl, die durchschnittlichen Kosten eines Speicherzugriffs, und zeigt, welche Speicherebene Ihre Zeit frisst.
Warum der Speicher und nicht die Arithmetik die Geschwindigkeit bestimmt
Ein Trading-Programm verbringt die meiste Zeit damit, auf Daten zu warten: einen Preis, eine Order, eine Tabellenzeile. Die Rechnung mit diesen Daten ist fast gratis, aber die Daten müssen erst vom Speicher zum Prozessor reisen, und je weiter weg sie liegen, desto länger dauert das. Denken Sie an einen Schreibtisch, ein Regal, das Stockwerk einer Bibliothek und ein Lager am anderen Ende der Stadt. Die paar Blätter auf dem Schreibtisch sind sofort da, das Regal braucht Sekunden, die Bibliothek eine Minute und das Lager einen Nachmittag. Computer kopieren die am meisten genutzten Daten in kleine, schnelle Speicher neben dem Prozessor, genannt Caches, damit die meisten Anfragen am Schreibtisch beantwortet werden.
Die Zeit zwischen der Anfrage nach einem Wert und seinem Eintreffen, hier in Nanosekunden (Milliardstel Sekunden) gemessen.
Ein typischer Serverkern hat drei Caches vor dem Hauptspeicher. Wir nennen sie L1, L2 und L3 und den Hauptspeicher RAM. Eine Anfrage, die ein Cache beantwortet, ist ein Treffer; eine Anfrage, die zur nächsten Ebene weiter muss, ist ein Fehlzugriff. Die Tabelle unten stellt die vier Latenzen nebeneinander.
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
Jede Ebene ist mehrfach langsamer als die darüber, und der RAM ist 80-mal langsamer als L1. In dieser ganzen Fähigkeit geht es darum, dass die meisten Zugriffe nahe der Spitze beantwortet werden.
Was ein Zugriff kostet
Ein Zugriff beginnt bei L1. Liegt der Wert dort, kostet der Zugriff die L1-Latenz und ist vorbei. Sonst fragt der Prozessor L2, dann L3, dann den RAM, der den Wert immer hat. Jede befragte Ebene kostet Zeit, ob sie trifft oder nicht, ein in L3 gefundener Zugriff hat also L1, L2 und L3 bezahlt.
- 1L1 fragen1 ns zahlen. Ein Treffer beendet den Zugriff.
- 2Bei Fehlzugriff L2 fragen4 ns mehr zahlen. Ein Treffer beendet den Zugriff.
- 3Bei Fehlzugriff L3 fragen15 ns mehr zahlen. Ein Treffer beendet den Zugriff.
- 4Bei Fehlzugriff zum RAM80 ns mehr zahlen. Der RAM hat den Wert immer.
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
Ein von L3 beantworteter Zugriff kostet 20 ns, nicht 15: die 1 ns und 4 ns für die beiden früheren Fehlzugriffe gehören zur Rechnung.
Jede Trefferquote zählt nur die Zugriffe, die diese Ebene erreichen. Eine L2-Trefferquote von 0,8 heißt 80 % der Zugriffe, die L1 verfehlt haben, nicht 80 % aller Zugriffe. Beides zu verwechseln ist der häufigste Fehler in diesem Thema.
Die durchschnittliche Zugriffszeit
Kein einzelner Zugriff ist typisch, also fragen wir nach dem Durchschnitt über viele Zugriffe. Gewichten Sie die Kosten jedes Pfads mit seiner Häufigkeit. Jeder Zugriff zahlt die L1-Latenz; nur der Anteil, der L1 verfehlt, zahlt L2; nur der, der beide verfehlt, zahlt L3; und so weiter. Als ein Ausdruck, mit Klammern, die wie die Ebenen verschachtelt sind:
Das ist die durchschnittliche Speicherzugriffszeit. Lesen Sie die Klammern von innen nach außen: die innerste ist, was ein Fehlzugriff in L3 kostet, die nächste addiert den L3-Besuch, und so weiter bis zum L1-Besuch, den jeder Zugriff zahlt.
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
1 - hist der Anteil der Zugriffe, die verfehlen, jede Klammer wird also mit dem Anteil multipliziert, der so weit kommt.
Selbst wenn 90 % der Zugriffe in L1 treffen, liegt der Durchschnitt noch bei 2,18 ns, mehr als das Doppelte der L1-Latenz. Die wenigen Zugriffe, die tief gehen, sind so teuer, dass sie den Durchschnitt bestimmen. Darum kann eine scheinbar hervorragende Trefferquote ein langsames Programm verbergen.
Chip-Hersteller geben die Latenz in Prozessortakten an: 4 Takte bei 4 GHz sind 1 ns. Wir nutzen Nanosekunden, damit sich die Ebenen auf einen Blick vergleichen lassen. Die Zahlen sind typisch, nicht exakt: echte Chips weichen um den Faktor zwei in beide Richtungen ab.
Wer antwortet und wer kostet
Zwei Fragen sehen ähnlich aus, haben aber verschiedene Antworten. Welche Ebene beantwortet die Zugriffe? Und welche Ebene nimmt die Zeit? Die erste zählt Zugriffe, die zweite zählt Warten. Eine Ebene wird von einem Anteil der Zugriffe erreicht, und jeder Besuch kostet ihre Latenz, eine selten erreichte, aber langsame Ebene kann das Warten also trotzdem dominieren.
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
reachist der Anteil der Zugriffe, die jede Ebene besuchen: alle besuchen L1. - 2
sum(cost)ist die durchschnittliche Zugriffszeit: dieselben 2,18 ns wie zuvor.
Der RAM beantwortet nur 0,6 % der Zugriffe, macht aber 22 % der Wartezeit aus, während L1 90 % beantwortet und 46 % der Zeit nimmt. Das ist die Schlüsselaussage hinter jeder Optimierung in dieser Fähigkeit: Zählen Sie nicht Zugriffe, zählen Sie, wohin die Zeit geht.
Eine echte Tabelle lesen
Wie viel bedeutet das für eine echte Tabelle? Die SPY-Tagesbalken-Tabelle des Labors hat 5.405 Zeilen und fünf Spalten (Eröffnung, Hoch, Tief, Schluss, Volumen), also 27.025 Werte. Lesen Sie jeden Wert einmal unter drei Bedingungen: heiße Caches, in denen fast alles trifft, warme Caches und kalte Caches, in denen die Hälfte der Zugriffe auf jeder Ebene verfehlt.
Was Sie bauen werden
Das Labor macht aus dieser Lektion sechs kleine Funktionen, jede baut auf den vorigen auf, und endet damit, das Lesen der echten SPY-Tabelle zu beziffern. Hier sind sie mit der Frage, die jede beantwortet.
- Funktion · FrageBaut auf
- average_access_time(hit_rates)Was kostet ein Zugriff im Durchschnitt?Die Latenztabelle
- slowdown(hit_rates)Wie viel langsamer als immer in L1 zu treffen?average_access_time
- levels_served(hit_rates)Welche Ebene beantwortet die Zugriffe?Lokale Trefferquoten
- time_shares(hit_rates)Welche Ebene nimmt die Zeit?average_access_time
- scan_time_us(n_accesses, hit_rates)Wie lange dauern n Zugriffe?average_access_time
- study(bars)Was kostet es, die ganze SPY-Tabelle zu lesen?scan_time_ustime_shares
Nächstes Thema: Diese Lektion hat die Trefferquoten als gegeben genommen. In Cache-Zeilen und räumliche Lokalität bauen Sie den Cache, der sie erzeugt, und erfahren, warum es fast nichts kostet, einen Wert neben einem gerade gelesenen zu lesen.
Lab: Was bewertet wird
6 Aufgaben · 100 Pkt.- Durchschnittliche Zugriffszeit20 Pkt.
- Verlangsamung gegenüber L110 Pkt.
- Wer die Zugriffe beantwortet15 Pkt.
- Wer die Zeit nimmt20 Pkt.
- Die Zeit von n Zugriffen15 Pkt.
- Die Studie mit der SPY-Tabelle20 Pkt.