memory.dd

Ddoc

$(D_S メモリ管理,

	$(P 少しでも大きなプログラムなら、
	ほぼ確実に、メモリ割り当てと解放が必要になります。
	プログラムが複雑に、大きくなるにつれ、メモリ管理技術はより一層重要になります。
	Dは、メモリ管理の様々なオプションを提供します。
	)

	$(P Dでメモリを割り当てる簡便な方法とは次の３つです：)

	$(OL
	$(LI 静的データ。デフォルトのデータセグメントに割り当てられる。)
	$(LI スタックデータ。CPUのプログラムスタックへ割り当てられる。)
	$(LI $(LINK2 garbage.html, ガベージコレクトされたデータ)。
	GC
	のヒープから動的に割り当てられる。)
	)

	$(P この章では、これらを使うテクニックと、
	より高度な代替手段について説明します。
	)

	$(UL
	$(LI $(LINK2 #copy-on-write, 文字列 (と 配列) の Copy-on-Write))
	$(LI <a href="#realtime">リアルタイム</a>)
	$(LI <a href="#smoothoperation">スムーズな操作</a>)
	$(LI <a href="#freelists">フリーリスト</a>)
	$(LI <a href="#referencecounting">参照カウント</a>)
	$(LI <a href="#newdelete">明示的なクラスインスタンス割り当て</a>)
	$(LI <a href="#markrelease">Mark/Release</a>)
	$(LI <a href="#raii">RAII (Resource Acquisition Is Initialization)</a>)
	$(LI <a href="#stackclass">スタックへのクラスインスタンス割り当て</a>)
	$(LI <a href="#uninitializedarrays">スタックへの未初期化配列の割り当て</a>)
	$(LI $(LINK2 #isr, 割り込みサービスルーチン))
	)

<h2>$(LNAME2 copy-on-write, 文字列 (と 配列) の Copy-on-Write)</h2>

	$(P 配列を受け取って、
	それを（もしかしたら）変更して返す関数を考えてみましょう。
	配列は値ではなく参照渡しされますので、
	"この配列の内容の所有者は誰だ？"
	という重大な問題が持ち上がります。
	例えば、配列の内容を大文字に変換する関数：
	)

------
char[] toupper(char[] s)
{
    int i;

    for (i = 0; i < s.length; i++)
    {
        char c = s[i];
        if ('a' <= c && c <= 'z')
            s[i] = cast(char)(c - ('a' - 'A'));
    }
    return s;
}
------

	$(P 呼び出し側のs[]も変更されることに注意してください。これは、
	意図しない動作かもしれません。あるいはもっと悪く、s[]
	はメモリの読み取り専用領域のスライスかもしれません。
	)

	$(P しかし、toupper() で常に s[] のコピーを作ると、
	既に文字列が大文字だった場合には、
	無駄にメモリと時間を消費してしまいます。
	)

	$(P 解決策は copy-on-write、
	つまり文字列を変更する必要があるときだけコピーする、
	方式で実装することです。いくつかの文字列処理言語では、
	これが実際にデフォルトの挙動となっていますが、これは大きなコストがかかっています。
	文字列 "abcdeF" は関数によって５回コピーされることになるでしょう。
	最大に効率的に実装するには、copy-on-write を明示的にコードとして書くことです。
	以下に、効率的にcopy-on-writeを実装して書き直したtoupperを示します。
	)

------
char[] toupper(char[] s)
{
    int changed;
    int i;

    changed = 0;
    for (i = 0; i < s.length; i++)
    {
        char c = s[i];
        if ('a' <= c && c <= 'z')
        {
            if (!changed)
            {
                char[] r = new char[s.length];
                r[] = s;
                s = r;
                changed = 1;
            }
            s[i] = cast(char)(c - ('a' - 'A'));
        }
    }
    return s;
}

------

	$(P D の Phobos ランタイムライブラリでは、配列処理関数は copy-on-write
	で実装されています。
	)

<h2><a name="realtime">リアルタイム</a></h2>

	$(P リアルタイムプログラミングでは、プログラムは、遅れ時間の上限か
	操作完了にかかる時間の保証をしなくてはなりません。ほとんどの
	メモリ割り当て操作、これはmalloc/freeやGCを含みますが、には、
	理論的な時間の上限はありません。
	レイテンシを保証する最も信頼性のある方法は、
	時間制限の厳しい箇所で必要なメモリは全てあらかじめ割り当てておく、
	という手です。もしそこにメモリ割り当てのコードがなければ、
	GCは走らず、時間制限を超過してしまう原因にもなりません。
	)

<h2><a name="smoothoperation">スムーズな操作</a></h2>

	$(P リアルタイムプログラミングに関連した事項として、
	プログラムがGCによって任意の時点で動作中断することなく、
	スムーズに切れ目無く動作することが必要な場合があります。
	このようなプログラムの例としては、ガンシューティング・ゲームが上げられます。
	ゲームが不規則に中断するのは、プログラムにとっては致命的ではありませんが、
	ユーザーにとっては迷惑なことでしょう。
	)

	$(P いくつか、この挙動を和らげるテクニックがあります：)

$(UL
	$(LI スムーズに動作しなくてはならない箇所の前に、
		必要なデータを全て割り当てておく。)

	$(LI 元々プログラムが停止しているような箇所で、
		手動でGCを走らせる。
		そのような箇所の例としては、
		ユーザーにプロンプトを出したけれど
		ユーザー入力がまだ無い、という状態があります。これによって、
		GCが起きて欲しくない箇所でGCが走る確率を減らすことができます。)

	$(LI スムーズ動作の前に、std.gc.disable() を呼んでおき、後に std.gc.enable()
		を呼び出す。これによって、GCは未使用メモリを回収せずに新しいメモリを
		割り当てるようになります。)
)

<h2><a name="freelists">フリーリスト</a></h2>

	$(P フリーリストは、頻繁に割り当て/破棄が行われる型へのアクセスを高速化する
	強力な手法です。考え方は簡単で、使い終わったオブジェクトは、解放せずに
	フリーリストへ積んで置くというだけです。割り当て時は、
	まずフリーリストのオブジェクトを１つ取り出してきて使います。
	)
------
class Foo
{
    static Foo freelist;		// フリーリストの先頭

    static Foo allocate()
    {   Foo f;

	if (freelist)
	{   f = freelist;
	    freelist = f.next;
	}
	else
	    f = new Foo();
	return f;
    }

    static void deallocate(Foo f)
    {
	f.next = freelist;
	freelist = f;
    }

    Foo next;		// FooFreeList で使うため
    ...
}

void test()
{
    Foo f = Foo.allocate();
    ...
    Foo.deallocate(f);
}
------

	このようなフリーリスト方式で、高いパフォーマンスを得ることも可能です。

	$(UL
	$(LI 複数のスレッドから使う場合、allocate() と deallocate()
		関数には同期処理が必要です。)

	$(LI allocate()
		によってフリーリストから取得されるとき、
		Fooのコンストラクタは再実行されません。)

	$(LI RAIIと組み合わせる必要はありません。
		例外が投げられてフリーリストへ
		戻されなかったオブジェクトなども、
		いずれGCによって回収されます。)
	)

<h2><a name="referencecounting">参照カウント</a></h2>

	$(P 参照カウントとは、オブジェクトにカウント変数を含める、
	ということです。
	オブジェクトを指す参照が増えればカウントを増やし、参照が終われば
	カウントを減らします。カウントが0になったオブジェクトは削除できます。
	)

	$(P D は参照カウントを自動化する方法を提供していません。
	明示的に記述する必要があります。
	)

	$(P <a href="COM.html">Win32 COM プログラミング</a>
	では、参照カウントの管理に、
	メンバ AddRef() と Release() を使います。
	)

<h2><a name="newdelete">明示的なクラスインスタンス割り当て</a></h2>

	$(P D は、クラスのインスタンスのためのカスタムアロケータ/デアロケータを
	作る方法を提供しています。通常、インスタンスはGCのヒープから確保され、
	GCが走ったときに解放されます。特定の目的に対しては、
	$(I NewDeclaration) と $(I DeleteDeclaration)
	を書いてメモリ割り当てを管理することができます。
	例えば、Cのランタイム関数 
	$(TT malloc) と $(TT free) で割り当てを行う例です：
	)

------
import std.c.stdlib;
import core.exception;
import core.memory : GC;

class Foo
{
    new(size_t sz)
    {
        void* p;

        p = std.c.stdlib.malloc(sz);

        if (!p)
            throw new OutOfMemoryError();

        GC.addRange(p, sz);
        return p;
    }

    delete(void* p)
    {
        if (p)
        {
            GC.removeRange(p);
            std.c.stdlib.free(p);
        }
    }
}
------

	$(P new() の重要な特徴は：)

	$(UL
	$(LI new() には返値型を指定しませんが、
		void*として定義されます。
		new() は void* を返さなくてはなりません。)

	$(LI new() がメモリを割り当てられなかった場合、null を返すのではなく、
		必ず例外を投げるようにします。)

	$(LI new() の返すポインタは、
		デフォルトのメモリ境界に整列されている
		必要があります。Win32 システムでは、8バイト境界です。)

	$(LI 割り当て関数が Foo から派生したより大きいサイズのクラスから
		呼び出された場合のために、$(I size)
		パラメタが必要です。)

	$(LI メモリを割り当てられなかった場合、null を返すのではなく、
		必ず例外を投げます。どの例外を投げるかはプログラマに任されています。
		この例の場合は OutOfMemory でした。)

	$(LI GCがメモリ中のポインタを探索する時には、
		静的データセグメントと
		スタックは自動的に探索されますが、
		C のヒープはそうではありません。
		このため、FooやFooから派生したクラスがGCから確保した領域への参照を
		保持するときには、そのことをGCに伝える必要があります。
		これは、std.gc.addRange() メソッドによって行います)

	$(LI メモリの初期化は必要ありません。インスタンスのメンバを
		デフォルト初期化をするコードや、（もしあれば）
		コンストラクタを呼ぶコードが new() の呼び出しの後ろに
		自動で挿入されます。)
	)

	deleteの重要な特徴は：

	$(UL
	$(LI （もし存在すれば）デストラクタは、
		既に 引数p に対して呼び出されています。
		従って、pの指すメモリは既にゴミとなっていると仮定すべきです。)

	$(LI ポインタ p は null である可能性があります。)

	$(LI GC へ std.gc.addRange() で通知してあった場合は、deleteでは対応して
		std.gc.removeRange() を呼び出す必要があります。)

	$(LI delete() を作るなら、対応する new() も作成してください。)
	)

	$(P クラス特有のアロケータを使ってメモリを割り当てる場合は、
	'宙ぶらりんポインタ' や 'メモリリーク' が発生しないように
	注意深くコードを書かなくてはなりません。例外の存在まで考慮すると、
	メモリリークを防ぐためには RAII を使う習慣が重要です。
	)

	$(P 構造体や共用体についても、
	カスタムアロケータを定義して使うすることができます。)

<h2><a name="markrelease">Mark/Release</a></h2>

	$(P Mark/Release は、スタックを使うのと同等のメモリ割り当て/解放方法です。
	$(SINGLEQUOTE スタック) はメモリ中に作られます。オブジェクトは、メモリ中でポインタを
	下に動かすことで作成します。個々のポイントが
	$(SINGLEQUOTE mark) され、
	それまでに確保されたオブジェクトを解法します。
	)

------
import std.c.stdlib;
import core.exception;
import core.memory : GC;

class Foo
{
    static void[] buffer;
    static int bufindex;
    static const int bufsize = 100;

    static this()
    {
        void* p;
        p = malloc(bufsize);

        if (p is null)
            throw new OutOfMemoryError;

        GC.addRange(p, bufsize);
        buffer = p[0 .. bufsize];
    }

    static ~this()
    {
        if (buffer.length)
        {
            GC.removeRange(buffer.ptr);
            free(buffer.ptr);
            buffer = null;
        }
    }

    new(size_t sz)
    {
        void* p;

        p = &buffer[bufindex];
        bufindex += sz;

        if (bufindex > buffer.length)
            throw new OutOfMemoryError;

        return p;
    }

    delete(void* p)
    {
        assert(0);
    }

    static int mark()
    {
        return bufindex;
    }

    static void release(int i)
    {
        bufindex = i;
    }
}

void main()
{
    int m  = Foo.mark();
    Foo f1 = new Foo;           // 割り当て
    Foo f2 = new Foo;           // 割り当て

    Foo.release(m);             // f1 と f2
}
------

	$(P 割り当て用の buffer[] それ自身は、
		GC 対象領域に追加されます。
		このため、Foo.new() でその作業をするコードは必要ありません。)

<h2><a name="raii">RAII (Resource Acquisition Is Initialization)</a></h2>

	$(P 明示的なアロケータ/デアロケータを使っているときは、
	メモリリークを避けるためにRAIIというテクニックが有効です。
	そのようなクラスには <a href="attribute.html#scope">scope 属性</a>
	を加えると良いでしょう。
	)

<h2>$(LNAME2 stackclass, スタックへのクラスインスタンス割り当て)</h2>

	$(P クラスのインスタンスは、通常はガベージコレクタに管理された
	ヒープに割り当てられます。しかし、以下の条件が満たされていれば…)

	$(UL
	$(LI 関数のローカルシンボルで)
	$(LI $(B new) で割り当てられていて)
	$(LI その $(B new) にはアロケータ用の引数が指定されておらず（コンストラクタ用の引数は可）)
	$(LI $(B scope) 宣言されている)
	)

	$(P …インスタンスはスタックに割り当てられます。
	これはインスタンスのallocate/freeを行うよりも効率的ですが、
	オブジェクトへの参照が関数からのreturn後も生き延びることのないよう、
	注意が必要です。)

---
class C { ... }

scope c = new C();	// c はスタックに割り当てられる
scope c2 = new C(5);    // スタックに割り当てられる
scope c3 = new(5) C();  // カスタムアロケータで割り当てられる
---

	$(P クラスにデストラクタが定義されていた場合、
	そのデストラクタが、オブジェクトがスコープを抜けるタイミングで呼ばれることが保証されます。
	例外でスコープを抜けるときも同様です。)


<h2><a name="uninitializedarrays">スタックへの未初期化配列の割り当て</a></h2>

	$(P Dでは、配列は常に初期化されます。例えば、以下の宣言：)

------
void foo()
{   byte[1024] buffer;

    fillBuffer(buffer);
    ...
}
------

	$(P wiは、最初にbuffer[]の中身を初期化するため、
	あなたが思うほどは速くないかもしれません。もし注意深くプロファイルを取った結果、
	この初期化がスピードに関して問題になっているとわかったならば、
	$(I VoidInitializer) によってこれを除去することができます:
	)

------
void foo()
{   byte[1024] buffer = $(B void);

    fillBuffer(buffer);
    ...
}
------

	$(P スタック上の未初期化データには、
	使用する前によく考えておかねばならない危険が伴います：
	)

	$(UL

	$(LI スタック上の未初期化データは、参照が残っていないか、
	ガベージコレクタによって探索されます。未初期化データの中身は元々 D
	のスタックフレームだったものでしょうから、たぶんそこには GC
	のヒープへの参照が残っていて、その部分のGCメモリが解放されなくなります。
	この問題は実際に発生するもので、
	追跡するのは極めてやっかいです。)

	$(LI 関数から、スタックフレームに割り当てられたデータへの参照を
	外に返すことは可能です。
	その後新しいスタックフレームを古いデータの上に割り当て、未初期化で使った場合、
	古いデータへのリファレンスはまだ有効であるかのように振る舞います。
	このようなプログラムはエラーの要因です。スタックフレーム上の全てのデータの初期化は、
	多くのバグを確実に再現性があるものにするのに大きな役に立ちます。)

	$(LI 未初期化データは、正しく使ってさえ、バグとトラブルの元です。
	我々のDの設計の目的は、
	未定義動作のもとを除いて信頼性と移植性を高めることでした。
	そして、未初期化データは未定義・無移植性・エラー的・予測不能動作の大元です。
	したがって、ここにあげたイディオムは、他に最適化の種が尽きて、
	ベンチマークが確かに該当箇所が全体のボトルネックになっていることが確認できた時のみ、
	使用されるべきです。)

	)

<h2><a name="isr">割り込みサービスルーチン</a></h2>

	$(P ガベージコレクタがメモリ回収を実行するときには、
	レジスタやスタックの内容を調べてGCで割り当てたオブジェクトへの参照を集めるために、
	いったん全てのスレッドの実行を停止する必要があります。
	しかし、ISR (Interrupt Service Routine / 割り込みサービスルーチン)
	スレッドを停止してしまうと、プログラムの動きがおかしくなってしまいます。
	)

	$(P Tこのため、ISR スレッドは停止すべきではありません。
	標準ライブラリ $(LINK2 phobos/core_thread.html, core.thread)
	の関数で作ったスレッドは停止しますが、Cの
	$(TT _beginthread()) やそれと同等のルーチンで作ったスレッドは、
	GCがその存在を知らないため、停止しません。
	)

	$(P これを使って適切な動作を得るためには:)

	$(UL

	$(LI ISR スレッドはGCでメモリを割り当てることはできません。
	つまり、グローバルな $(TT new) を使用できないということです。
	さらに、動的配列のリサイズや、
	連想配列への要素追加も不可です。Dランタイムライブラリを使うときは、
	GCでメモリを割り当てる可能性がないことを確認するか…
	もっとベターなのは、ISR では D 
	のライブラリ関数を呼ばないことです。)

	$(LI 「ISR だけがGCで割り付けたオブジェクトへの参照を保持している状態」
	を作ってはいけません。そうなると、たとえISRで使用中でも
	GC がメモリを解放するおそれがあります。解決策としては、
	別にダミーの停止スレッドを作ってそこにも参照を置いておくか、
	参照をグローバルに保持しておくことです。)

	)
)

Macros:
	TITLE=メモリ管理
	WIKI=Memory
	CATEGORY_ARTICLES=$0