メモリと仲良しになろう！[超入門編]

次編でメモリアロケータの実装解説をします。記事作成中のため完成までお待ちください🥺

はじめに

近年メモリのことをあまり考えずにプログラムが書けるので、メモリが寂しそうだなぁと思い一筆執りました。メモリ周りの知識でお役に立てれば幸いです。

また本記事を読んだ後、下記の記事を読むとさらに深い理解を得られます。ぜひぜひ。
https://zenn.dev/tomoikey/articles/20f99256507362

誰のための記事か？(for whom)

• メモリの役割が分からない人
• メモリ上でどのようにデータが載るのかが分からない人
• アロケータが何か分からない人
• どのようにアロケーションが行われるか分からない人

なぜ学ぶのか？ (why)

• 近年はメモリをあまり意識しなくても良い反面、コンピュータの気持ちが分からないままプログラムが書けてしまい、暗黙的なパフォーマンス低下に気づけないという状態になりやすいため
• 自作 OS 開発をする上での基礎的な知識として必要であるため
• メモリアロケーションは高価な処理であるということを理解するため

1. メモリとは？

メモリとは「コンピュータさんが使う道具を置いておくための作業机」のことです。

僕もこの記事を読んでいるそこのアナタも、プログラミングをする上で様々なデータ型を扱うと思います。(文字列や可変長の配列などなど...)

では、宣言した変数に入っている文字列やクラスはどこに格納されているのでしょうか？プログラムが処理をしていく上で、データはどこか適当な場所に置いておかなければ何もできないはずです。その場所こそが「メモリ」です。日本語で一時記憶装置とも呼ばれています。メモリには沢山の道具入れが置いてあってその中にデータをしまっておくのです。

もう完璧に想像できたと思いますが、プログラムが走る時に利用されるデータ(道具)を置いておくための格納場所(作業机)なので「コンピュータさんが使う道具を置いておくための作業机」ということです。

実はメモリは使われ方によっていくつかの種類に分類されます。代表的なものは「スタックメモリ」と「ヒープメモリ」の2つです。いきなり単語が増えてビックリしているかもしれませんがとても簡単です。それぞれの Pros / Cons を見てみましょう。

• スタックメモリ
  • Pros
    • データの収納方法が単純なので格納場所探しに時間がかからない
    • 自主的にお片付けしなくてもゴミが残らない
  • Cons
    • あらかじめサイズが分かっているものしか格納することができない
    • 大きなデータを格納することが苦手
    • スタックできる量には上限があり、大量に積むことには向いていない
      • スタック上限を超えることを「スタックオーバーフロー」といいます
• ヒープメモリ
  • Pros
    • あらかじめサイズが分かっていないものでも収納することができる
    • 大きなデータを格納することが得意
  • Cons
    • データの収納方法が複雑なので格納場所探しに時間がかかる
    • 自主的にお片付けしなければゴミが残ってしまう
      • 掃除を忘れてメモリが逼迫することを「メモリリーク」といいます

それぞれ Pros / Cons が対極的であることが分かると思います。この記事ではヒープメモリについて覚えておけば読むことができるので軽く目を通しておいてください。

2. アドレスとは？

アドレスとは「作業道具を収納する引き出しに付いている番号」のことです。

あるデータをメモリの引き出しに置いたはいいけど、どこにしまったのかを忘れてしまったらデータを探すことができません。なのでデータをメモリの引き出しに収納する時は、その引き出しの番号シールをしっかり見て覚えておき、逆にデータを引っ張り出したいときは覚えておいた引き出しの番号シールを元に探し出しにいきます。この引き出しに貼ってある番号シールのことを「アドレス」と言います。

メモリアドレスは一般的に「0x1f3a9」や「0x86bd6」のように16進数で表記します。(0x は「16進数ですよ〜」という意味で頭につけられます)

また一つのアドレスには 1byte (8bit) のデータを収納することができます。1byte に収まらないデータに関してはなるべく隣り合ったアドレスに配置されます。

例として下記のような 1byte のデータを3つ持つ構造体がメモリ上でどのように配置されているか見てみましょう。

// 1byte のデータを3つ持った Sample という構造体 (≒ クラス)
type Sample struct {
    a int8 // 8bit int 型の a という名前のメンバー (つまり 1byte のデータ型)
    b int8
    c int8
}

