総合課題：ティック表のレイアウトを見直しミス減少を証明する

このスキルで学んだことが、1つのティックのテーブルに集まります。8つの列、それを異なる読み方で読む3つの仕事、メモリ上の3つの配置です。各値のアドレスをモデル化し、自作のキャッシュで各仕事のミスを数え、レイテンシモデルでコストを出して、どの配置が勝つかを示します。すべての仕事に勝つ配置はなく、ハイブリッドが混合で勝ち、構造体の配列よりミスが1.5分の1になります。

ティックのテーブルは、8バイトの列が8つ（タイムスタンプ、買い気配と売り気配の価格と数量、約定価格、その数量、いくつかのフラグ）です。1行はちょうど64バイトで、キャッシュラインの大きさと同じです。このテーブルを3つの仕事が読みます。スキャンは移動平均のために全行の価格列を読みます。気配の仕事は板を作るために全行の買い気配・売り気配・買い数量を読みます。ルックアップはデバッガやリプレイのように、テーブル全体から選んだ1,000行の完全なティックを読みます。第1トピックのメモリには階層があり、第2トピックにはライン64バイトがあり、第5トピックでは表の2つの配置、構造体の配列（行の値が一緒）と配列の構造体（列ごと）を学びました。ここに第3の道、ホットな気配の列をまとめ、コールドな列をまとめるハイブリッドが加わります。

3つの配置は1つの考え方です。配置とは列グループのリストです。1つのグループの値は行ごとに並び、グループは順に続きます。全列を入れた1グループが構造体の配列、列ごとに1グループが配列の構造体、4列ずつの2グループが今回のハイブリッドです。したがって1つの関数で、どの配置でも任意の値のアドレスが分かります。その列を含むグループより前のグループを飛ばし、グループ内で row * len(group) + position 個進みます。

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

1. 11グループは n_rows * len(group) * elem_bytes バイトを占め、次のグループはその直後から始まります。

3つの結果を手で確かめましょう。3列の1グループなら、行2・列1は値番号 2 × 3 + 1 = 7 で、56バイト目です。列ごとのグループなら、列1は列0の10個の値の後の80バイト目から始まり、行2はそこから16バイト先の96です。ハイブリッド [[1, 2], [0]] では列0のグループは2番目で、2値×10行（160バイト）の後に来て、行3はそこから24バイト先の184です。

仕事とは、訪れる各行について読む列のリストです。そのトレースは、行を順に、それらの列のアドレスを並べたものです。キャッシュがトレースをミスに変え、第1トピックのレイテンシモデルがミスを時間に変えます（ヒット1 ns、ミス80 ns）。比較は配置についてのループで、証明は最小の数です。講義の3つの仕事を4,000ティックで実行すると、最良の配置が仕事によって変わることが分かります。

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

スキャンは1列だけ欲しいので、配列の構造体は1ラインに価格8個を詰められます（500ミス）が、構造体の配列は読み込む各ラインの8分の7を無駄にします（4,000ミス）。ポイントルックアップは1行の8つの値すべてが欲しいので、構造体の配列は1ライン（1,000ミス）、配列の構造体は8ライン（8,000ミス）です。気配はホットグループの4列のうち3列を読むので、ハイブリッドは良いものの最良ではありません。どの配置を選ぶかは各仕事の頻度で決まり、それを測るのが混合です。

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

合計すると、構造体の配列は9,000回、配列の構造体は10,000回、ハイブリッドは6,000回ミスします。ハイブリッドはどの仕事でも圧勝せず、どの仕事でも大負けしません。スキャンと気配では配列の構造体の2倍、ルックアップでは構造体の配列の2倍のコストですが、混合では決して酷くない配置が有利です。レイテンシモデルでは構造体の配列の735 µsに対して498 µs、ミスは1.5分の1、時間は3分の1の削減です。これが最終課題の求める証明であり、この仕事の組み合わせに対してだけ成り立ちます。

ラボは講義の順に進みます。任意の配置での値のアドレス、仕事のトレース、1つの配置と全配置での仕事のミス、最良の配置、仕事の時間、そして混合の証明を含むティックテーブルの研究です。

• 関数 · 問い前提
• address(groups, row, col, n_rows)この値はメモリのどこにあるか？単純な算術
• workload_trace(groups, n_rows, reads, rows)仕事はどのアドレスに触れるか？address
• layout_misses(groups, n_rows, reads, rows)この配置でミスは何回か？workload_tracecount_misses
• compare_layouts(layouts, n_rows, reads, rows)全配置では？layout_misses
• best_layout(misses)どれが勝つか？単純な算術
• time_ns(accesses, misses)時間ではいくらか？単純な算術
• study(bars)仕事の混合ではどの配置が勝つか？compare_layoutsbest_layouttime_ns

次のスキル：性能のメモリ側は完了です。最適化トラックの次のスキルはプロセッサ側に移ります。ベクトルレジスタで同じ演算を多数の値に一度に行うことと、ロックなしでコア間でデータを共有することです。