Cプログラマへの道 #6 - 動的メモリ割り当て

この記事では、C言語における動的メモリ割り当てについて紹介します。

メモリ

関数や変数を定義すると、コンピュータはその情報をどのように保存するのでしょうか？メモリ管理のため裏で多くの複雑なことが起きていますが、 Cプログラマーとしては、以下のメンタルモデルを持っているだけで十分です。

メモリの上部には、コンパイルされたコードと静的変数(compiled code & static variables)があります。これらのサイズは固定され、プログラムが終了するまで存在し続けます。その次に、スタック(stack)があります。スタックのサイズは可変で、実行中の関数の重要な詳細（パラメーター、ローカル変数、リターンアドレス）を格納します。

スタックの仕組み

スタックの動作を理解するために、次のCコードを見てみましょう。

int add (int a, int b) {
    return a + b;
}
 
int main () {
    int x = 1;
    int y = 2;
    int z = add(1, 2);
    return 0;
}

上記のプログラムを実行し、スタックが時間の経過とともにどのように変化するかをみていきます。プログラムを開始すると、自動的にmainを探し、 mainのスタックフレームをスタックの上部に配置します。これには、パラメーター、ローカル変数、リターンアドレスが含まれます。この場合、リターンアドレスとローカル変数xとyがスタックaのように保存されます。

次に、main関数が別の関数addを呼び出します。ここで、スタックbのようにaddのための別のスタックフレームを追加します。 addの出力を計算するために必要なすべての値にアクセスできるため、出力を計算し、リターンアドレスにある値を出力に置き換えます。この際、addのパラメーターとローカル変数はすべて削除され、結果はmainスタックフレームの一部になります（スタックcのように）。その後、すべての計算が実行されると、リターンリンクを0に置き換え、プログラム全体の実行が終了すると空のスタック（スタックd）になります。

スタックは関連するデータを隣接して格納するため、より速くアクセスできます（キャッシュヒットの可能性が高い上にメモリの効率的な使用ができる）。また、使用されなくなったデータを自動的に削除します。しかし、スタックがデータを隣接して格納できるようにするには、各変数に割り当てるメモリ量を知る必要があります。これが、C言語は変数の型を指定することを求める理由です。

スタックがいっぱいになると（再帰関数呼び出しが多すぎたり、データ消費が多すぎたりするなど、いろいろな方法で発生する可能性があります）、スタックオーバーフロー(Stack Overflow)エラーが発生します。（はい、あの有名なウェブサイトの名前の由来でもあります！）

ヒープ

スタックは合理的で優れていますが、関数実行後にデータが自動的に削除されることは、必ずしも望ましくありません。変数が自動的に破棄されるのが望ましくない例を見てみましょう。

void slice (int **arr, int start, int end) {
    if (start < end) {
        int copy[end - start];
        int index = 0;
        int *p = *arr;
        for (int i = start; i <= end; i++) {
            copy[index] = p[i];
            index++;
        }
        *arr = copy;
    }
}
 
int main () {
    int xs[6] = {1,4,4,2,8,6};
    int *p = xs;
 
    slice(&p, 1, 4);
    printf("%d %d %d %d", p[0], p[1], p[2], p[3]); // => corrupted
    return 0;
}

ここでは、slice関数を定義しました。この関数は配列ポインタを取り、スライスされた配列を作成します。配列自体ではなくポインタを渡すのは、配列に新たな配列を代入することができないのに対し、ポインタは再代入できるからです。slice関数は、まずスタックにスライスされた配列を作成し、ポインタが指す位置を新しく作成した配列に変更しようとします。しかし、これは正しく機能しません。変数copyがスタックにあり、sliceが実行を終了するとスタックから削除されてしまうためです。

こんなとき、ヒープ(heap)が役に立ちます。ヒープはスタックと違って、プログラマーが動的に、つまり自由に、変数に割り当てるメモリの量や削除のタイミングを設定できます。

動的メモリ割り当て

sliceを動的メモリ割り当てを使用して書き直し、関数実行後にcopyが削除されないようにしましょう。

void slice (int **arr, int start, int end) {
    if (start < end) {
        // メモリを動的に割り当てる
        int size = end - start + 1;
        int *copy = malloc(sizeof(int)*size);
 
        int index = 0;
        int *p = *arr;
        for (int i = start; i <= end; i++) {
            copy[index] = p[i];
            index++;
        }
        *arr = copy;
    }   
}
 
int main () {
    int xs[6] = {1,4,4,2,8,6};
    int *p = xs;
 
    slice(&p, 1, 4);
    printf("%d %d %d %d", p[0], p[1], p[2], p[3]); // => 4, 4, 2, 8
 
    // メモリを解放する
    free(p);
 
    return 0;
}

ヒープでメモリを動的に割り当てるには、malloc（メモリ割り当て）関数を使用できます。この関数は割り当てたいメモリのサイズを引数として受け取ります。返されたポインタを逆参照することで、割り当てられたメモリの値を参照できます。calloc（連続割り当て）関数を使用して同じようにメモリを割り当てることもできます。 callocは、その割り当てられたメモリのすべての値を0に設定します。callocを使用すると、ヒープに既にランダムな値が格納されていても0に初期化してくれるため、動作がより予測可能です。しかし、各値にアクセスし、0に設定するのにかなりの時間がかかる傾向があります。（安全性とスピードのトレードオフ）

