メモリは一つではない

目標

コンピューターの仕組みは、抽象的に学ぶと何も残りません。このPodの本物のCPUで、直接測ってみます。

ここで測る数字は、あとで「なぜこのコードは遅いのか」「なぜ計算が1ウォンずれるのか」といった疑問の答えになります。

見る場所

grep -m1 'model name' /proc/cpuinfo
cat /sys/devices/system/cpu/cpu0/cache/index0/size
cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
nproc

時間を測るとき

Pythonは遅いです。そのため、読み取りの回数を固定して、配列のサイズだけを変えることで、Pythonの遅さが相殺され、メモリの違いだけが残ります。

また、ウォームアップを1回は必ず行ってください。最初の実行には、配列を作るコストが混ざります。

ステップ

CPUとキャッシュ → 01-cpu.txt
キャッシュ外のレイテンシ → 02-latency.txt
キャッシュライン → 03-line.md
0.1 + 0.2 → 04-float.txt
足す順序 → 05-order.txt
エンディアン → 06-endian.txt
2の補数 → 07-int.txt
整理 → 08-notes.md

参考

ステップ2の数字は、マシンごとに違います。絶対値ではなく倍率を見てください。キャッシュの内と外で2倍以上の差が出ていれば、正しく測れています。

このCPUとキャッシュを読み取る

このマシンのCPU名とキャッシュ階層(L1/L2/L3のサイズとラインサイズ)を取り出して、01-cpu.txtに残してください。

CPUはgrep -m1 'model name' /proc/cpuinfoです。キャッシュは、/sys/devices/system/cpu/cpu0/cache/index*/の下にあるlevel、type、size、coherency_line_sizeを読めばわかります。

キャッシュが階段のように何段にもなっていることと、レベルが上がるほど大きくなり遅くなることを、目で確認するステップです。

キャッシュの外に出たときの遅さを測る

読み取りの回数は同じにして、配列のサイズだけを変えながら、1回の読み取りにかかる時間を測り、02-latency.txtに残してください。4KB・1MB・64MBの3つで十分です。

核心は、読み取りの回数を固定することです。そうすれば、Python自体の遅さが相殺され、メモリの違いだけが残ります。

import array, random, time
def bench(elems, idx):
    a = array.array('i', [1]) * elems
    for i in idx[:1000]: a[i]        # 워밍업
    t = time.perf_counter()
    s = 0
    for i in idx: s += a[i]
    return (time.perf_counter() - t) / len(idx) * 1e9

ランダムなインデックスを30万個あらかじめ作り、3つの配列に同じ回数だけ使ってください。キャッシュの内と外で、2倍以上の差が出る必要があります。

順番に読むと速い理由を計算する

キャッシュラインのサイズを確認し、int32の配列なら1ラインに何個載るかを計算して、03-line.mdに書いてください。

ラインサイズはステップ1で見ました(たいてい64B)。int32は4バイトなので、1ラインに16個です。

メモリは、1バイトずつではなくライン丸ごと取得します。そのため、配列を順番に読むと、一度取得したラインから16個をタダで使えます。ランダムに読むと、毎回新しいラインを取得して、残りの15個は捨てます。

同じデータを扱うのに、アクセス順序を変えるだけで数倍速くなる理由がこれです。

0.1 + 0.2は0.3ではないことを確認する

0.1 + 0.2の結果と== 0.3の判定、そして0.1を小数点以下20桁まで出力した値を、04-float.txtに残してください。

print(f"{0.1:.20f}")です。0.1は2進数でぴったり表せません。10進数で1/3を書き切れないのと同じです。

そのため、お金をfloatで扱ってはいけません。整数(ウォン単位)か十進型を使います。

足す順序が結果を変えることを示す

同じ3つの数を、順序だけを変えて足したときに結果が変わる例を作り、05-order.txtに残してください。

1e16、1.0、-1e16を使ってみてください。

1e16 + 1 - 1e16 = 0.0
1e16 - 1e16 + 1 = 1.0

大きな数に小さな数を足すと、小さいほうが桁の外に押し出されて消えます。そのため、浮動小数点の足し算は結合法則が成り立たず、合計を求めるときは小さいものから足すほうが正確です。

同じ数字を別のバイト順で表す

0x12345678を、リトルエンディアンとビッグエンディアンでそれぞれ4バイトにして、06-endian.txtに残してください。このマシンがどちらかも一緒に書いてください。

struct.pack('<I', n).hex()とstruct.pack('>I', n).hex()、そしてsys.byteorderを使います。

リトルエンディアンは78563412と、ひっくり返って見えます。ファイルやネットワークで数値をやり取りするときにこれを揃えないと、値がおかしくなります。ネットワークバイトオーダーがビッグエンディアンと決められている理由です。

2の補数とオーバーフローを確認する

2**31を符号付き32ビットとして読むと何になるか、-1を符号なし32ビットとして読むと何になるかを確認して、07-int.txtに残してください。

struct.unpack('<i', struct.pack('<I', 2**31))[0]と、その逆を試します。

2**31 → -2147483648、-1 → 4294967295が出ます。同じビットをどう読むと決めたかの違いにすぎません。

他の言語で、整数が突然負の数になる事故(オーバーフロー)の正体がこれです。Pythonの整数は自動的に大きくなりますが、それはPythonが特別なのです。

3つのことを整理する

08-notes.mdに3行以上書いてください。キャッシュの外へのアクセスがなぜ遅いのか、お金をfloatで扱ってはいけない理由、バイト順を揃えなければならないときです。

本文に캐시、소수、순서が含まれている必要があります(韓国語で、順に「キャッシュ」「小数」「順序」を意味する語です)。