Abschlussprojekt: eine Tick-Tabelle neu anordnen und den Rückgang der Fehler belegen

6 Min. Lesezeit3 Codebeispiele

Alles, was diese Fähigkeit gelehrt hat, trifft sich in einer Tabelle von Ticks. Acht Spalten, drei Aufgaben, die sie unterschiedlich lesen, und drei Anordnungen im Speicher. Sie modellieren die Adresse jedes Werts, zählen die Fehlzugriffe jeder Aufgabe mit dem selbst gebauten Cache, bewerten sie mit dem Latenzmodell und beweisen, welche Anordnung gewinnt. Keine gewinnt alle Aufgaben; die hybride gewinnt die Mischung, mit 1,5-mal weniger Fehlzugriffen als das Array of Structs.

Eine Tabelle, drei Aufgaben

Eine Tick-Tabelle hat 8 Spalten zu 8 Byte: einen Zeitstempel, Bid- und Ask-Preise und -Größen, den Handelspreis, seine Größe und einige Flags. Eine Zeile ist genau 64 Byte groß, die Größe einer Cache-Zeile. Drei Aufgaben lesen diese Tabelle. Ein Scan liest die Preisspalte jeder Zeile, für einen gleitenden Durchschnitt. Eine Quote-Aufgabe liest Bid, Ask und Bid-Größe jeder Zeile, um ein Orderbuch aufzubauen. Ein Lookup liest den vollständigen Tick von 1.000 über die Tabelle verteilten Zeilen, wie es ein Debugger oder ein Replay tut. Der Speicher des ersten Themas hat eine Hierarchie, der des zweiten eine 64-Byte-Zeile und der des fünften zwei Anordnungen einer Tabelle: das Array of Structs (die Werte einer Zeile zusammen) und das Struct of Arrays (jede Spalte für sich). Nun gibt es einen dritten Weg, die hybride Anordnung, die die heißen Quote-Spalten zusammenhält und die kalten Spalten zusammenhält.

Eine Anordnung ist eine Liste von Spaltengruppen

Alle drei Anordnungen sind eine Idee. Eine Anordnung ist eine Liste von Spaltengruppen. Die Werte einer Gruppe werden Zeile für Zeile gespeichert, und die Gruppen folgen aufeinander. Eine Gruppe mit allen Spalten ist das Array of Structs; eine Gruppe pro Spalte ist das Struct of Arrays; zwei Gruppen zu vier Spalten sind unser Hybrid. Eine Funktion liefert also die Adresse jedes Werts in jeder Anordnung: die Gruppen vor derjenigen mit der Spalte überspringen, dann row * len(group) + position Werte in sie hineingehen.

main.pyPython

def address(groups, row, col, n_rows, elem_bytes=ELEM_BYTES):    base = 0    for group in groups:        if col in group:            return base + (row * len(group) + group.index(col)) * elem_bytes        base += n_rows * len(group) * elem_bytes1    raise ValueError("column %d is in no group" % col)print(address([[0, 1, 2]], 2, 1, 10))print(address([[0], [1], [2]], 2, 1, 10))print(address([[1, 2], [0]], 3, 0, 10))

56
96
184

1Eine Gruppe belegt n_rows * len(group) * elem_bytes Byte: Die nächste Gruppe beginnt direkt danach.

Prüfen Sie die drei Ergebnisse von Hand. Bei einer Gruppe mit drei Spalten ist Zeile 2, Spalte 1 der Wert Nummer 2 × 3 + 1 = 7, bei Byte 56. Bei einer Gruppe pro Spalte beginnt Spalte 1 nach den 10 Werten von Spalte 0, bei Byte 80, und Zeile 2 liegt 16 Byte weiter: 96. Im Hybrid [[1, 2], [0]] kommt die Gruppe von Spalte 0 an zweiter Stelle, nach 10 Zeilen zu 2 Werten (160 Byte), und Zeile 3 liegt 24 Byte weiter: 184.

Eine Adresse ist alles, was das Modell braucht

Der Cache sieht nie Spalten oder Zeilen, nur Adressen. Deshalb reichen wenige Zeilen, um Anordnungen zu vergleichen, die in C++ andere Structs und andere Schleifen bräuchten.

Zählen, bewerten und beweisen

Eine Aufgabe ist die Liste der Spalten, die sie für jede besuchte Zeile liest. Ihre Spur besteht für jede Zeile der Reihe nach aus den Adressen dieser Spalten; der Cache macht aus der Spur Fehlzugriffe; und das Latenzmodell des ersten Themas macht aus Fehlzugriffen Zeit, mit 1 ns pro Treffer und 80 ns pro Fehlzugriff. Der Vergleich ist dann eine Schleife über die Anordnungen, und der Beweis ist die kleinste Zahl. Führen Sie die drei Aufgaben der Lektion auf 4.000 Ticks aus, und Sie sehen, dass die beste Anordnung von der Aufgabe abhängt.