一度ヒープにメモリが割り当てられると、free関数を使ってそのメモリを解放するまで削除されたり、書き換えられることはありません。これはメモリを柔軟に操作できるという大きな力を与えてくれます。しかし、大きな力には常に大きな責任が伴います。もしそのメモリを解放するのを忘れると、プログラム全体を実行した後でもそのメモリは書き換えられないよう留められ、アクセスするためのポインタを失うと、メモリは永遠に使えなくなります。この恐ろしい事象をメモリリークと呼び、これを絶対に避けるために常にfreeを使用しなければなりません。

メモリ再割り当て

場合によっては、ポインタに割り当てられたメモリのサイズを変更したいことがあります。その場合、realloc（再割り当て）関数が便利です。

int main () {
 
    int *p = malloc(sizeof(int)*2);
 
    p[0] = 1;
    p[1] = 2;
 
    // Add more memory
    p = realloc(p, sizeof(int)*3);
 
    p[2] = 3;
 
    free(p);
 
    return 0;
}

reallocで以前より小さなサイズを指定すると、そのポインタに予約されていたスペースを一部解放します。ただし、メモリは依然として存在するため、ヒープのセキュリティを考慮する必要があります。

reallocがポインタより大きなサイズを受け取ると、まず同じ場所でメモリを拡張しようとします。拡張が他のメモリを妨げない場合、同じアドレスで拡張されます。それ以外の場合、他のスペースを探して別のアドレスに再割り当てします。別のアドレスに再割り当てする場合でも、メモリは依然として以前のポインタが指していたアドレスに存在するため、適切に処理する必要があります。また、ヒープに利用可能な連続したスペースがない場合は、NULLを返します。その場合も適切に処理する必要があります。以下は、その場合の処理方法の例です。

int *p = malloc(sizeof(int)*2);
 
    p[0] = 1;
    p[1] = 2;
 
    // メモリを追加する
    int *temp; // pのアドレスを失わないようにするための一時的なポインタ
    temp = realloc(p, sizeof(int)*3);
 
    if (temp == NULL) {
        return 1;
    }
    
    // アドレスが変更された場合、数値を0に設定する
    if (p != temp) {
        p[0] = 0;
        p[1] = 0;
    }
 
    p = temp;
    p[2] = 3;
    
    free(temp);
    free(p);
 
    return 0;

ヒープセキュリティは、malloc、calloc、またはreallocでヒープ上に機密データを保存する際に考慮すべき重要な事項です。機密データを保存する際には単純に暗号化を行うか、使用を終えたときに上記のように0に設定することを検討しなければいけません。

ガベージコレクタ

残念ながら我々人間はヒープを適切に管理してメモリリークを防いだりヒープセキュリティを担保することが苦手です。コードベースが大きくなればなるほど、ヒープを適切に管理することが難しくなっていきます。そのため、多くの賢い人々が高級言語（Python、Haskellなど）でガベージコレクタを開発しました。ガベージコレクタはプログラムと並行して実行され、人間の代わりにヒープを監視して未使用のメモリを自動的に解放してくれます。また、開発者は高級言語でポインタの詳細を抽象化し、変数がメモリにどのように格納されているかを気にする必要がないようにしました。これらの発明により高級言語はプログラマの生産性の向上や参入障壁の低下に大きく貢献しました。では、なぜそんな高級言語を差し置いて C言語を学んできたのでしょうか?

すべての物事には長所と短所があります。ガベージコレクタはプログラミングをとてもスムーズなものにしてくれる一方で、プログラムと並行して実行されなければならず、必然的により多くのメモリを消費し、プログラムの実行速度を遅くしてしまいます。また、ポインタの概念を抽象化することで、メモリ操作の柔軟性が失われます。これはシステムレベルのプログラミングや組み込みプログラミングには非常に重要であり、より高速で軽量なコードを書くのにも役立ちます。

高級言語、低級言語のどちらにも長所と短所があり、目的によってどちらが優れているかが違います。システムや組み込みプログラミングでないある程度のクオリティのプログラムをスピード感を持って開発したい場合、高級言語の方が優れているでしょう。しかし、実行時のスピードやメモリ消費に重きを置いているなら、難しいですがC言語のような比較的低級な言語を使用すべきです。ただ、このシリーズの最初に述べたように、 C言語を学ぶことはたとえC言語を今後使わないとしても、優れたプログラマになるのに役立つと考えます。引き続きC言語を学んでより良いプログラマを目指しましょう。

クイズ

この記事では、学習した内容を確認するためのクイズを設けます。記事のメイン部分を読んだ後に、ぜひ自分で問題を解いてみることを強くお勧めします。各問題をクリックすると答えが表示されます。

リソース

Portfolio Courses. 2021. Dynamic Memory Allocation | C Programming Tutorial. YouTube.
Portfolio Courses. 2021. realloc Security Vulnerability | C Programming Tutorial YouTube.

Q1: 整数配列ポインタからユニークな要素をフィルタリングする関数 unique を定義してください。