今回はＣ++の「メモリアロケーション (メモリ確保, メモリ割り当て)」について説明します。今までは大域変数や局所変数を宣言することでメモリ領域を確保しました。大域変数はプログラムを実行するとき、あるメモリ領域 (データ領域) に確保されます。これを「静的メモリ割り当て」といいます。局所変数や関数の引数は「スタック領域」に確保されます。これを「自動メモリ割り当て」といいます。
最後に、「ヒープ領域」[*1] からメモリを割り当てる方法があります。これを「動的メモリ割り当て」[*2] といいます。Ｃ++では new 演算子でメモリを取得します。new で割り当てたメモリ領域は局所変数や関数の引数のように自動的に解放されません。Ｃ++でメモリを解放するのが delete 演算子です。new や delete を使いこなせるようになると、プログラミングの幅はぐーんと広がります。少々難しい話になりますが、恐れずにチャレンジしましょう。
一般的なＣ/Ｃ++コンパイラの実装では、引数を「スタック (stack)」というメモリ領域に格納してから関数を呼び出します。また、局所変数もスタック上に確保されます。では、スタックとはどのようなものなのでしょうか。よく例に取り上げられるのが「バネ付きのトレイ」です。下図を見てください。
|-----| |[ A ]| |[ B ]| |[ A ]| |-----|
| | | |-----| |[ A ]| |-----| | | |
| | | | | | |-----| | | | | | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
+-----+ +-----+ +-----+ +-----+ +-----+
1. 空の状態 2.PUSH 3.PUSH 4.POP 5.POP
A B B A
図 : スタックの動作例
初めは空の状態です。ここにトレイを上から入れると、重さによってバネを圧縮し、次のトレイを追加できるようになります。さらにもうひとつトレイを乗せると、さらにバネを圧縮し次のトレイを追加できるようになります。バネが限界まで圧縮されるとトレイは追加できなくなります。トレイを取り出す場合は、上にあるトレイから取り出します。ひとつ取り出すと、その分バネが伸びて下にあるトレイが上に出てくるので、次のトレイを取り出すことができます。
このトレイをデータに見立ててみましょう。データ A をスタックに追加し (2)、次にデータ B を追加します (3)。データを取り出す場合、後から入れたデータ B が先に取り出され (4)、その次にデータ A が取り出されてスタックは空になります (5)。スタックにデータを追加することを「プッシュ (PUSH)」といい、スタックからデータを取り出すことを「ポップ (POP)」といいます。
コンピュータではメモリを使ってこのスタックを実装することになります。一般に、バネの代わりに「スタックポインタ (SP)」を使ってスタックを管理します。下図を見てください。
アドレス Low High SP
A B C D E
[ ] E スタックは空
[ 3 ] D PUSH 3
[ 2 3 ] C PUSH 2
[ 1 2 3 ] B PUSH 1
[ 2 3 ] C POP => 1 が取り出される
[ 3 ] D POP => 2 が取り出される
[ ] E POP => 3 が取り出される
スタックが空になる
図 : メモリ上でのスタックの実現
便宜上アドレスを A から E までのアルファベットで表すことにします。スタックが空の場合 SP は E を指示しています。データをプッシュする場合、SP を E から D にひとつ減らし [*3] D にデータをセットします。データをプッシュしていくと SP は Low アドレスに向かっていきます。つまりデータは High アドレスから Low アドレスに向かってスタックに積まれていきます。[*4]
データをポップする場合、SP が B を指示しているならば、B にあるデータ 1 を取り出してから SP をひとつ増やして C に移します。データを次々とポップしていくと SP の値は E になり、スタックは空の状態になります。
これが何の役に立つんだと思ってはいけません。近代的なプログラミング言語は、スタックを使って関数呼び出しを実装しているからです。関数の呼び出しや局所変数の確保に使われるスタックを「システムスタック」とか「コールスタック」といいます。
それでは、関数が呼び出されるときのスタックの様子を見てみましょう。階乗の計算を行う関数 fact(4) から fact(3) を呼び出す場合を考えてみます。次の図を見てください。
リスト : 階乗
int fact(int n)
{
if (n == 0)
return 1;
else
return n * fact(n - 1);
}
<---- 4 byte ---->
アドレス Low A [ ]
B [リターンアドレス] <= SP (5)
C [引数 n : 0 ]
D [リターンアドレス] <= SP (4)
E [引数 n : 1 ]
F [リターンアドレス] <= SP (3)
G [引数 n : 2 ]
H [リターンアドレス] <= SP (2)
I [引数 n : 3 ]
High J [ ] <= SP (1)
図 : 引数をスタックに積む
fact(4) が実行されているときのスタックポインタは (1) の状態であったとしましょう。アドレスを便宜上 A から J までのアルファベットで表すことにすると、SP は J を示しています。
まず引数 n の値 3 がスタックに積まれます。SP はひとつ減りアドレス I を指し示し、そこに n の値 3 が格納されます。fact の引数はひとつなので、次に fact の関数呼び出しが行われます。関数を呼び出す場合、呼び出された関数から呼び出し元の関数に戻るための情報 (リターンアドレス) をスタックにプッシュします。
fact(3) が実行されるときの SP は (2) の状態です。呼び出された関数では、スタックポインタの位置から引数がスタックのどの位置に積まれたかわかるので引数を取り出すことができます。同様にして fact(2) が呼び出されるときは、アドレス G の位置に引数 n の値 2 が格納されます。このように、関数呼び出しが行われるたびに引数が新しい領域にコピーされていくことがわかると思います。これが「値呼び」の仕組みです。
関数の実行が終了すると、スタックからリターンアドレスを取り出して呼び出し側に戻ります。このままではスタックに引数を積んだままの状態なので、呼び出し側の関数でスタックから引数を削除する処理を行います。なお、スタックに積んだ引数を削除するタイミングは、プログラミング言語によって異なります。
fact は引数がひとつしかなかったので、今度は引数が複数ある関数を呼び出す場合を考えてみましょう。
リスト : 引数が複数ある場合の例
int foo(int a, int b, int c)
{
return a * a + 2 * b + c;
}
foo(1, 2, 3); と呼び出した場合
アドレス Low [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ 1 ] <= SP
[ ] [ ] [ 2 ] <= SP [ 2 ]
[ ] [ 3 ] <= SP [ 3 ] [ 3 ]
High [ ] <= SP [ ] [ ] [ ]
図 : 引数をスタックに積む順序
CPU が x86 の場合、実引数は右側から順番にスタックに積まれていくことに注意してください。ただし、引数を評価する順序は規定 [*5] されていないので、左側の引数から評価する処理系があってもかまいません。その場合でも、実引数をスタックに積む順番は変わりません。
たとえば、a = 10, b = 20, c = 30 として、foo(a, b, c) を呼び出す場合、変数から値を取り出す順番が a -> b -> c になるのか c -> b -> a になるのかは処理系に依存しますが、スタックに格納される実引数はどちらの方法でも Low [10 20 30] High になるということです。
簡単な例を示しましょう。次のプログラムは clang++ と g++ で実行結果が異なります。
リスト : 引数の評価順序 (sample70.cpp)
#include <iostream>
using namespace std;
int foo(string mes, int n)
{
cout << mes << endl;
return n * n;
}
void bar(int a, int b, int c)
{
cout << a << " " << b << " " << c << endl;
}
int main()
{
int a = 10, b = 20, c = 30;
bar(foo("foo", a), foo("bar", b), foo("baz", c));
}
$ clang++ sample70.cpp $ ./a.out foo bar baz 100 400 900 $ g++ sample70.cpp $ ./a.out baz bar foo 100 400 900
Clang++ の場合は左側の引数から評価され、g++ の場合は右側の引数から評価されていることがわかります。
引数と同様に、局所変数もスタック上に確保されます。なお、これから説明することは単純化した一般論であり、コンパイラの最適化によっては結果が異なる場合もあります。ご注意ください。
リスト : 局所変数の例
void foo(int n, int m)
{
int a = n / m;
int b = n % m;
cout << "n / m = " << a << ", n % m = " << b << endl;
}
関数 foo は引数の商と剰余を求めて表示します。局所変数 a と b はスタック上に確保されます。
スタック
アドレス Low
[ b ] + <= SP(3)
[ a ] +
[ OLD FP ] <= SP(2) <= FP(2)
[リターンアドレス] <= SP(1)
[ n ]
[ m ]
[ x ] + 呼び出し元関数の局所変数
[ y ] +
[ OLD FP ] <= FP(1)
[リターンアドレス]
High [ ]
図 : 局所変数の確保
関数 foo が呼び出されたときのスタックポインタの位置は (1) です。局所変数をスタック上に確保するには、必要なサイズだけスタックポインタを Low アドレスに向かって移動させるだけです。ただし、単純に移動させると、リターンアドレスの位置がわからなくなるので、「フレームポインタ (FP)」を使ってスタックポインタを管理します。
局所変数を作る場合、まず FP の値をスタックに積みます。FP には呼び出し元関数のフレームポインタがセットされているので、その値をスタックに退避しないといけません。SP は (2) の位置に移動します。その値を FP にセットしてから局所変数のサイズだけ SP を移動させると (3)、局所変数 a, b の領域を確保することができます。
必要な局所変数のサイズはコンパイルした時点で決めることができます。また、フレームポインタを基準にすれば局所変数にアクセスすることも簡単にできます。この場合、引数のアクセスもスタックポインタではなくフレームポインタを使った方が簡単になります。
呼び出し元関数に戻るときは、まず FP の値を SP に戻します。すると SP は (2) の位置に戻るので、そこに積まれている値を POP して FP にセットします。これで呼び出し元関数のフレームポインタを元に戻すことができます。すると SP は (1) の位置にもどり、そこにはリターンアドレスが積まれているので、そのアドレスを取り出して呼び出し元関数に戻ることができます。
以上のことから、局所変数は関数の実行が終了した時点で解放されることもわかります。今まで局所変数として使っていた領域は、ほかの関数が実行されると、その局所変数もしくは引数を渡すための領域として使用されることになります。なお、コンパイラの最適化によっては、局所変数 a, b はスタック上に確保されるのではなく、レジスタに割り当てられる場合があります。
レジスタは CPU 内部にある一時記憶メモリのことで、CPU の外部に接続されているメモリ（主記憶メモリ）とは異なります。一般に、レジスタはメモリよりも高速にアクセスすることができるので、局所変数をスタック上に作るよりもレジスタに割り当てたほうが、プログラムを高速に実行することができます。
ところで、前々回説明した局所変数の値を交換するプログラム swap の動作も、スタックについて理解していれば当然な結果であると納得していただけると思います。
リスト : 値の交換（間違い）
#include <iostream>
using namespace std;
void swap(int a, int b)
{
int tmp = a;
a = b;
b = tmp;
}
int main()
{
int x = 10;
int y = 20;
swap(x, y);
cout << "x = " << x << endl;
cout << "y = " << y << endl;
}
swap が呼ばれた時点でのスタックの様子を下図に示します。
アドレス Low
A [ tmp ] <= SP
B [フレームポインタ]
C [リターンアドレス]
D [ a: 10 ] swap の引数 <-- ここの値を書き替え
E [ b: 20 ] <-- ることになる
F [ x: 10 ] main の局所変数
G [ y: 20 ]
H [フレームポインタ]
High
図 : swap を呼び出したときのスタック（その１）
main の局所変数 x, y の値がスタック上にコピーされて swap に渡され、swap はこの領域の値を書き替えるので、x と y の値は変更されないことがわかります。
Ｃ++で値を交換したい場合は参照を使います。
#include <iostream>
using namespace std;
void swap(int& a, int& b)
{
int tmp = a;
a = b;
b = tmp;
}
int main()
{
int x = 10;
int y = 20;
swap(x, y);
cout << "x = " << x << endl;
cout << "y = " << y << endl;
}
swap の引数は参照として宣言します。swap を呼び出したときのスタックは次のようになります。
アドレス Low
A [ tmp ] <= SP
B [フレームポインタ]
C [リターンアドレス]
D [ a: アドレス F ] swap の引数
E [ b: アドレス G ]
F [ x: 10 ] main の局所変数
G [ y: 20 ]
H [フレームポインタ]
High
図 : swap を呼び出したときのスタック（その２）
前回の Appendix で説明したように、引数 a にはアドレス F が入っているので、main で定義した局所変数 x にアクセスすることができます。引数 b も同様です。
いままでスタックについて説明してきましたが、それでは実際にはメモリのどこに割り当てられているのでしょうか。これは OS などの処理系に依存しますが、ここでは下図に示すようにスタック領域はプログラム本体の後ろに確保されると考えてください。
アドレス Low +-----------------+
| |
| プログラム領域 |
| |
+-----------------+
| |
| データ領域 |
| |
+-----------------+
| |
| ヒープ領域 |
| |
+-----------------+
: ↓ :
: :
: :
: ↑ :
+-----------------+
| |
| スタック領域 |
| |
High +-----------------+
図 : メモリの配置
外部変数はデータ領域に確保されます。ヒープ領域は「動的メモリ確保」で使用します。これはあとで説明します。スタックは高位アドレスから低位に向かって伸びていくので、再帰呼び出しの回数が多くなると (深くなるともいう) スタック領域が足りなくなって、他の領域を侵したときに Segmentation fault (コアダンプ) が発生します。簡単な例を示します。
リスト : スタックオーバーフロー (sample71.c)
#include <iostream>
using namespace std;
int sum(int n, int m)
{
if (n == m)
return n;
else
return n + sum(n + 1, m);
}
int main(void)
{
for (int i = 100; i < 10000000; i *= 10)
cout << i << ", " << sum(1, i) << endl;
}
$ clang++ sample71.cpp $ ./a.out 100, 5050 1000, 500500 10000, 50005000 100000, 705082704 Segmentation fault
関数 sum は再帰呼び出しが深くなるとスタック領域をはみ出して他の領域を侵すことになるので、Segmentation fault が発生します。ちなみに、デフォルトのスタックサイズはコマンド ulimit で調べることができます。
$ ulimit -a real-time non-blocking time (microseconds, -R) unlimited core file size (blocks, -c) 0 data seg size (kbytes, -d) unlimited scheduling priority (-e) 0 file size (blocks, -f) unlimited pending signals (-i) 15481 max locked memory (kbytes, -l) 65536 max memory size (kbytes, -m) unlimited open files (-n) 1024 pipe size (512 bytes, -p) 8 POSIX message queues (bytes, -q) 819200 real-time priority (-r) 0 stack size (kbytes, -s) 8192 cpu time (seconds, -t) unlimited max user processes (-u) 15481 virtual memory (kbytes, -v) unlimited file locks (-x) unlimited
M.Hiroi の環境では 8192 kbyte でした。
今までは、変数を宣言することでメモリの確保を行なっていました。局所変数はスタック上に割り当てられ、大域変数はデータ領域に確保されます。どちらの変数もコンパイル時にその大きさが決定されるので、プログラムを実行している途中でサイズを変更することはできません。あらかじめ決められたサイズ以上にデータを書き込めば、ほかのデータを破壊し、最悪の場合、プログラムは暴走することになります。
たとえば、テキストファイルを行単位で処理する場合、1 行の長さは不定長ですので、文字列長は実際に読み込んでみないとわかりません。このような場合、あらかじめ大域変数としてバッファを用意すると、そのバッファサイズより長い行が含まれているテキストファイルは処理できないことになります。
また、余裕をもって大きいサイズのバッファを用意すると、メモリの無駄使いになってしまいます。最近のように、メインメモリが大量に搭載されていれば、あまり問題にならないかもしれませんが、使用できるメモリが少ない環境では、プログラムを実行することができないかもしれません。
このような場合、プログラムの実行中に必要なサイズが判明した時点で、その大きさのメモリを、どこからか確保できるような手段が必要になります。このことを「動的メモリ割り当て」といいます。
Ｃ++でメモリを動的に割り当てるには new 演算子を使います。new はヒープ領域から必要なメモリ領域を確保します。なお、本稿ではヒープ領域の位置はデータ領域の後ろにあるものとして説明します。
Low アドレス +--------------+ ----
|プログラム領域| ↑
+--------------+ │
| | │
| データ領域 | プロセスで使う
| | スタック以外のメモリ
+--------------+ │
| ヒープ領域 | │ ===> メモリを割り当てる
| | │ new
+--------------+ │
│ │ <=== メモリを返還する
拡張する │ delete
↓ │
| | ↓
High アドレス+--------------+ ----
図 : ヒープ領域
malloc,calloc, realloc, free はＣ言語のライブラリ関数で、Ｃ++ では new と delete を使います。 一般に、Ｃ/Ｃ++の標準ライブラリではヒープ領域が足りなくなると、空きメモリがあれば自動的に拡張されます。上図に示すように、高位アドレスに向かって拡張されます。
new 演算子の書式を示します。
データ型* 変数 = new データ型
new は指定したデータ型を格納するメモリをヒープ領域から取得し、その先頭アドレス (ポインタ) を返します。確保したメモリは、領域の範囲内で使用するように注意して下さい。
使い終わったメモリは解放しないといけません。ヒープ領域が自動的に拡張されるからといって使ったまま放置したのでは、いつかはメモリ不足になってしまいます。メモリの解放には delete 演算子を使います。
delete newが返したポインタ
delete には new が返したポインタ (アドレス) を渡してください。delete に 0 を渡すこともできますが、その場合は何も起こりません。
簡単な例を示しましょう。
リスト : 動的メモリ割り当て (sample72.cpp)
#include <iostream>
using namespace std;
int main()
{
int* p = new int;
double* q = new double;
int* a = new int[8];
cout << p << endl;
cout << *p << endl;
cout << q << endl;
cout << *q << endl;
cout << a << endl;
for (int i = 0; i < 8; i++) cout << a[i] << " ";
cout << endl;
*p = 100;
*q = 1.2345;
a[0] = 10;
a[7] = 80;
cout << *p << endl;
cout << *q << endl;
for (int i = 0; i < 8; i++) cout << a[i] << " ";
cout << endl;;
// メモリの解放 (省略してもよい)
delete p;
delete q;
delete[] a;
return 0;
}
$ clang++ sample72.cpp $ ./a.out 0x5601845b5eb0 0 0x5601845b5ed0 0 0x5601845b5ef0 0 0 0 0 0 0 0 0 100 1.2345 10 0 0 0 0 0 0 80
new int で int 型に必要なメモリを、new double で double 型に必要なメモリを取得することできます。また、配列を確保することもできます。int a[8] と同じ大きさのメモリを取得するには new int[8] とします。これで配列に必要な 32 バイトのメモリを確保することができます。この場合、メモリの解放は演算子 delete[] で行います。あとは、new の返り値をポインタにセットして、そのメモリ領域にアクセスすればいいわけです。
ところで、取得したメモリ領域は使い終わったら元に戻す処理が必要になります。最近は、不要になったメモリ領域を自動的に回収する「ガベージコレクション (garbage collection, GC)」という機能を持つプログラミング言語が多くなりました。Ｃ/Ｃ++の場合、標準では GC をサポートしていないので、不要になったメモリ領域は自動的に回収されません。不要なメモリ領域は delete で解放することを忘れないでください。
ただし、ほとんどの処理系ではプログラムの終了時に new で取得したメモリを delete で解放する必要はありません。プログラムで使用したメモリは実行終了時に解放されますが、このとき new で割り当てたメモリも解放されるようになっているからです。もちろん、例外的な処理系もあるでしょうが、一般的には new で取得したメモリを最後まで使うのであれば、delete を省略できると考えてもいいでしょう。