main.go

func main() {
    sample := Sample{a: 1, b: 2, c: 3} // Sample を生成
    fmt.Printf("a: %p\n", &sample.a) // Sample.a のアドレス (引き出しの番号)
    fmt.Printf("b: %p\n", &sample.b) // Sample.b のアドレス (引き出しの番号)
    fmt.Printf("c: %p\n", &sample.c) // Sample.c のアドレス (引き出しの番号)
}

出力

a: 0xc00009800b
b: 0xc00009800c
c: 0xc00009800d

16進数に馴染みがないとパッと分からないかもしれませんが a, b, c はそれぞれ隣り合って並んでいますね！

では 2byte のデータを並べてみたらどうでしょう？結果は下記の通りになります。

出力

a: 0xc000010080
b: 0xc000010082
c: 0xc000010084

アドレスは変わりましたが2つ間隔で並んでいますね！なぜなら 2byte のデータを1つ格納するためには2つ引き出しが必要だからです。そのためアドレスが2つ間隔で並んでいます。
ズバリ、データのアドレスとは「データの先頭が格納されているアドレスのこと」となります。

ここでもしかすると勘の良い方は疑問に思ったことでしょう。「データの先頭アドレスが分かっても、どのアドレスまで読み進めればいいか分からないとダメじゃない？」と。その通りです😎

次の章でその説明をします。

3. メモリレイアウトとは？

メモリレイアウトとは「データの間取り」のことです。

では具体的にメモリレイアウトにはどのような構成要素があるのか見てみましょう。下記の3つです。

• アラインメント
• サイズ
• 配置順序

1. アラインメント

アラインメントとは「整理整頓」のことです。

メモリにデータを格納するとき、どんなアドレスに配置するかは重要な問題です。なぜならば CPU が読み書きしやすい配置があるからです。

例えば 32bit CPU は一度に 4byte の読み書きができます。この一度に読み書きできる単位を「ワード」といいます。CPU はその設計上、ワード単位のアクセスを最も得意としています。そのため 32bit CPU では、アクセス対象の開始アドレスが 4byte 境界に存在しているとめちゃめちゃ高速にアクセスしてくれます。他にもハーフワード(ワードの半分である単位)や 1byte 単位でのアクセスが得意だったりします。このように n byte 境界でデータが配置されていることを「n byte 境界にアラインされている」といいます。(この n は2の冪乗(1, 2, 4, 8, ...)であることが一般的です)

ワードの定義の曖昧さ

ワードという言葉について詳しく調べてみると、定義が曖昧な語であることが分かりました。調査結果を下記にまとめます。

1. Intel® 64 and IA-32 Architectures Software Developer’s Manuals

   • a word is 2 bytes (16bits) (Vol.1 4-1 FUNDAMENTAL DATA TYPES より引用)

   • 16 bit 時代からの拡張による歴史的背景が関連(?)
2. Arm Architecture Reference Manual for A-profile architecture

   • Word 32bits (A1.4 Supported data types より引用)

3. CPU が一度に扱える bit 数をワードと定義する文化
   • 64bit => 1ワード == 64
   • 32bit => 1ワード == 32

本記事ではワードを「3」の意味で使っています。ご注意ください。

実は驚くことにアラインされていないデータの読み書きをしようとすると、unaligned memory access というエラー (bus error) が発生する CPU がこの世には存在するのです。そのためアラインメントは適切に行わないとパフォーマンスが悪くなったり、実行環境依存ではそもそも動かなかったりするのでメモリの読み書きをする上ではアラインメントを常に意識しなければなりません。

メモリを扱う上でアラインメントは絶対的正義です。ですが複合データ型メンバをしっかりアラインしようとすると、どうしても余分に空きメモリを差し込む必要が出てきます。これは良いのでしょうか？はい、多少余分にメモリを消費してでもしっかりアラインすることの方が大事です。

この空きメモリのことを「padding」と言います。詳しくは下記のサイズのセクションで分かると思います。

余談 (一般的なデータ型のアラインメントについて)

プリミティブ型のアラインメントはそのサイズに一致することが多いので覚えておくと良いでしょう。(int8 = 1, int16 = 2 ...)

