アロケータとメモリプール

プログラムが作るリストのノード、木のノード、注文はすべてアロケータから来ており、そのアドレスを決めるのもアロケータです。汎用の malloc は、ヘッダと、プログラム自身の一時オブジェクトのおかげで小さなオブジェクトを散らばらせ、プールは詰めて並べます。この講義では両方をモデル化し、同じリストをプールから走査するとキャッシュミスが3.3分の1になることを示します。

プログラムがオブジェクト用のメモリを要求すると、アロケータがブロックを渡してアドレスを返します。汎用のアロケータは各ブロックの大きさを覚えておく必要があるので、ブロックの前に小さなヘッダを置き、どんな値でも入れられるようにブロックを16バイトの倍数に切り上げます。最も単純なモデルはメモリを再利用しません。各要求は直前のブロックのすぐ後ろにブロックを取り、プログラムはヘッダのすぐ後ろのアドレスを受け取ります。

def round_up(n, align):    return -(-n // align) * aligndef malloc_addresses(sizes, header=HEADER_BYTES, align=ALIGN):    addresses = []    start = 0    for size in sizes:        addresses.append(start + header)1        start += round_up(size + header, align)    return addressesprint(malloc_addresses([24, 100, 24]))print([round_up(size + 16, 16) for size in (24, 100)])

[16, 64, 192]
[48, 128]

1. 1ブロックは要求サイズ＋ヘッダを16の倍数に切り上げたもので、24バイトには48バイト、100バイトには128バイトのブロックが必要です。

24バイトのノード（終値、出来高、次ポインタが各8バイト）は必要量の2倍の48バイトのブロックを受け取り、100バイトの一時オブジェクトは128バイトを受け取ります。3つのアドレスは16、64、192です。2つ目の要求は1つ目の48バイトのブロックの後ろ、3つ目は2つ目の128バイトのブロックの後ろから始まります。

実際のコードは、リストを真空の中で作るわけではありません。2つのノードの間で、メッセージを整形したり、キーを作ったり、行を解析したりし、その一時オブジェクトも割り当てられます。メモリを再利用しない単純なアロケータでは、それらがノードの間に入り込みます。次の最初の関数は要求の計画（ノード1つに100バイトの一時オブジェクト3つ）を作り、2つ目はその計画を実行してノードのアドレスだけを残します。比較のため、固定スロットを次々に渡すプールも書きます。

def alloc_plan(n_nodes, garbage_per_node, garbage_bytes, node_bytes):    sizes = []    node_index = []    for _ in range(n_nodes):        node_index.append(len(sizes))        sizes.append(node_bytes)        sizes.extend([garbage_bytes] * garbage_per_node)    return sizes, node_indexdef node_addresses(n_nodes, garbage_per_node, garbage_bytes, node_bytes):    sizes, node_index = alloc_plan(n_nodes, garbage_per_node, garbage_bytes, node_bytes)    addresses = malloc_addresses(sizes)    return [addresses[i] for i in node_index]def pool_addresses(n, slot_bytes, base=0):    return [base + i * slot_bytes for i in range(n)]print(node_addresses(3, 3, 100, 24))print(node_addresses(3, 0, 100, 24))print(pool_addresses(3, 24))

[16, 448, 880]
[16, 64, 112]
[0, 24, 48]

ノードあたり3つの一時オブジェクトがあると、ノードは432バイト離れます（ノード48、ゴミ3 × 128）。一時オブジェクトがなければ48バイト、プールでは、ヘッダもゴミもなくノードの大きさそのものの24バイトです。64バイトのラインには、散らばったノードなら1つ、ヘッダだけなら1.3個、プールなら2.7個が入ります。ここで3,000個のノードを、各ノードの最初と最後のバイトを読みながら、これまでのトピックのキャッシュで走査します。

def traversal_misses(addresses, node_bytes):    cache = Cache()    for address in addresses:        cache.access(address)        cache.access(address + node_bytes - 1)    return cache.missesn = 3000for name, addresses in (("scattered", node_addresses(n, 3, 100, 24)), ("headers only", node_addresses(n, 0, 100, 24)), ("pool", pool_addresses(n, 24))):    print(name, traversal_misses(addresses, 24), "misses, last node at", addresses[-1] // 1024, "KB")

scattered 3750 misses, last node at 1265 KB
headers only 2250 misses, last node at 140 KB
pool 1125 misses, last node at 70 KB

散らばったリストは3,750回ミスし、1,265 KBに広がります。まったく同じ3,000個のノードを持つプールは、70 KBで1,125回のミスで、3.3分の1です。ノードはL2キャッシュにも収まるほどです。プログラム、データ、走査の順序は同じで、変わったのはアドレスだけです。

ラボは講義の順に進みます。切り上げ、単純な汎用アロケータ、プール、一時オブジェクトを含む要求の計画、ノードのアドレス、走査のミス数、そしてSPYの日のリストでの研究です。

• 関数 · 問い前提
• round_up(n, align)n を倍数に切り上げると？単純な算術
• malloc_addresses(sizes)汎用アロケータは各ブロックをどこに置くか？round_up
• pool_addresses(n, slot_bytes)プールは？単純な算術
• alloc_plan(...)プログラムはどんな要求をするか？単純な算術
• node_addresses(...)ノードはどこに置かれるか？alloc_planmalloc_addresses
• traversal_misses(addresses, node_bytes)走査は何回ミスするか？Cache
• study(bars)SPYのリストでプールはどれだけ節約するか？node_addressespool_addressestraversal_misses

次のトピック：ここまでのコストはすべてメモリから来ていました。このスキルの最後のハードウェア効果は、プロセッサの予想から来ます。分岐予測では、予測器をモデル化し、if を含むループでその予測ミスを数えて、同じループがソート済みのデータで速くなる理由を見ます。