メモリアロケータ
実装:
foundations/allocator// 実行:go test ./foundations/allocator/
プログラムが「nバイトください」と言うと、裏でアロケータが働く。連続メモリを管理し、要求に応じ切り出して貸し回収する。素朴なのは空きの一覧から足る最初を貸すfirst-fit。問題は断片化で、確保と解放を繰り返すと空きの総量は足りても細切れで大きな塊が取れない。返却時に隣接する空きを併合して戦う。free list方式のmalloc/freeを実装し、断片化と併合、速さに振り切ったbumpも見る。
この章で作るもの
使われなくなったメモリを自動で回収する話は、後の GC の章で扱う。この章はその一段下、そもそも「メモリを確保する」とはどういうことか、になる。malloc(n) や、Go の make、new を呼ぶと n バイトが返ってくる。この裏で、アロケータが働いている。OS から受け取った 1 枚の連続したメモリ(ヒープ)を管理し、プログラムの要求に応じて必要な分を切り出して貸し、返されたら次に備えて回収する。銀行の窓口が、大きな金庫から必要な額を出し入れするようなものだ。
素朴な方式は free list だ。空いているブロックの一覧を持ち、「n バイト」と言われたら、それに足る最初の空きブロックを見つけて貸す(first-fit)。空きが要求より大きければ、必要分を切り取り、余りを空きとして残す。返却されたらそのブロックを空きに戻す。ここまでは単純だが、確保と解放を繰り返すうちに厄介な問題が育つ。断片化だ。空きの総量は十分あるのに、それが細切れに散らばって、大きな一塊が取れなくなる。この章では、free list アロケータを実装し、断片化と、それを緩める併合(coalescing)、そして対極の bump アロケータを見る。
初期 [────────── 空き 100 ──────────]
確保30 [使 30][────── 空き 70 ──────] first-fit + 分割
確保30 [使 30][使 30][─ 空き 40 ─]
解放① [空 30][使 30][─ 空き 40 ─] 空き総量70だが連続は最大40
解放② [──── 空き 100 ────] 隣接を併合 → 大きな塊が戻る順に見ていく。
- free list と first-fit: 空きブロックの一覧から、要求に足る最初の空きを貸す。大きすぎれば切り分ける
- 断片化: 確保と解放を繰り返すと、空きの総量は足りても連続領域が細切れになり、大きな確保が失敗する
- 併合(coalesce): 返却時に隣り合う空きをまとめる。断片化を緩め、再び大きな確保を可能にする
① free list と first-fit: 空きを見つけて切り分ける
まず確保だ。ヒープ全体を、アドレス順に並んだブロックの列として持つ。各ブロックは「空きか使用中か」を覚えている。確保では、要求に足る最初の空きブロックを探し、大きすぎれば余りを切り分ける:
// Alloc は n バイトを first-fit で確保し、その先頭オフセットを返す。
// 足る最初の空きブロックを使い、大きすぎれば余りを空きとして切り分ける。
func (a *Allocator) Alloc(n int) (int, bool) {
if n <= 0 {
return 0, false
}
for i := range a.blocks {
b := &a.blocks[i]
if !b.Free || b.Size < n {
continue
}
off := b.Offset
if b.Size > n {
// 余りを空きブロックとして直後に挿入する(分割)。
remainder := Block{Offset: b.Offset + n, Size: b.Size - n, Free: true}
b.Size = n
b.Free = false
a.blocks = append(a.blocks[:i+1], append([]Block{remainder}, a.blocks[i+1:]...)...)
} else {
b.Free = false // ぴったりなら分割せず貸す
}
return off, true
}
return 0, false // 足る空きがない
}Alloc(n) は先頭から空きブロックを走査し、n 以上の最初の空きを使う(first-fit)。ぴったりならそのまま貸し、大きければ必要分だけ切って、残りを空きブロックとして直後に挿入する(分割)。テストで、確保が重ならず詰めて配置されること、分割で「使用中 + 余りの空き」の 2 ブロックになること、容量を超える確保が失敗することを固定した。first-fit は速いが、必ずしも最適な空きを選ばない。「最も無駄の少ない空き」を選ぶ best-fit もあるが、探索が遅く、断片化がむしろ増えることもある。方式ごとに一長一短だ。
② 断片化: 空きはあるのに取れない
問題はここから育つ。確保と解放を繰り返すと、使用中と空きがまだらに並ぶ。すると、空きの総バイト数は十分あるのに、連続した大きな空きが取れなくなる。真ん中に使用中のブロックが残っていると、その両側の空きは分断され、合わせれば足りるのに 1 つの確保には使えない:
// Free は offset のブロックを解放し、隣り合う空きと併合する。
func (a *Allocator) Free(offset int) bool {
for i := range a.blocks {
if a.blocks[i].Offset == offset {
if a.blocks[i].Free {
return false // 二重解放
}
a.blocks[i].Free = true
a.coalesce()
return true
}
}
return false // そのオフセットのブロックがない
}
// coalesce は隣り合う空きブロックを 1 つにまとめる(断片化対策)。
func (a *Allocator) coalesce() {
merged := make([]Block, 0, len(a.blocks))
for _, b := range a.blocks {
if len(merged) > 0 {
last := &merged[len(merged)-1]
if last.Free && b.Free {
last.Size += b.Size // 直前も今も空き → まとめる
continue
}
}
merged = append(merged, b)
}
a.blocks = merged
}
// FreeBytes は空きの総バイト数。
func (a *Allocator) FreeBytes() int {
total := 0
for _, b := range a.blocks {
if b.Free {
total += b.Size
}
}
return total
}
// LargestFree は連続した最大の空きブロックのサイズ(ここまでしか一度に確保できない)。
func (a *Allocator) LargestFree() int {
max := 0
for _, b := range a.blocks {
if b.Free && b.Size > max {
max = b.Size
}
}
return max
}
// Fragmentation は外部断片化の度合い(0=断片なし, 1に近いほど細切れ)。
// 空きは十分でも連続領域が小さいほど大きくなる。
func (a *Allocator) Fragmentation() float64 {
free := a.FreeBytes()
if free == 0 {
return 0
}
return 1 - float64(a.LargestFree())/float64(free)
}LargestFree が「一度に確保できる最大」で、FreeBytes の総量とは別物だ。テストで、90 バイトのヒープに 30 を 3 つ確保し、両端を解放すると、空きの総量は 60 なのに連続は 30 までで、40 の確保が失敗することを固定した。これが外部断片化(external fragmentation)だ。Fragmentation は、空きが十分でも連続領域が小さいほど 1 に近づく指標にした。断片化は、長時間動くサーバやアロケータの宿命的な敵で、放置すると「メモリはあるのに確保できない」状態に陥る。
③ 併合と bump: 断片化への2つの答え
断片化への 1 つの答えが併合(coalescing)だ。ブロックを解放するとき、隣り合うブロックも空きなら、それらを 1 つの大きな空きにまとめる。
上の coalesce がそれだ。解放後にブロックの列を走査し、連続する空きを結合する。真ん中の使用中ブロックが解放されて両側の空きと繋がれば、3 つの小さな空きが 1 つの大きな空きに戻る。テストで、断片化して 50 が取れない状態から、間のブロックを解放して併合すると、大きな空きが復活して確保できるようになることを固定した。併合は断片化を根絶はしないが、大きく緩める。
もう 1 つの答えは、そもそも個別解放をやめることだ。bump アロケータは、ポインタを 1 つ持ち、確保のたびにそれを進めるだけ。空きを探す必要も、分割も併合もない:
// Bump は bump(ポインタ前進)アロケータ。確保はポインタを進めるだけで速いが、
// 個別の解放ができない。Reset で全部まとめて解放する(アリーナ方式)。
type Bump struct {
size int
next int
}
// NewBump は size バイトの bump アロケータを作る。
func NewBump(size int) *Bump { return &Bump{size: size} }
// Alloc は next を n だけ進めて確保する。溢れたら失敗。
func (b *Bump) Alloc(n int) (int, bool) {
if n <= 0 || b.next+n > b.size {
return 0, false
}
off := b.next
b.next += n
return off, true
}
// Used は確保済みバイト数。
func (b *Bump) Used() int { return b.next }
// Reset は全確保を一度に解放する(個別解放はできない)。
func (b *Bump) Reset() { b.next = 0 }Alloc はポインタを n 進めて返すだけで、極めて速い。代償は、個別の解放ができないことだ。あるオブジェクトだけを返すことはできず、Reset で全部を一度に解放する。これはアリーナ(arena)方式と呼ばれ、「一連の処理でまとめて確保し、処理が終わったら全部捨てる」場面(1 リクエストの処理、1 フレームの描画)に向く。断片化は起きようがない。速さと引き換えに、解放の柔軟さを捨てた割り切りだ。汎用の malloc と使い分ける。
動かす
下のデモは、ヒープにブロックを確保・解放しながら、free list の様子・断片化の発生・併合による回復を見る。空きの総量は足りても連続領域が足りず確保に失敗する様子、隣接ブロックの解放で空きが繋がる様子を確かめてほしい。
初期状態は断片化している(空き60だが連続20まで)
ヒープを空き/使用中のブロック列で管理する。確保は足る最初の空きを first-fit で貸し、大きすぎれば分割する。 確保と解放を繰り返すと、空きの総量は足りても連続領域が細切れになり、大きな確保が失敗する(外部断片化)。 使用中ブロックを解放すると隣り合う空きが併合され、大きな空きが復活する。連続最大と空き総量が別物なのが肝だ。
設計の観点
- 配置方針の選択: first-fit(速い)・best-fit(無駄少なめだが遅い)・segregated(サイズ別リスト)など。ワークロードで最適が変わる。万能はない
- 断片化との戦い: 併合に加え、サイズをクラスに丸める(segregated free list)、2 の冪で管理する(buddy)などで断片化を抑える。GC 付き言語はコンパクション(生存オブジェクトを詰め直す)も使える
- アリーナの威力: 寿命が揃うオブジェクト群は bump/arena でまとめて確保・解放すると速く、断片化もない。用途を見極めて汎用アロケータと使い分ける
- メタデータの置き場: 実物は各ブロックの前にヘッダ(サイズ・使用フラグ)を置く。free() がポインタだけでブロックを特定できるのはこのため
- 並行性: 実用アロケータ(tcmalloc, jemalloc)は、スレッドごとのキャッシュや arena でロック競合を避ける。単一の free list はマルチスレッドでボトルネックになる
対照と実例
| 方式 | 確保速度 | 個別解放 | 断片化 | 用途 |
|---|---|---|---|---|
| free list(first-fit) | 中(探索あり) | できる | 起きる(要併合) | 汎用 malloc |
| best-fit | 遅い | できる | 抑えめ | 無駄を嫌う場面 |
| buddy | 速い | できる | 内部断片化あり | カーネル、ページ確保 |
| bump / arena | 最速 | できない | 起きない | 寿命が揃う一括処理 |
裏どり:
- Doug Lea's malloc (dlmalloc): 多くの libc malloc の原型。ビン分けした free list と併合の実装
- tcmalloc / jemalloc: Google / Facebook の高性能アロケータ。per-thread キャッシュとサイズクラスで並行性と断片化を両立
- buddy allocator: Linux カーネルの物理ページ確保。2 の冪ブロックの分割・併合
- arena / region allocation: Apache や多くのコンパイラが使う。寿命の揃うメモリを一括管理
簡略化したこと
- オフセットのみ: 実バイト列でなく、区画の位置とサイズだけを管理する
- first-fit のみ: best-fit や segregated free list、buddy は扱わない
- アライメントとヘッダなし: 実物は境界揃えやブロックヘッダを持つ
- スレッド非対応: 実物はロックや per-thread arena で並行確保を捌く
参考資料
- The Art of Computer Programming, Vol.1 (Knuth) — 動的記憶割り当てと断片化の古典
- CS:APP, Dynamic Memory Allocation — malloc/free の実装解説
- jemalloc paper — 現代の並行アロケータの設計
- 実装: foundations/allocator