一方で複合型 (構造体など) ではメンバの中で最も厳格なアラインメントに合わせられることも覚えておくと良いです。

2. サイズ

サイズとは「1データがメモリ上で占める大きさ」のことです。

サイズは比較的分かりやすい概念ですが、少し注意が必要です。それは必ずしも実データのみの大きさのみを指しているわけではないからです。あまりピンと来ませんね。少し具体を見てみましょう。

こちらは 8bit 整数2つと 16bit 整数1つで構成された構造体です。サイズはどのようになるでしょうか。

type Sample struct {
    a int8 // 8bit int 型の a という名前のメンバー (つまり 1byte のデータ型)
    b int8
    c int16 // 16bit int 型の c という名前のメンバー (つまり 2byte のデータ型)
}

main.go

func main() {
    sample := Sample{a: 1, b: 2, c: 3}
    sampleAddress := uintptr(unsafe.Pointer(&sample))

    aOffset := unsafe.Offsetof(sample.a)
    bOffset := unsafe.Offsetof(sample.b)
    cOffset := unsafe.Offsetof(sample.c)

    sampleSize := unsafe.Sizeof(sample)

    fmt.Printf("sample address: 0x%x\n\n", sampleAddress)
    fmt.Printf("a offset: 0x%x\n", aOffset)
    fmt.Printf("b offset: 0x%x\n", bOffset)
    fmt.Printf("c offset: 0x%x\n", cOffset)
    fmt.Printf("size: %d\n", sampleSize)
}

出力

sample address: 0xc00007ceec

a offset: 0x0
b offset: 0x1
c offset: 0x2
size: 4

このようになりました。1byte * 2 + 2byte * 1 = 4byte なので計算通りですね。では次の例ではどうでしょう。

type Sample struct {
    a int8
    b int16 // int8 から int16 に書き換えた
    c int8 // int16 から int8 に書き換えた
}

何が変わったのかというと b が 8bit 整数から 16bit 整数になり、c が 16bit 整数から 8bit 整数になりました。直感ではデータのサイズは変わらないと思いますが結果はどうなるでしょうか。

出力

sample address: 0xc00007ceea

a offset: 0x0
b offset: 0x2
c offset: 0x4
size: 6

おかしい...。サイズが4から6に増えてますね...。なぜなのでしょうか。

答えは「メンバデータは定義順に格納され、尚且つメンバ自体もアラインメントされているから」です。(あくまで Go ではの話)

もう少し噛み砕いてみましょう。

図示してみる

1つ目の実験

出力 (再掲)

sample address: 0xc00007ceec

a offset: 0x0
b offset: 0x1
c offset: 0x2
size: 4

Offset \ Address	0	1	2	3	4	5	6	7
0x0	a	b	c	c	-	-	-	-

2つ目の実験

出力 (再掲)

sample address: 0xc00007ceea

a offset: 0x0
b offset: 0x2
c offset: 0x4
size: 6

Offset \ Address	0	1	2	3	4	5	6	7
0x0	a	(padding)	b	b	c	(padding)	-	-

2つ目の実験を図示したものから分かるように、メンバもアラインされているので padding が差し込まれています。c の後ろにも謎の padding が入っている理由は、Sample 構造体のメンバの中で最も厳格なアラインメント要件を持っている int16 に合わせて Sample のアラインメントも 2byte 境界になっているためです。そのため size が5ではなく6になっています。

3. 配置順序

メモリレイアウトで最も重要な構成要素です。言葉通りデータがどのように配置されるのかを決定するものです。そしてこの配置順序は言語によって異なります。私が観測している中では3種類存在します。

• アラインメントを守っているタイプ
  • 定義順に並べるタイプ
  • サイズが小さくなるように配置するタイプ
• アラインメントを守っていないタイプ
  • サイズが最も小さくなるように配置するタイプ

アラインメントを守っているタイプ

1. 定義順に並べるタイプ

このタイプは、アラインメントを守りつつ構造体のメンバ定義順に並べるタイプです。非常に分かりやすいですね。C や Go がこれに該当します。

main.go

type Sample struct {
    a int8
    b int64
    c int8
    d int32
    e int8
    f int16
}