main.pyPython

def workload_trace(groups, n_rows, reads, rows):    return [address(groups, row, col, n_rows) for row in rows for col in reads]def layout_misses(groups, n_rows, reads, rows=None):    rows = range(n_rows) if rows is None else rows    return count_misses(workload_trace(groups, n_rows, reads, rows))def compare_layouts(layouts, n_rows, reads, rows=None):    return {name: layout_misses(groups, n_rows, reads, rows) for name, groups in layouts.items()}def best_layout(misses):    return min(misses, key=misses.get)def time_ns(accesses, misses, hit_ns=HIT_NS, miss_ns=MISS_NS):    return (accesses - misses) * hit_ns + misses * miss_nsprint(workload_trace([[0, 1]], 4, [1, 0], [2]))for job, reads in WORKLOADS.items():    rows = sampled_rows(4000) if job == "lookup" else None    result = compare_layouts(LAYOUTS, 4000, reads, rows)    print(job, result, "->", best_layout(result))

[40, 32]
scan {'aos': 4000, 'soa': 500, 'hybrid': 2000} -> soa
quote {'aos': 4000, 'soa': 1500, 'hybrid': 2000} -> soa
lookup {'aos': 1000, 'soa': 8000, 'hybrid': 2000} -> aos

Der Scan will eine einzige Spalte: Das Struct of Arrays packt acht Preise pro Zeile (500 Fehlzugriffe), und das Array of Structs verschwendet sieben Achtel jeder geladenen Zeile (4.000 Fehlzugriffe). Der Punkt-Lookup will alle acht Werte einer Zeile: Das Array of Structs braucht eine Zeile (1.000 Fehlzugriffe), das Struct of Arrays acht (8.000). Die Quote-Aufgabe liest drei der vier Spalten der heißen Gruppe, der Hybrid ist also gut, aber nicht der beste. Welche Anordnung man wählt, hängt davon ab, wie oft jede Aufgabe läuft, und genau das misst die Mischung.

Messen Sie, bevor Sie neu anordnen

Eine Anordnung, die die Scans gewinnt, kann die Lookups um den Faktor acht verlieren. Bevor Sie die Datenstruktur eines echten Programms ändern, notieren Sie, welche Aufgaben sie lesen und wie oft, und zählen Sie die Fehlzugriffe jeder Anordnung wie hier.

main.pyPython

def study(bars):    n_rows = min(int(bars.shape[0]), 4000)    misses = {}    accesses = 0    for job, reads in WORKLOADS.items():        rows = sampled_rows(n_rows) if job == "lookup" else None        misses[job] = compare_layouts(LAYOUTS, n_rows, reads, rows)        accesses += len(reads) * (len(rows) if rows is not None else n_rows)    mixed = {name: sum(misses[job][name] for job in WORKLOADS) for name in LAYOUTS}    best = best_layout(mixed)    return {"mixed": mixed, "mixed_best": best, "reduction": mixed["aos"] / mixed[best],            "ns": {name: time_ns(accesses, mixed[name]) for name in LAYOUTS}}out = study(load_bars())print(out["mixed"], "->", out["mixed_best"])print(round(out["reduction"], 2), "times fewer misses than the array of structs")print({name: round(ns / 1000) for name, ns in out["ns"].items()}, "microseconds")

{'aos': 9000, 'soa': 10000, 'hybrid': 6000} -> hybrid
1.5 times fewer misses than the array of structs
{'aos': 735, 'soa': 814, 'hybrid': 498} microseconds

Zusammengezählt hat das Array of Structs 9.000 Fehlzugriffe, das Struct of Arrays 10.000 und der Hybrid 6.000. Der Hybrid gewinnt keine Aufgabe klar und verliert keine schlimm: Die Scans und Quotes kosten das Doppelte dessen, was das Struct of Arrays zahlt, die Lookups das Doppelte dessen, was das Array of Structs zahlt, und die Mischung bevorzugt die Anordnung, die nie schrecklich ist. Im Latenzmodell sind das 498 µs gegen 735 µs für das Array of Structs: 1,5-mal weniger Fehlzugriffe und ein Drittel weniger Zeit. Das ist der Beweis, den das Abschlussprojekt verlangt, und er gilt nur für diese Mischung von Aufgaben.

DefinitionHeiße und kalte Spalten

Die heißen Spalten sind die, die die meisten Aufgaben zusammen lesen (hier Bid, Ask und die beiden Größen); die kalten werden selten gelesen (Zeitstempel, Preis, Größe, Flags). Hält man jede Sorte zusammen, berühren die häufigen Aufgaben wenige Zeilen, und die seltenen bleiben günstig.

Was die echten Daten sagen4.000 Ticks mit 8 Spalten, 32-KB-Cache mit 8 Wegen, Treffer 1 ns, Fehlzugriff 80 ns

Preis-Scan, Struct of Arrays500Fehler (Array of Structs: 4.000)

