コンピュータにおけるデータの操作とコスト感

読了目安 約5分

メモリ参照からデータセンター間の往復まで、操作 1 回の時間を桁で覚え、何が速くなり何が変わらなかったかを知ります。

競プロでは、定数倍を無視して計算量だけを見ました。 どの操作も 1 回は 1 回として数えられたからです。

Web では、その「1 回」どうしが 6 桁違います。 どちらの 1 回なのかを知らないと、見積もりが桁ごと外れます。

桁の一覧

おおよその目安です。 正確な値ではなく、隣とどれだけ離れているかを覚えてください。 どれも、頼んでから終わって手元に返ってくるまでの時間です。

メモリ参照 1 回と、データベースへの 1 往復とでは 2,000 倍違います。 「メモリに載せれば速い」が効くのは、この差があるからです。

CPU の 1 秒は 30 億回の刻み

CPU の中では、電圧が規則正しく上下する信号が走っています。 この波の 1 往復が 1 回の刻みで、1 秒あたりの回数がクロック周波数です。 3 GHz なら 1 秒に 30 億回、1 刻みはおよそ 0.33 ナノ秒です。

回路はこの刻みに合わせて、処理を 1 段階ずつ進めます。 CPU を「何秒使った」と数えるのは、「刻みを何回ぶん使った」と数えるのと同じことです。

この単位で上の表を読み直すと、待ち時間の重さが見えます。

メモリを 1 回待つあいだに 300 回刻めますが、そのほとんどは空回りです。 周波数を上げても待ちは短くならないので、空回りの回数が増えるだけです。

キャッシュに当たるかどうかで 100 倍

上の表の 1 ns と 100 ns、つまり L1 とメインメモリの差を体験できます。 同じ回数だけ配列をたどりますが、たどる順番だけを変えます。

package main

import (
	"fmt"
	"math/rand"
	"time"
)

const n = 1 << 22     // 配列の要素数。ここを変えて試す
const steps = 1 << 22 // たどる回数。こちらは固定

// next[i] に「次にたどる番号」が入っている
func chase(next []int32) time.Duration {
	start := time.Now()
	p := int32(0)
	for i := 0; i < steps; i++ {
		p = next[p]
	}
	elapsed := time.Since(start)
	_ = p
	return elapsed
}

func main() {
	// 隣へ進むだけの順路
	seq := make([]int32, n)
	for i := range seq {
		seq[i] = int32((i + 1) % n)
	}

	// 同じ要素を通るが、順番がばらばらの順路
	perm := rand.New(rand.NewSource(1)).Perm(n)
	shuf := make([]int32, n)
	for i := 0; i < n; i++ {
		shuf[perm[i]] = int32(perm[(i+1)%n])
	}

	fmt.Println("配列の大きさ:", n*4/1024, "KB   たどった回数:", steps)
	fmt.Println("順番に  :", chase(seq).Round(time.Millisecond))
	fmt.Println("ばらばら:", chase(shuf).Round(time.Millisecond))
}

たどる回数は同じで、違うのは次にどこへ飛ぶかだけです。 それでも桁が変わります。

順番にたどると、1 回運ぶだけで隣の要素も一緒に載ってくるので、次の数回はメモリまで行かずに済みます。 ばらばらだと、毎回取りに行きます。

競プロで「配列は連続だから速い」と言われていたのは、この話です。

帯域は太くなるが、レイテンシは縮まない

回線やストレージ、メモリバスといった部品は、世代が新しくなるたびに 1 秒間に運べるデータの量（帯域）が増えます。 一方で、リクエストを送ってから応答が返ってくるまでの時間（レイテンシ）は、ほとんど変わりません。

この 2 つは、まったく別の量です。 1 KB を回線に流し込むだけなら 1 マイクロ秒ほどで終わりますが、相手に届いて返事が戻ってくるまでの往復には 200 マイクロ秒かかります。 運ぶだけの時間をどれだけ削っても、応答の速さは往復の待ち時間で決まってしまいます。

縮まないものには、それぞれ理由があります。

• 大陸をまたぐ往復は、光の速度と地球の大きさで決まっている
• HDD は、物理的にヘッドを動かしている
• メインメモリの参照は、CPU が速くなっても短くならない

この非対称が、書き方の良し悪しを決めます。

• 1 回でまとめて運ぶ書き方は、帯域が太くなるぶん年々有利になる
• 何度も往復する書き方は、レイテンシが縮まないので相対的に年々不利になる

N+1 の解消も、一括 INSERT も、同じことを言っています。 運ぶ量ではなく、往復の回数を減らしています。

CPU の速度だけが上がり続けるので、CPU から見たメモリは相対的に遠くなり続けます。キャッシュに当たるかどうかの差は、開く一方です。

同じマシンかどうかの差

ISUCON で効いてくるのは、往復の 2 つの段です。

10 倍ほど違います。 1 リクエストで 50 回問い合わせている処理は、同じマシンなら数ミリ秒で済みますが、分けた瞬間に 10 ミリ秒になります。

試してみよう

n だけを 1 << 16 に下げて実行してください（steps は変えません）。 たどる回数は同じままなのに、差がほとんどなくなります。

配列が 256 KB に縮んでキャッシュに収まり、ばらばらにたどってもメモリまで行かずに済むからです。 n を少しずつ増やして差が開き始める大きさを探すと、手元のマシンのキャッシュの容量が分かります。

配列の大きさ: 256 KB   たどった回数: 4194304
順番に  : 6ms
ばらばら: 11ms