func main() {
    sample := Sample{a: 1, b: 2, c: 3, d: 4, e: 5, f: 6}
    sampleAddress := uintptr(unsafe.Pointer(&sample))

    aOffset := unsafe.Offsetof(sample.a)
    bOffset := unsafe.Offsetof(sample.b)
    cOffset := unsafe.Offsetof(sample.c)
    dOffset := unsafe.Offsetof(sample.d)
    eOffset := unsafe.Offsetof(sample.e)
    fOffset := unsafe.Offsetof(sample.f)

    sampleSize := unsafe.Sizeof(sample)

    fmt.Printf("sample address: 0x%x\n\n", sampleAddress)
    fmt.Printf("a offset: 0x%x\n", aOffset)
    fmt.Printf("b offset: 0x%x\n", bOffset)
    fmt.Printf("c offset: 0x%x\n", cOffset)
    fmt.Printf("d offset: 0x%x\n", dOffset)
    fmt.Printf("e offset: 0x%x\n", eOffset)
    fmt.Printf("f offset: 0x%x\n", fOffset)
    fmt.Printf("size: %d\n", sampleSize)
}

出力

sample address: 0xc00007cea0

a offset: 0x0
b offset: 0x8
c offset: 0x10
d offset: 0x14
e offset: 0x18
f offset: 0x1a
size: 32

綺麗に a => b => c => d => e => f のように定義順で並んでいますね！サイズは32でした。

2. サイズが小さくなるように配置するタイプ

このタイプはアラインメントを守りながらサイズがなるべく小さくなるように並べるタイプです。従って定義順とは異なる並べ方をされる可能性があります。Rust がこれに該当します。

正確には Rust の構造体フィールドの配置順序は言語仕様で未定義であるため厳密性を欠いている可能性があります。

main.rs

struct Sample {
    a: i8,
    b: i64,
    c: i8,
    d: i32,
    e: i8,
    f: i16,
}

fn main() {
    let sample = Sample {a: 1, b: 2, c: 3, d: 4, e: 5, f: 6};
    let sample_address = addr_of!(sample) as usize;
    
    let a_offset = addr_of!(sample.a) as usize - sample_address;
    let b_offset = addr_of!(sample.b) as usize - sample_address;
    let c_offset = addr_of!(sample.c) as usize - sample_address;
    let d_offset = addr_of!(sample.d) as usize - sample_address;
    let e_offset = addr_of!(sample.e) as usize - sample_address;
    let f_offset = addr_of!(sample.f) as usize - sample_address;
    
    let sample_size = std::mem::size_of::<Sample>();
    
    println!("sample address: 0x{sample_address:x}\n");
    println!("a offset: 0x{a_offset:x}");
    println!("b offset: 0x{b_offset:x}");
    println!("c offset: 0x{c_offset:x}");
    println!("d offset: 0x{d_offset:x}");
    println!("e offset: 0x{e_offset:x}");
    println!("f offset: 0x{f_offset:x}");
    println!("size: {sample_size}");
}

出力

sample address: 0x7fff59c955c0

a offset: 0xe
b offset: 0x0
c offset: 0xf
d offset: 0x8
e offset: 0x10
f offset: 0xc
size: 24

なんとアドレスが b => d => f => a => c => e の順番になってますね！さらにサイズが32ではなく24になっているのでかなりメモリが節約されています。めっちゃ面白い！！

アラインメントを守っていないタイプ

1. アラインメントを無視しながら定義順に並べるタイプ

