Array of Structs gegen Struct of Arrays

Eine Tick-Tabelle kann auf zwei Arten im Speicher liegen, und die richtige hängt davon ab, wie Sie sie lesen. Eine Spalte einer zeilenweise gespeicherten Tabelle zu durchlaufen lädt fünfmal so viel Speicher, wie Sie nutzen; ganze Zeilen aus getrennten Spalten zu lesen verschwendet umgekehrt genauso viel. Diese Lektion zählt die Fehlzugriffe beider Layouts und lässt die Zahlen entscheiden.

Der Speicher ist eine lange Reihe von Bytes, eine zweidimensionale Tabelle muss also flachgelegt werden. Es gibt zwei natürliche Wege. In einem Array of Structs liegen die fünf Werte eines Tages (Eröffnung, Hoch, Tief, Schluss, Volumen) zusammen, dann die fünf des nächsten Tages und so weiter. In einem Struct of Arrays kommen zuerst alle Eröffnungen, dann alle Hochs und so weiter. Werte und Programm sind gleich, nur die Adressen unterscheiden sich.

Die Adresse eines Werts folgt aus seiner Zeile und Spalte. Im AoS ist die Wertnummer Zeile mal Spaltenzahl plus Spalte. Im SoA ist sie Spalte mal Zeilenzahl plus Zeile. Mit 8 Byte für einen float64 multiplizieren. Der Code unten gibt die Adressen der Schlusskurse der ersten vier Tage in einer Tabelle mit 100 Tagen und 5 Spalten aus.

def address(layout, row, col, n_rows, n_cols, elem_bytes=8):    if layout == "aos":        return (row * n_cols + col) * elem_bytes1    return (col * n_rows + row) * elem_bytesclose = 3print("aos:", [address("aos", row, close, 100, 5) for row in range(4)])print("soa:", [address("soa", row, close, 100, 5) for row in range(4)])

aos: [24, 64, 104, 144]
soa: [2400, 2408, 2416, 2424]

1. 1Im AoS liegt die nächste Zeile n_cols Werte weiter, aufeinanderfolgende Schlusskurse sind also 5 Werte (40 Byte) auseinander.

Im AoS liegen die Schlusskurse aufeinanderfolgender Tage 40 Byte auseinander. Im SoA sind es 8 Byte, einer direkt nach dem anderen, genau das Lesen in Reihenfolge aus dem ersten Thema dieser Fähigkeit.

Der Mittelwert der Schlusskurse liest eine Spalte der Tabelle. Wir machen aus diesem Lesen eine Adressliste, schicken sie durch den Cache aus den letzten Themen und zählen die Fehlzugriffe für 1.000 Tage. Die letzte ausgegebene Zahl ist der nützliche Anteil.

def scan_column(layout, col, n_rows, n_cols):    return [address(layout, row, col, n_rows, n_cols) for row in range(n_rows)]for layout in ("aos", "soa"):    misses = count_misses(scan_column(layout, 3, 1000, 5))    print(layout, "misses:", misses, "- useful share:", round(1000 * 8 / (misses * 64), 3))

aos misses: 625 - useful share: 0.2
soa misses: 125 - useful share: 1.0

Der SoA-Durchlauf verfehlt 125-mal bei 1.000 Werten, ein Fehlzugriff pro acht Werte und nichts verschwendet. Der AoS-Durchlauf verfehlt 625-mal, fünfmal so oft, und nur 20 % der geladenen Byte sind Schlusskurse. Die übrigen 80 % sind Eröffnungen, Hochs, Tiefs und Volumina, die der Mittelwert nie ansieht und die nützliche Zeilen aus dem Cache verdrängen.

Viele Tick-Programme stellen eine andere Frage: Gib mir für diesen Tick Preis, Größe und Seite zusammen. Das liest jeden Wert einer Zeile. Im AoS ist die ganze Zeile ein 40-Byte-Block in einer oder zwei Cache-Zeilen. Im SoA liegen die fünf Werte in fünf verschiedenen Arrays, jede Zeile öffnet also fünf Cache-Zeilen. Der Code liest jede siebte Zeile und zählt die Fehlzugriffe.

def scan_rows(layout, rows, n_rows, n_cols):    return [address(layout, row, col, n_rows, n_cols) for row in rows for col in range(n_cols)]rows = list(range(0, 1000, 7))for layout in ("aos", "soa"):    print(layout, "misses:", count_misses(scan_rows(layout, rows, 1000, 5)))

aos misses: 214
soa misses: 625

Jetzt gewinnt AoS mit dem Faktor drei: 214 Fehlzugriffe gegen 625. Das Layout, das beim Spaltendurchlauf fünfmal schlechter war, ist beim Zeilenlesen dreimal besser. Keines der Layouts ist das beste; jedes ist für eine Art des Lesens das beste.

Ein echtes Programm macht beide Arten des Lesens, die Wahl hängt also von der Mischung ab. Addieren Sie für jedes Layout die Fehlzugriffe der Last: Spaltendurchläufe mal Spaltenfehlzugriffe plus Zeilenlesen mal Zeilenfehlzugriffe. Das Layout mit der kleineren Summe gewinnt, ein Gleichstand geht an AoS. Der Code unten probiert vier Mischungen an derselben Tabelle.

def compare(n_rows, n_cols, col, rows):    out = {}    for layout in ("aos", "soa"):        out[layout] = {            "column": count_misses(scan_column(layout, col, n_rows, n_cols)),            "rows": count_misses(scan_rows(layout, rows, n_rows, n_cols)),        }    return outdef best_layout(n_column_scans, n_row_reads, n_rows, n_cols, col, rows):    counts = compare(n_rows, n_cols, col, rows)    totals = {layout: n_column_scans * counts[layout]["column"] + n_row_reads * counts[layout]["rows"] for layout in counts}    return "soa" if totals["soa"] < totals["aos"] else "aos"rows = list(range(0, 1000, 7))for scans, reads in ((1, 4), (1, 2), (1, 1), (4, 1)):    print(scans, "column scans per", reads, "row reads:", best_layout(scans, reads, 1000, 5, 3, rows))

1 column scans per 4 row reads: aos
1 column scans per 2 row reads: aos
1 column scans per 1 row reads: soa
4 column scans per 1 row reads: soa

Das Labor folgt der Lektion: die zwei Layouts, die zwei Arten des Lesens, der Vergleich, die Wahl für eine Last, der nützliche Anteil und die Studie an der echten SPY-Tabelle.

• Funktion · FrageBaut auf
• address(layout, row, col, n_rows, n_cols)Wo liegt dieser Wert?Einfache Arithmetik
• scan_column(layout, col, n_rows, n_cols)Welche Adressen liest ein Spaltendurchlauf?address
• scan_rows(layout, rows, n_rows, n_cols)Welche Adressen berührt ein Zeilenlesen?address
• compare(n_rows, n_cols, col, rows)Wie viele Fehlzugriffe kostet jedes Lesen in jedem Layout?scan_columnscan_rows
• best_layout(...)Welches Layout passt zu dieser Last?compare
• useful_fraction(layout, col, n_rows, n_cols)Wie viel vom Geladenen wird genutzt?scan_column
• study(bars)Welches Layout passt zur SPY-Tabelle?comparebest_layout

Nächstes Thema: Das Layout hat die Schrittweite einer Tabelle bestimmt. In Durchlaufreihenfolge und Loop Tiling ist die Tabelle eine Matrix, Sie wählen die Reihenfolge der Schleifen und zerlegen sie dann in Kacheln, damit ein Block der Matrix im Cache bleibt, solange er genutzt wird.