構造体の配列と配列の構造体

ティック表はメモリ上で2通りに置けて、どちらが正しいかは読み方で決まります。行ごとに置いた表で1列だけを走査すると、使う量の5倍のメモリを読み込みます。列ごとに分けた表で行全体を読むのも、逆向きに同じだけ無駄です。この講義では両方のレイアウトのミスを数え、その数に選ばせます。

メモリは長いバイト列なので、2次元の表は平らに並べなければなりません。自然な方法が2つあります。構造体の配列では、1日の5つの値（始値、高値、安値、終値、出来高）をまとめて置き、次の日の5つ、というように続けます。配列の構造体では、まず始値がすべて、次に高値がすべて、というように並べます。値もプログラムも同じですが、アドレスが変わります。

値のアドレスは、行と列から決まります。AoSでは値の番号は「行 × 列数 + 列」、SoAでは「列 × 行数 + 行」です。float64なら8バイトを掛けます。次のコードは、100日×5列の表の最初の4日の終値のアドレスを表示します。

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. 1AoSでは次の行はn_cols個先なので、連続する終値は5個（40バイト）離れます。

AoSでは連続する日の終値は40バイト離れ、SoAでは8バイト、つまり隣同士で並びます。これは、このスキルの最初のトピックで見た「順に読む」ケースそのものです。

終値の平均を取ると、表の1列を読みます。この読み出しをアドレスのリストにし、前のトピックで作ったキャッシュに通して、1,000日分のミスを数えます。最後に表示する数が有効率です。

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

SoAの走査は1,000個の値で125回ミスし、8個に1回で無駄がありません。AoSの走査は625回、つまり5倍ミスし、読み込んだバイトのうち終値は20%だけです。残り80%は平均が見向きもしない始値・高値・安値・出来高で、有用なラインをキャッシュから押し出します。

多くのティック処理は別の問いを立てます。このティックの価格、数量、売買方向をまとめて欲しい、というものです。これは行の全部の値を読みます。AoSでは行全体が40バイトのひとかたまりで、1〜2ラインに収まります。SoAでは5つの値が5つの別々の配列にあるので、1行ごとに5ラインを開きます。コードは7行に1行を読み、ミスを数えます。

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

今度はAoSが3倍有利で、ミスは214回対625回です。列の走査では5倍悪かったレイアウトが、行の読み出しでは3倍よくなります。どちらかが常に最良なのではなく、それぞれが1つの読み方に最適なのです。

実際のプログラムは両方の読み方をするので、選択は割合で決まります。各レイアウトについて、負荷のミスを合計します。列の走査回数×列のミス＋行の読み出し回数×行のミスです。合計が小さいレイアウトが勝ち、同点ならAoSです。次のコードは同じ表で4つの割合を試します。

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

ラボは講義の順に進みます。2つのレイアウト、2種類の読み出し、比較、負荷に応じた選択、有効率、そして実際のSPYの表での研究です。

• 関数 · 問い前提
• address(layout, row, col, n_rows, n_cols)この値はどこにあるか？単純な算術
• scan_column(layout, col, n_rows, n_cols)列の走査はどのアドレスを読むか？address
• scan_rows(layout, rows, n_rows, n_cols)行の読み出しはどのアドレスに触れるか？address
• compare(n_rows, n_cols, col, rows)各レイアウトで各読み出しは何回ミスするか？scan_columnscan_rows
• best_layout(...)この負荷にはどのレイアウトが合うか？compare
• useful_fraction(layout, col, n_rows, n_cols)読み込んだもののうちどれだけ使われるか？scan_column
• study(bars)SPYの表にはどのレイアウトが合うか？comparebest_layout

次のトピック：レイアウトは1つの表のストライドを決めました。走査順序とループタイリングでは、表は行列になり、ループの順序を選び、さらにループをタイルに分けて、行列の一区画を使っている間キャッシュに残るようにします。