このタイプは CPU のご都合度外視でパディングを一切入れないようにするタイプです。同じく Rust がこれに該当します。(#[repr(packed)] というアトリビュートを指定した場合に限る)

main.rs

#[repr(packed)]
struct Sample {
    a: i8,
    b: i64,
    c: i8,
    d: i32,
    e: i8,
    f: i16,
}

fn main() {
    let sample = Sample {a: 1, b: 2, c: 3, d: 4, e: 5, f: 6};
    let sample_address = addr_of!(sample) as usize;
    
    let a_offset = addr_of!(sample.a) as usize - sample_address;
    let b_offset = addr_of!(sample.b) as usize - sample_address;
    let c_offset = addr_of!(sample.c) as usize - sample_address;
    let d_offset = addr_of!(sample.d) as usize - sample_address;
    let e_offset = addr_of!(sample.e) as usize - sample_address;
    let f_offset = addr_of!(sample.f) as usize - sample_address;
    
    let sample_size = std::mem::size_of::<Sample>();
    
    println!("sample address: 0x{sample_address:x}\n");
    println!("a offset: 0x{a_offset:x}");
    println!("b offset: 0x{b_offset:x}");
    println!("c offset: 0x{c_offset:x}");
    println!("d offset: 0x{d_offset:x}");
    println!("e offset: 0x{e_offset:x}");
    println!("f offset: 0x{f_offset:x}");
    println!("size: {sample_size}");
}

出力

sample address: 0x7fff14131217

a offset: 0x0
b offset: 0x1
c offset: 0x9
d offset: 0xa
e offset: 0xe
f offset: 0xf
size: 17

こちらはアドレスが定義順に並んでおりますが、アラインメントが完全に無視されていますね。しかしサイズが17になっているのでかなりコンパクトになっていることが分かります。

このように配置順は静的に確定しているので、データのアドレスが分かれば読み書きが可能です。またデータの掃除に関してもサイズが静的に算出されているので、アドレスさえ分かれば掃除範囲の特定が可能であることが分かります。

4. アロケータとは？

アロケータとは「ヒープメモリにある引き出しの管理人さん」のことです。

あるデータをメモリに格納するとき、好き勝手な引き出しを開けて収納するとどうなるでしょうか。誰かが既に引き出しに収納しているかもしれませんね。では引き出しに収納しているデータを勝手に捨てたらどうでしょうか。データの持ち主が引き出しを開けに帰ってきて「自分のお道具セットがない！」なんてあったらあまりに可哀想です。従って新しいデータを格納したい場合は誰も使っていない引き出しを探す必要があります。しかしどこが空いているかなんて分かりませんよね。

そこで、どの引き出しが利用中でどの引き出しが空いているのかを管理する人が必要です。まさにその人こそが「アロケータ」です。

アロケータは最大限引き出しを有効活用できるようにデータの大きさを考慮して最適な場所を探す責任があります。実は現代の優秀なアロケータをもってしても、最適な場所を探す処理はかなり複雑で高負荷な処理です。メモリアロケーションの回数とプログラムのパフォーマンスは大きく直結します。プログラマがメモリを意識せずともプログラムを書けるからといって、むやみやたらにヒープアロケーションが走るようなプログラムを書くのは大罪です。例えば可変長配列の capacity が良い例です。あらかじめ最大サイズが分かっているのにも関わらず、適当に要素の追加をしていませんか？もしやってしまっているのであれば、明示的に capacity を渡すことでメモリの最大利用サイズを指定し、再アロケーションが走らないようにするべきです。なるべくアロケーション回数が最小限に抑えられるように気をつけましょう。

またデータの持ち主が「もうこの道具いらないから捨てて欲しい」と言ったらアロケータさんが掃除してくれます。引き出しの個数は有限なので、利用者みんなで仲良く再利用できるように要らない道具は要らないと表明する必要があります。
このデータのお掃除ですが、ガベージコレクション(GC)を持っている言語であれば、必要なくなった道具のアドレスをかき集めてアロケータに掃除してもらいます。ガベージコレクションを持っていない言語では、プログラマが「この行で道具をポイしてください」と表明する必要があります。(Rust は所有権システムによって自動でお掃除するので例外です)

(余談) アロケータの種類

アロケータにはメモリ管理アルゴリズムがいくつか存在します。アルゴリズム別にアロケータの名前だけ簡単に紹介します。

1. バンプアロケータ
2. 連結リストアロケータ
3. 固定サイズブロックアロケータ

実装編にてこれらアロケータについて深掘りしますが、完璧なアロケータというものは存在しません。アルゴリズムごとに得意なシチュエーションや苦手なシチュエーションがあるので用途ごとに使い分けることが大切です。

5. まとめ

いかがでしたでしょうか。プログラムが裏側でどんなことをしているのか感覚が掴めたと思います。次回の記事ではアロケータの実装をすることで深い理解を得られるようにする試みです。

よろしければ GitHub のフォローもお願いします🥺
https://github.com/tomoikey

参考: https://os.phil-opp.com/