時間的局所性とワーキングセット

キャッシュが役に立つのは再び読むデータだけで、大事なのはそれがどれだけ早いかです。この講義ではそれを再利用距離という1つの数で測り、あらゆるキャッシュサイズのヒット率を一度に予測します。ループがほんの少し大きすぎて収まらなくなる崖も含めてです。

これまでの2つのトピックは、ラインがどこに入るかの話でした。このトピックは、ラインがいつ戻ってくるかの話です。価格を読み、少し作業して、少し後に同じ価格をもう一度読むプログラムは、時間的局所性を示しています。間隔が短いほど、そのラインがまだキャッシュにある可能性が高まります。机の上の本を思い浮かべてください。1分前に使った本はまだそこにあり、先月使った本は棚に戻っています。

ライン5を続けて2回読むと距離は0です。1, 2, 3, 1という並びでは、最後の読み出しの距離は2で、間にライン2と3が来ています。ライン1の2回の読み出しの間にライン2を10回読んでも、1ラインと数えます。コードは、最後に使った順（最近のものが末尾）にラインのリストを保持します。ラインが再び来たとき、リストでそのラインより後ろにあるものが、それ以降に使われたラインそのものです。

def reuse_distances(lines):    stack = []    out = []    for line in lines:        if line in stack:            position = stack.index(line)            out.append(len(stack) - 1 - position)1            stack.pop(position)        else:            out.append(None)        stack.append(line)    return outprint(reuse_distances([1, 2, 3, 1, 2, 1, 1]))

[None, None, None, 2, 2, 1, 0]

1. 1リストでこのラインより後ろにあるのが、前回の読み出し以降に使われたラインそのもので、その数が距離です。

ここに役に立つ事実があります。C個のラインを持ち、ライン番号に関係なく最も長く使われていないものを追い出すキャッシュを考えます。いつでも、最近使われた異なるC個のラインを保持しています。読み出しがヒットするのは、そのラインがその中にあるとき、つまり最後に使われてから読まれた異なるラインがC個未満のときです。言い換えると、再利用距離がCより小さいときにヒットします。

次のコードでこの主張を確かめます。容量1〜4のLRUキャッシュをシミュレートし、同時にキャッシュなしで距離だけからヒット率を計算します。2つの列は一致します。距離は一度計算するだけで、どのキャッシュサイズのヒット率も求まります。

def lru_hit_rate(lines, capacity):    cache = []    hits = 0    for line in lines:        if line in cache:            hits += 1            cache.remove(line)        elif len(cache) >= capacity:            cache.pop(0)        cache.append(line)    return hits / len(lines)def hit_rate_from_distances(distances, capacity):    hits = sum(1 for d in distances if d is not None and d < capacity)    return hits / len(distances)lines = [1, 2, 3, 1, 2, 3, 4, 1, 2, 3]d = reuse_distances(lines)for capacity in (1, 2, 3, 4):    print(capacity, "lines:", round(lru_hit_rate(lines, capacity), 3), round(hit_rate_from_distances(d, capacity), 3))1

1 lines: 0.0 0.0
2 lines: 0.0 0.0
3 lines: 0.3 0.3
4 lines: 0.6 0.6

1. 1両方の列で同じ数になります。距離だけで、どのキャッシュサイズのヒット率も予測できます。

一連の読み出しのワーキングセットは、それらが触れる異なるラインの集合です。ワーキングセットがキャッシュに収まれば、プログラムはほぼ全部キャッシュから動きます。わずかに大きいだけでも、LRUは完全に失敗しえます。48ラインを順に読むループを3回繰り返す場合を考えます。各ラインは他の47ラインの後に再び読まれるので、再利用距離はすべて47です。したがって47ライン以下のキャッシュでは一度もヒットせず、48ラインあれば最初の走査以降のすべての読み出しがヒットします。

def sweep_lines(n_lines, passes):    return list(range(n_lines)) * passeslines = sweep_lines(48, 3)for capacity in (16, 32, 47, 48):    print(capacity, "lines:", round(lru_hit_rate(lines, capacity), 3))

16 lines: 0.0
32 lines: 0.0
47 lines: 0.0
48 lines: 0.667

単純な方法で計算する移動平均は、毎日直近20個の値を読みます。前日に読んだ20個のうち19個を読み直すことになり、時間的局所性がとても高いプログラムです。次のコードは、最初の600個の終値で読まれるアドレスを作ってラインに変換し、距離、4つのキャッシュサイズでのヒット率、連続する20回の読み出しのワーキングセットを測ります。

def rolling_mean_trace(n, window, elem_bytes):    trace = []    for end in range(window - 1, n):        for position in range(end - window + 1, end + 1):            trace.append(position * elem_bytes)    return tracedef working_set(lines, window):    return max(len(set(lines[i:i + window])) for i in range(len(lines) - window + 1))lines = [address // 64 for address in rolling_mean_trace(600, 20, 8)]d = reuse_distances(lines)print(len(lines), "reads from", len(set(lines)), "lines")for capacity in (1, 2, 4, 8):    print(capacity, "lines:", round(hit_rate_from_distances(d, capacity), 3))print("working set of 20 reads:", working_set(lines, 20), "lines")

11620 reads from 75 lines
1 lines: 0.831
2 lines: 0.831
4 lines: 0.994
8 lines: 0.994
working set of 20 reads: 4 lines

1ラインあるだけで読み出しの83%がヒットします。配列の次の値が、いま読んだラインに入っているからです。4ラインなら99.4%に達します。データ全体の75ラインが収まる必要はまったくありません。20回の読み出しのワーキングセットは4ラインだけなので、ごく小さなキャッシュで足ります。データの大きさとワーキングセットの大きさの違いです。

ラボでは、上の部品に加えて、あるヒット率に必要な最小のキャッシュを見つける関数を作り、最後に実際のSPYの終値での研究を行います。

• 関数 · 問い前提
• reuse_distances(lines)各ラインはどれだけ早く再び読まれるか？最終使用順のリスト
• lru_hit_rate(lines, capacity)シミュレートしたLRUキャッシュのヒット率は？LRU順のライン
• hit_rate_from_distances(distances, capacity)キャッシュなしで同じヒット率は？reuse_distances
• working_set(lines, window)ひとまとまりの読み出しは何ラインに触れるか？スライディングウィンドウ
• capacity_for(lines, target)キャッシュはどこまで小さくできるか？reuse_distanceshit_rate_from_distances
• rolling_mean_trace(n, window, elem_bytes)単純な移動平均はどのアドレスを読むか？単純な算術
• study(bars)SPYの終値の移動平均はどれだけ局所的か？rolling_mean_tracecapacity_for

次のトピック：レイアウトがトレースになり、トレースがヒットとミスになる流れが分かりました。構造体の配列と配列の構造体では、それを使ってティック表のレイアウトを選び、両方のレイアウトで列の読み出しと行全体の読み出しを比べます。