Lookup von 1.000 Ticks, Array of Structs1,000Fehler (Struct of Arrays: 8.000)

Die Mischung, hybride Anordnung6,000Fehler (9.000 und 10.000 bei den anderen)

Reduktion gegenüber dem Array of Structs1.5×weniger Fehler (735 µs → 498 µs)

Fehler der Mischung nach Anordnung

Struct of Arrays10000

Array of Structs9000

Hybrid6000

Was Sie bauen werden

Das Labor folgt der Lektion: die Adresse eines Werts in jeder Anordnung, die Spur einer Aufgabe, die Fehlzugriffe einer Aufgabe in einer Anordnung und in allen, die beste Anordnung, die Zeit einer Aufgabe und die Studie der Tick-Tabelle mit dem Beweis der Mischung.

Funktion · FrageBaut auf
address(groups, row, col, n_rows)Wo liegt dieser Wert im Speicher?Einfache Arithmetik
workload_trace(groups, n_rows, reads, rows)Welche Adressen berührt die Aufgabe?address
layout_misses(groups, n_rows, reads, rows)Wie viele Fehler in dieser Anordnung?workload_tracecount_misses
compare_layouts(layouts, n_rows, reads, rows)Und in jeder Anordnung?layout_misses
best_layout(misses)Welche gewinnt?Einfache Arithmetik
time_ns(accesses, misses)Was kostet es an Zeit?Einfache Arithmetik
study(bars)Welche Anordnung gewinnt die Mischung der Aufgaben?compare_layoutsbest_layouttime_ns

Schnelltest

Eine Aufgabe liest nur die Preisspalte von 4.000 Zeilen. Im Struct of Arrays belegt jeder Wert 8 Byte, und eine Zeile fasst 64. Wie viele Zeilen berührt sie?

Wähle eine Antwort.

Nächste Fähigkeit: Die Speicherseite der Leistung ist geschafft. Die nächsten Fähigkeiten des Optimierungspfads wenden sich dem Prozessor zu: dieselbe Operation auf viele Werte gleichzeitig in Vektorregistern auszuführen und Daten ohne Sperren zwischen Kernen zu teilen.

Lab: Was bewertet wird

7 Aufgaben · 100 Pkt.

Die Adresse eines Werts20 Pkt.
Die Spur einer Aufgabe15 Pkt.
Die Fehlzugriffe einer Aufgabe10 Pkt.
Jede Anordnung10 Pkt.
Die beste Anordnung5 Pkt.
Die Zeit einer Aufgabe10 Pkt.
Die Studie mit der SPY-Tabelle30 Pkt.

def address(groups, row, col, n_rows, elem_bytes=ELEM_BYTES): base = 0 for group in groups: if col in group: return base + (row * len(group) + group.index(col)) * elem_bytes base += n_rows * len(group) * elem_bytes raise ValueError("column %d is in no group" % col)print(address([[0, 1, 2]], 2, 1, 10))print(address([[0], [1], [2]], 2, 1, 10))print(address([[1, 2], [0]], 3, 0, 10))

def workload_trace(groups, n_rows, reads, rows): return [address(groups, row, col, n_rows) for row in rows for col in reads]def layout_misses(groups, n_rows, reads, rows=None): rows = range(n_rows) if rows is None else rows return count_misses(workload_trace(groups, n_rows, reads, rows))def compare_layouts(layouts, n_rows, reads, rows=None): return {name: layout_misses(groups, n_rows, reads, rows) for name, groups in layouts.items()}def best_layout(misses): return min(misses, key=misses.get)def time_ns(accesses, misses, hit_ns=HIT_NS, miss_ns=MISS_NS): return (accesses - misses) * hit_ns + misses * miss_nsprint(workload_trace([[0, 1]], 4, [1, 0], [2]))for job, reads in WORKLOADS.items(): rows = sampled_rows(4000) if job == "lookup" else None result = compare_layouts(LAYOUTS, 4000, reads, rows) print(job, result, "->", best_layout(result))

def study(bars): n_rows = min(int(bars.shape[0]), 4000) misses = {} accesses = 0 for job, reads in WORKLOADS.items(): rows = sampled_rows(n_rows) if job == "lookup" else None misses[job] = compare_layouts(LAYOUTS, n_rows, reads, rows) accesses += len(reads) * (len(rows) if rows is not None else n_rows) mixed = {name: sum(misses[job][name] for job in WORKLOADS) for name in LAYOUTS} best = best_layout(mixed) return {"mixed": mixed, "mixed_best": best, "reduction": mixed["aos"] / mixed[best], "ns": {name: time_ns(accesses, mixed[name]) for name in LAYOUTS}}out = study(load_bars())print(out["mixed"], "->", out["mixed_best"])print(round(out["reduction"], 2), "times fewer misses than the array of structs")print({name: round(ns / 1000) for name, ns in out["ns"].items()}, "microseconds")